Python:List vs Dict查找表

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

我知道你可以做两件事:

if something in dict_of_stuff:
    pass

和

if something in list_of_stuff:
    pass

我的想法是dict会更快更有效率.

谢谢你的帮助.

编辑1
关于我正在尝试做什么的更多信息. 欧拉问题92.我正在查找表,看看计算出的值是否已经准备就绪.

编辑2
查找效率.

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

1> Torsten Mare..：

---

速度

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

记忆

字典和集合都使用散列,并且它们使用的内存比仅用于对象存储的内存多得多.根据AM Kuchling的漂亮代码,实现尝试保持哈希2/3满,所以你可能会浪费相当多的内存.

如果您不动态添加新条目(根据更新的问题,您可以这样做),可能需要对列表进行排序并使用二进制搜索.这是O(log n),对于字符串来说可能更慢,对于没有自然排序的对象来说是不可能的.

---

是的,但如果内容永远不会改变,那就是一次性操作.二进制搜索是O(log n).

---

@Aerovistae我认为你误读了那个页面上的信息.在列表下,我看到O(n)代表"x in s"(查找).它还显示set和dict查找为O(1)平均情况.

---

这是一个老问题,但我认为_amortized O(1)_可能不适用于非常大的集/ dicts.根据http://wiki.python.org/moin/TimeComplexity的最坏情况是O(n).我想这取决于内部哈希实现在什么时候平均时间偏离O(1)并开始收敛于O(n).您可以通过基于某些_easily discernible_属性(例如第一个数字的值,然后第二个,第三个等等)将全局集划分为更小的部分来帮助查找性能,只要您需要获得最佳设置大小) .

2> nosklo..：

---

dict是一个哈希表,所以找到密钥真的很快.所以在dict和list之间,dict会更快.但是如果你没有要关联的值,那么使用集合会更好.它是一个哈希表,没有"表"部分.

---

编辑:对于你的新问题,是的,一套会更好.只创建2组,一组用于序列以1结尾,另一组用于以89结尾的序列.我已成功使用集合解决了这个问题.

3> recursive..：

---

set()正是你想要的.O(1)查找,小于dict.

4> EriF89..：

---

我做了一些基准测试,事实证明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个元素),那么列表表现相当不错.

---

@andzep,你错了,`-s`选项是设置`timeit`环境,即它不计入总时间.`-s`选项只运行一次.在Python 3.3上,我得到以下结果:gen(范围) - > 0.229 usec,list - > 157 msec,dict - > 0.0806 usec,set - > 0.0807 usec.Set和dict的表现是一样的.然而,Dict初始化比设置要长一些(总时间13.580s v.11.803s)

5> zweiterlinde..：

---

你想要一个字典.

对于Python中的(未排序)列表,"in"操作需要O(n)时间 - 当您有大量数据时不好.另一方面,dict是一个哈希表,所以你可以期待O(1)查找时间.

正如其他人所指出的那样,如果你只有键而不是键/值对,你可以选择一组(一种特殊类型的dict).

有关:

Python wiki:有关Python容器操作的时间复杂性的信息.

SO:Python容器操作时间和内存复杂性

---

对于链表,是 - 但Python中的"列表"是大多数人称之为向量的向量,它们在排序时在O(1)中提供索引访问,在O(log n)中提供查找操作.

6> SilentGhost..：

---

如果数据是唯一的set()将是最有效的,但是两个 - dict(也需要唯一性,oops :)