我有大约1000万的价值，我需要把某种类型的查找表，所以我想知道哪个会更有效的列表或字典?
我知道你可以这样做:
if something in dict_of_stuff:
pass
and
if something in list_of_stuff:
pass
我的想法是字典会更快更有效。
谢谢你的帮助。
编辑1 再多说点我要做的事。欧拉92题。我正在做一个查找表，看看计算的值是否已经全部计算完毕。
编辑2 查找效率。
编辑3 没有与值…相关的值。那么一套会更好吗?
当前回答
作为一组新的测试，以表明@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
这里我们还比较了一个元组，在某些用例中，元组比列表更快(并且使用更少的内存)。在查找表的情况下，元组也没有更好。
字典和电视机都表现得很好。这就涉及到@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) 值在原始数据集中的位置(即[2]返回在原始数据列表中找到数据的索引列表:[1,4])
其他回答
我做了一些基准测试，结果表明，对于大型数据集，dict比list和set都快，在linux上的i7 CPU上运行python 2.7.3:
Python -mtimeit -s 'd=range(10**7)' '5*10**6 in d' 10个循环，最好的3:64.2 msec每循环 Python -mtimeit -s 'd=dict.fromkeys(range(10**7))' '5*10**6 in d' 10000000次循环，最好为0.0759 usec /循环 python -mtimeit -s 'from 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
这里我们还比较了一个元组，在某些用例中，元组比列表更快(并且使用更少的内存)。在查找表的情况下，元组也没有更好。
字典和电视机都表现得很好。这就涉及到@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) 值在原始数据集中的位置(即[2]返回在原始数据列表中找到数据的索引列表:[1,4])
速度
在列表中的查找是O(n)，在字典中的查找是O(1)平摊，关于数据结构中的项的数量。如果不需要关联值，则使用集合。
内存
字典和集合都使用哈希，它们比对象存储使用更多的内存。根据上午。在Beautiful Code中，实现尝试保持hash的2/3是满的，所以你可能会浪费一些内存。
如果您没有动态地添加新条目(根据您更新的问题，您会这样做)，那么对列表进行排序并使用二分搜索可能是值得的。这是O(log n)，对于字符串来说可能更慢，对于没有自然顺序的对象来说是不可能的。
字典是一个哈希表，所以找到键非常快。所以在dict和list之间，dict会更快。但是如果您没有要关联的值，那么使用集合会更好。它是一个哈希表，没有“表”部分。
编辑:对于你的新问题，是的，一套会更好。只需创建2个集合，一个用于以1结尾的序列，另一个用于以89结尾的序列。我已经成功地用集合解决了这个问题。
你想要一本字典。
对于Python中的(未排序的)列表，“in”操作需要O(n)时间——当你有大量数据时，这并不好。另一方面，字典是一个哈希表，因此您可以预期查找时间为O(1)。
正如其他人所注意到的，如果您只有键而不是键/值对，那么您可能会选择一个集合(一种特殊类型的dict)。
相关:
Python wiki:关于Python容器操作的时间复杂度的信息。 SO: Python容器操作时间和内存复杂度
