在Python中搜索列表的最快方法

Question

当您在 a 中执行诸如 "test" in a 之类的操作（其中 a 是一个列表）时，Python 是否会对列表进行顺序搜索，或者是否创建哈希表表示形式来优化查找？在应用程序中，我需要这个，因为我将在列表中进行大量查找，因此最好执行类似 b = set(a) 的操作，然后在中执行 "test" b？另请注意，我将拥有的值列表不会有重复的数据，而且我实际上并不关心它的顺序；我只需要能够检查一个值是否存在。

Answer 1

另请注意，我将拥有的值列表不会有重复的数据，而且我实际上并不关心它的顺序；我只需要能够检查值是否存在。

不要使用列表，使用 set() 相反。它完全具有您想要的属性，包括速度极快的 in 测试。

我发现在更改一组列表的地方（主要是繁重的数字运算），速度提高了 20 倍甚至更高。

Answer 2

"test" in a 与列表 a 将进行线性搜索。动态设置哈希表比线性搜索要昂贵得多。另一方面，b 中的“test”将执行 O(1) 哈希查找。

在您描述的情况下，似乎没有理由使用列表而不是集合。

Answer 3

我认为按照既定的实施方式会更好。我知道集合的查找时间为 O(1)。我认为列表需要 O(n) 查找时间。但即使列表也是 O(1) 查找，切换到集合也不会造成任何损失。

此外，集合不允许重复值。这也会使你的程序的内存效率稍微提高一些

Answer 4

列表和元组似乎有相同的时间，并且使用“in”对于大数据来说很慢：

>>> t = list(range(0, 1000000))
>>> a=time.time();x = [b in t for b in range(100234,101234)];print(time.time()-a)
1.66235494614
>>> t = tuple(range(0, 1000000))
>>> a=time.time();x = [b in t for b in range(100234,101234)];print(time.time()-a)
1.6594209671

这是更好的解决方案：在巨大列表中查找/搜索的最有效方法（python）

它非常快：

>>> from bisect import bisect_left
>>> t = list(range(0, 1000000))
>>> a=time.time();x = [t[bisect_left(t,b)]==b for b in range(100234,101234)];print(time.time()-a)
0.0054759979248