Python：List vs dict用于查找表

Question

Python：List vs dict用于查找表我有大约1000万个值，我需要放入某种类型的查找表中，所以我想知道哪一个会更有效列单或迪克特?我知道你可以为两个人做这样的事：if something in dict_of_stuff:     pass和if something in list_of_stuff:     pass我的想法是这样会更快更有效率。谢谢你的帮助。

Answer 1

DICT是一个哈希表，所以找到键是非常快的。所以在DIT和LIST之间，DIT会更快。但是，如果您没有一个可以关联的值，那么使用一个集合就更好了。它是一个哈希表，没有“表”部分。

---

编辑：对于你的新问题，是的，一套会更好。只需创建2组，一组用于结束于1的序列，另一组用于结束于89的序列。我用集合成功地解决了这个问题。

Answer 2

我做了一些基准测试，结果发现DIT比清单和大型数据集的设置都要快，在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'

  10000000个循环，每个循环3：0.0759 usc。

• python -mtimeit -s 'from sets import Set; d=Set(range(10**7))' '5*10**6 in d'

  1000000个循环，每个循环3：0.262 usc。

如您所见，DIT比List快得多，比SET快3倍。但是，在某些应用程序中，您可能仍然希望为它的美丽选择SET。如果数据集真的很小(<1000个元素)，列表就会执行得很好。

Answer 3

速度

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

记忆

字典和集合都使用散列，它们使用的内存比仅用于对象存储的内存多得多。根据上午库奇林美丽代码，该实现试图使散列2/3保持满，因此您可能会浪费相当多的内存。

如果您不动态添加新条目(基于更新的问题，您可以这样做)，那么对列表进行排序并使用二进制搜索可能是值得的。这是O(Logn)，对于字符串来说可能更慢，对于没有自然排序的对象来说是不可能的。