Python:用于查找表的列表与字典 [英] Python: List vs Dict for look up table

问题描述

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

I have about 10million values that I need to put in some type of look up table, so I was wondering which would be more efficient a list or dict?

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

I know you can do something like this for both:

if something in dict_of_stuff:
    pass

和

if something in list_of_stuff:
    pass

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

My thought is the dict will be faster and more efficient.

感谢您的帮助.

编辑 1
关于我正在尝试做什么的更多信息.欧拉问题 92.我正在制作一个查找表，以查看计算的值是否已全部计算完毕.

EDIT 1
Little more info on what I'm trying to do. Euler Problem 92. I'm making a look up table to see if a value calculated has all ready been calculated.

编辑 2
查找效率.

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

推荐答案

速度

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

Speed

Lookups in lists are O(n), lookups in dictionaries are amortized O(1), with regard to the number of items in the data structure. If you don't need to associate values, use sets.

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

Both dictionaries and sets use hashing and they use much more memory than only for object storage. According to A.M. Kuchling in Beautiful Code, the implementation tries to keep the hash 2/3 full, so you might waste quite some memory.

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

If you do not add new entries on the fly (which you do, based on your updated question), it might be worthwhile to sort the list and use binary search. This is O(log n), and is likely to be slower for strings, impossible for objects which do not have a natural ordering.

这篇关于Python:用于查找表的列表与字典的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！