作为一组新的测试,以证明 @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),在某些用例中,元组被认为比列表更快(并且使用更少的内存)。但在查找表的情况下,元组表现并不更好。
字典(dict)和集合(set)的性能都非常好。这带出了一个有趣的观点,与@SilentGhost关于唯一性的答案有关:如果OP在数据集中有1000万个值,并且不知道其中是否存在重复项,则值得将其元素的set/dict与实际数据集并行保留,并在其中测试是否存在。可能这1000万个数据点只有10个唯一值,这是一个更小的搜索空间!
SilentGhost关于字典的错误实际上很有启示性,因为可以使用字典将重复数据(在值中)相关联到一个不重复的集合(键)中,从而保持一个数据对象来保存所有数据,但仍然像查找表一样快速。例如,字典键可以是要查找的值,而值可以是虚拟列表中该值出现的索引列表。
例如,如果要搜索的源数据列表是l=[1,2,3,1,2,1,4],则可以通过以下字典对其进行优化,以实现搜索和内存的优化:
>>> 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]
)