Python：查找表的列表与字典

Question

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

我知道你可以为这两种方法执行以下操作：

if something in dict_of_stuff:
    pass

和

if something in list_of_stuff:
    pass

我的想法是，该命令将更快，更高效。

谢谢你的帮助。

编辑1
我正在尝试做的更多信息。 欧拉问题92。我正在查找表，以查看计算出的值是否已经准备好了。

编辑2
查找效率。

编辑3
没有与值相关的值…那么集合会更好吗？

Answer 1

速度

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

记忆

字典和集合都使用哈希，并且它们使用的内存比仅用于对象存储的更多。根据AM Kuchling在Beautiful Code中的介绍，该实现尝试使哈希2/3保持完整，因此你可能会浪费一些内存。

如果你不立即添加新条目（根据更新的问题，你可以这样做），则可能需要对列表进行排序并使用二进制搜索。这是O（log n），对于字符串来说可能更慢，对于没有自然顺序的对象则不可能。