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

Question

当你像这样执行 "test" in a，其中a是一个列表时，Python会在列表上执行顺序搜索还是创建哈希表表示以优化查找？在我需要这个的应用程序中，我将对列表进行大量查找，那么做类似于 b = set(a) 然后 "test" in b 的操作是否最好？也请注意，我将拥有的值列表不会有重复数据，我实际上并不关心它的顺序; 我只需要能够检查某个值是否存在。

- Ian Burris

---

创建哈希需要检查每个元素以构建哈希，因此除非由于某种原因比较两个值的相等性非常缓慢，否则无法更快。当然，如果将重复使用这样的哈希，则构建此类哈希会更快。 - Karl Knechtel

Answer 1

请使用set()而不是列表。它具有您想要的属性，包括超快速的in测试，并且值列表中不会有重复数据，实际上您并不关心其顺序；我只需要能够检查值是否存在即可。

在某些地方（主要是重量级数字计算），使用集合替换一个列表可以看到20倍甚至更高的加速。

- orlp

---

@blcArmadillo：由于集合中没有重复数据且不关心顺序，因此使用集合是最好的选择 - 而且您始终可以枚举集合成员或在需要时快速将其转换为列表。 - martineau

我使用了这个，它大大加速了事情。谢谢。 - Josh Usre

哇，我之前写的脚本很愚蠢，需要遍历两个文件来查找相似行，但这个新方法将时间从大约20分钟缩短到不到1分钟。谢谢！ - Parker

使用一个非常大的列表，进行近200万次检查，计算时间从3小时降至不到1分钟!!!! - vin

我认为用户在这里应该小心，因为如果列表包含非可哈希类型（如字典或列表），使用 set(ORIGINAL_LIST) 将会引发异常。 - Ebram Shehata

Answer 2

"test" in a 在列表 a 中进行线性搜索。动态设置哈希表的开销比线性搜索要大得多。另一方面，"test" in b 将进行平均为 O(1) 的哈希查找。

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

- Sven Marnach

---

只有在 b 构建后进行了许多查找时，才会出现这种情况。如果每次执行查找都需要重新构建 b，则“test” in b 会变慢，因为集合的构建不是线性的。 - Jamie Wong

@Jamie：从原帖中可以看出：“在我需要这个应用程序中，我将会对列表执行很多次查找操作[...]”。看起来有很多次查找。 - Sven Marnach

我同意这是正确的解决方案 - 只是想要弄清楚。 - Jamie Wong

Answer 3

我认为使用集合实现会更好。我知道集合的查找时间是O(1)，而列表的查找时间是O(n)。即使列表也是O(1)查找，但切换到集合也不会有任何损失。

此外，集合不允许重复值。这也会使您的程序略微更加内存高效。

- inspectorG4dget

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

- Grzegorz Świerad

---

列表必须先排序。 - Grzegorz Świerad