python - pandas index.searchsorted() 是做什么的？

Question

我正在处理两个数据帧 df1 和 df2。我使用了代码:

df1.index.searchsorted(df2.index)

但我不确定它是如何工作的。有人可以向我解释一下吗？

Answer 1

该方法应用 binary search到索引。这是一种众所周知的算法，它利用值已经排序的事实来以尽可能少的步骤找到插入索引。

二分搜索的工作原理是选择值的中间元素，然后将其与搜索值进行比较；如果该值低于中间元素，则将搜索范围缩小到前半部分，如果下半部分较大，则查看下半部分。

通过这种方式，您可以将查找元素所需的步骤数减少到至多 索引长度的对数。对于 1000 个元素，少于 7 步，对于一百万个元素，少于 14 步，等等。

插入索引是添加您的值以保持索引有序的地方； left 位置也恰好是 匹配 值的索引，因此您还可以使用它来查找插入缺失值或重复值的位置，以及测试是否索引中存在给定值。

pandas 实现基本上是 numpy.sortedsearch()函数，它使用 generated C code优化针对不同对象类型的搜索，尽可能地降低速度。

Pandas 在各种索引实现中使用该方法来确保快速操作。您通常不会使用此方法来测试索引中是否存在值，例如，因为 Pandas 索引已经为您实现了一个高效的 __contains__ 方法，通常基于 searchsorted() 有意义的地方。参见 DateTimeEngine.__contains__()对于这样的例子。