Nop*_*ope 158 python performance
我有大约1000万个值,我需要放在某种类型的查找表中,所以我想知道哪个列表或字典更有效？
我知道你可以做两件事:
if something in dict_of_stuff:
pass
和
if something in list_of_stuff:
pass
我的想法是dict会更快更有效率.
谢谢你的帮助.
编辑1
关于我正在尝试做什么的更多信息. 欧拉问题92.我正在查找表,看看计算出的值是否已经准备就绪.
编辑2
查找效率.
编辑3
没有与值相关的值...那么一组会更好吗？
Tor*_*rek 205
列表中的查找是O(n),字典中的查找是分摊的O(1),关于数据结构中的项目数.如果您不需要关联值,请使用集合.
字典和集合都使用散列,并且它们使用的内存比仅用于对象存储的内存多得多.根据AM Kuchling的漂亮代码,实现尝试保持哈希2/3满,所以你可能会浪费相当多的内存.
如果您不动态添加新条目(根据更新的问题,您可以这样做),可能需要对列表进行排序并使用二进制搜索.这是O(log n),对于字符串来说可能更慢,对于没有自然排序的对象来说是不可能的.
nos*_*klo 42
dict是一个哈希表,所以找到密钥真的很快.所以在dict和list之间,dict会更快.但是如果你没有要关联的值,那么使用集合会更好.它是一个哈希表,没有"表"部分.
编辑:对于你的新问题,是的,一套会更好.只创建2组,一组用于序列以1结尾,另一组用于以89结尾的序列.我已成功使用集合解决了这个问题.
Eri*_*F89 27
我做了一些基准测试,事实证明dict比大型数据集的列表和设置更快,在Linux上的i7 CPU上运行python 2.7.3:
python -mtimeit -s 'd=range(10**7)' '5*10**6 in d'
10个循环,最佳3:每循环64.2毫秒
python -mtimeit -s 'd=dict.fromkeys(range(10**7))' '5*10**6 in d'
10000循环,最佳3:0.0759 usec每循环
python -mtimeit -s 'from sets import Set; d=Set(range(10**7))' '5*10**6 in d'
1000000循环,最佳3:每循环0.262 usec
正如您所看到的,dict比列表快得多,并且比set快3倍.但是在某些应用程序中,您可能仍然希望选择适合它的美丽.如果数据集非常小(<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
在这里我们还比较了 a ，已知在某些用例中tuple它比 a 更快（并且使用更少的内存）。lists对于查找表来说，情况tuple并没有更好。
和 都dict表现set得非常好。这提出了一个与@SilentGhost关于唯一性的答案有关的有趣观点：如果OP在数据集中有10M个值，并且不知道其中是否有重复项，那么值得并行保留其元素的集合/字典使用实际数据集，并测试该数据集/字典中是否存在。10M 数据点可能只有 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]：）你想要一个字典.
对于Python中的(未排序)列表,"in"操作需要O(n)时间 - 当您有大量数据时不好.另一方面,dict是一个哈希表,所以你可以期待O(1)查找时间.
正如其他人所指出的那样,如果你只有键而不是键/值对,你可以选择一组(一种特殊类型的dict).
有关:
如果数据是唯一的set()将是最有效的,但是两个 - dict(也需要唯一性,oops :)