排序列表的Python"in"关键字的效率

Question

如果我有一个已经排序的列表并使用in关键字,例如:

a = [1,2,5,6,8,9,10]
print 8 in a

我认为这应该进行顺序搜索,但是我可以通过二进制搜索来加快速度吗？是否有一种pythonic方式在排序列表中搜索？

Answer 1

标准库具有bisect支持按排序顺序搜索的模块.

但是,对于小型列表,我敢打赌,in运营商背后的C实现会击败bisect.您必须使用一堆常见案例进行测量,以确定目标硬件上真正的收支平衡点......

值得注意的是,如果你可以使用无序迭代(即a set),那么你可以O(1)平均进行查找(使用in运算符),与序列上的二分相比,序列上O(logN)的in运算符是O(N).并且,通过设置,您还可以避免首先对其进行排序的成本:-).

Answer 2

标准库中的 module 中有对 Python 的二分搜索bisect。它不支持in/contains原样，但你可以编写一个小函数来处理它：

from bisect import bisect_left
def contains(a, x):
    """returns true if sorted sequence `a` contains `x`"""
    i = bisect_left(a, x)
    return i != len(a) and a[i] == x

然后

>>> contains([1,2,3], 3)
True
>>> contains([1,2,3], 4)
False

不过，这不会很快，因为它是用 Python 编写的，而不是用 C 编写的，所以在很多情况下，bisect您可能会发现顺序更快。in bisect自 Python 2.4 起，CPython 中就有了可选的 C 加速。

在 CPython 中很难计算出准确的收支平衡点。这是因为代码是用C写的；如果你检查的值大于或小于序列中的任何值，那么 CPU 的分支预测就会对你耍花招，你会得到：

In [2]: a = list(range(100))
In [3]: %timeit contains(a, 101)
The slowest run took 8.09 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 370 ns per loop

这里，3中最好的并不代表算法的真实运行时间。

但通过调整测试，我得出的结论是，平分可能比in只有 30 个元素的列表更快。

但是，如果您要执行很多in操作，则应该使用set; 您可以将列表一次转换为集合（甚至不排序），并且该in操作将比任何二分搜索更快：

>>> a = [10, 6, 8, 1, 2, 5, 9]
>>> a_set = set(a)
>>> 10 in a_set
True

另一方面，对列表进行排序比构建集合具有更大的时间复杂度，因此大多数情况下集合是可行的方法。