小开

如果数据是唯一的set()将是最有效的，但two - dict(它也要求唯一性，哎呀:)

小开

字典是一个哈希表，所以找到键非常快。所以在dict和list之间，dict会更快。但是如果您没有要关联的值，那么使用集合会更好。它是一个哈希表，没有“表”部分。

编辑:对于你的新问题，是的，一套会更好。只需创建2个集合，一个用于以1结尾的序列，另一个用于以89结尾的序列。我已经成功地用集合解决了这个问题。

小开

你想要一本字典。

对于Python中的(未排序的)列表，“in”操作需要O(n)时间——当你有大量数据时，这并不好。另一方面，字典是一个哈希表，因此您可以预期查找时间为O(1)。

正如其他人所注意到的，如果您只有键而不是键/值对，那么您可能会选择一个集合(一种特殊类型的dict)。

速度

在列表中的查找是O(n)，在字典中的查找是O(1)平摊，关于数据结构中的项的数量。如果不需要关联值，则使用集合。

内存

字典和集合都使用哈希，它们比对象存储使用更多的内存。根据上午。在漂亮的代码中的Kuchling，实现尝试保持散列2/3满，因此您可能会浪费相当多的内存。

如果您没有动态地添加新条目(根据您更新的问题，您会这样做)，那么对列表进行排序并使用二分搜索可能是值得的。这是O(log n)，对于字符串来说可能更慢，对于没有自然顺序的对象来说是不可能的。

小开

实际上，您不需要在表中存储1000万个值，所以这都不是什么大问题。

提示:想想在第一次平方和运算之后你的结果能有多大。最大可能的结果将远远小于1000万……

小开

set()正是你想要的。O(1)查找，并且小于字典。

小开

我做了一些基准测试，结果表明，对于大型数据集，dict比list和set都快，在linux上的i7 CPU上运行python 2.7.3:

< p > python -mtimeit -s 'd=range(10**7)' '5*10**6 in d'

10个循环，最好的3:64.2 msec每个循环
< p > python -mtimeit -s 'd=dict.fromkeys(range(10**7))' '5*10**6 in d'

10000000个循环，最好的3:0.0759 usec每个循环
< p > python -mtimeit -s 'from sets import Set; d=Set(range(10**7))' '5*10**6 in d'

1000000循环，最好的3:每循环0.262 usec

如您所见，dict比list快得多，比set快大约3倍。在一些应用程序中，你可能仍然想选择set，因为它很漂亮。如果数据集真的很小(<1000个元素)列表执行得相当好。

小开

作为一组新的测试，以表明@EriF89在这么多年后仍然是正确的:

$ python -m timeit -s "l={k:k for k in xrange(5000)}"    "[i for i in xrange(10000) if i in l]"
1000 loops, best of 3: 1.84 msec per loop
$ python -m timeit -s "l=[k for k in xrange(5000)]"    "[i for i in xrange(10000) if i in l]"
10 loops, best of 3: 573 msec per loop
$ python -m timeit -s "l=tuple([k for k in xrange(5000)])"    "[i for i in xrange(10000) if i in l]"
10 loops, best of 3: 587 msec per loop
$ python -m timeit -s "l=set([k for k in xrange(5000)])"    "[i for i in xrange(10000) if i in l]"
1000 loops, best of 3: 1.88 msec per loop

这里我们还比较了tuple，在某些用例中，它比lists更快(并且使用更少的内存)。在查找表的情况下，tuple也没有更好。

dict和set都表现得很好。这就涉及到@SilentGhost关于唯一性的回答:如果OP在一个数据集中有10M个值，并且其中是否存在重复值是未知的，那么值得将其元素与实际数据集并行保存，并测试其在该集合/字典中的存在性。10M数据点可能只有10个唯一值，这是一个小得多的搜索空间!

SilentGhost关于字典的错误实际上很有启发性，因为人们可以使用字典将复制的数据(在值中)关联到一个非复制的集(键)中，从而保持一个数据对象来保存所有数据，但仍然像查找表一样快。例如，dict键可以是正在查找的值，而值可以是该值所在的虚构列表中的索引列表。

例如，如果要搜索的源数据列表是l=[1,2,3,1,2,1,4]，则可以通过将其替换为以下dict来优化搜索和内存:

>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> l=[1,2,3,1,2,1,4]
>>> for i, e in enumerate(l):
...     d[e].append(i)
>>> d
defaultdict(<class 'list'>, {1: [0, 3, 5], 2: [1, 4], 3: [2], 4: [6]})

有了这个词典，我们可以知道:

如果一个值在原始数据集中(即2 in d返回True)
在哪里值在原始数据集中(即d[2]返回在原始数据列表中找到数据的索引列表:[1, 4])

Python: List vs Dict用于查找表

速度

内存