python lis中的搜索算法

Question

检查列表中是否存在元素的效率如何？你知道吗

假设我有一个listL=[1,2,3,4,5]并执行以下命令：

5 in L
>>> True
12 in L
>>> False

这两个都要花多少时间。确切地说，python的列表采用什么样的搜索算法？你知道吗

Answer 1

检查列表中的成员身份是一个O(n)操作。 列表中的每一项都将按相等顺序进行检查。如果发现某个项相等，则返回True。因此，检查成员资格所需的时间取决于列表的长度，以及列表中项目的位置（如果有）：

In [1]: L = list(range(10**6))

In [2]: %timeit 0 in L
10000000 loops, best of 3: 43.2 ns per loop

In [3]: %timeit 999999 in L
100 loops, best of 3: 16.1 ms per loop

In [4]: %timeit 1000001 in L
100 loops, best of 3: 16.1 ms per loop

相反，检查集合或dict中的成员身份是O(1)操作。你知道吗

In [103]: s = set(xrange(10**6))

In [104]: %timeit 0 in s
10000000 loops, best of 3: 48 ns per loop

In [105]: %timeit 999999 in s
10000000 loops, best of 3: 65.3 ns per loop

In [106]: %timeit 1000001 in s
10000000 loops, best of 3: 45.7 ns per loop

这里是一个wiki页面，总结了complexity of operations on Python builtin types。你知道吗