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

作为一组新的测试，以表明@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])

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

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

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

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

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

速度

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

内存

字典和集合都使用哈希，它们比对象存储使用更多的内存。根据上午。在Beautiful Code中，实现尝试保持hash的2/3是满的，所以你可能会浪费一些内存。

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