Python:用于查找表的列表与字典

Question

我有大约 1000 万个值需要放入某种类型的查找表中，所以我想知道 list 或 dict 哪个更有效？

我知道你可以为两者做这样的事情:

if something in dict_of_stuff:
    pass

和

if something in list_of_stuff:
    pass

我的想法是 dict 会更快更高效。

感谢您的帮助。

编辑 1
关于我正在尝试做的事情的更多信息。 Euler Problem 92 .我正在制作一个查找表，以查看计算的值是否已全部计算完毕。

编辑 2
查找效率。

编辑 3
没有与值相关联的值...那么 set 会更好吗？

Answer 1

速度

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

内存

字典和集合都使用散列，它们使用的内存比仅用于对象存储要多得多。据 A.M.在 Beautiful Code 中，Kuchling 的实现试图保持 2/3 的散列满，所以你可能会浪费相当多的内存。

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