Python字典vs列表,哪个更快？

Question

我正在编写一个欧拉问题,我遇到的问题引起了我的好奇心.我有两个代码片段.一个是列表,另一个是字典.

使用清单:

n=100000
num=[]
suma=0
for i in range(n,1,-1):
    tmp=tuple(set([n for n in factors(i)]))
    if len(tmp) != 2: continue
    if tmp not in num:
       num.append(tmp)
           suma+=i

使用词典:

n=100000
num={}
suma=0
for i in range(n,1,-1):
   tmp=tuple(set([n for n in factors(i)]))
   if len(tmp) != 2: continue
   if tmp not in num:
      num[tmp]=i
      suma+=i

我只关心表现.为什么使用字典的第二个示例运行速度非常快,比第一个带列表的示例快.字典的例子运行速度快了近三十倍!

我使用n = 1000000测试了这两个代码,第一个代码在1032秒内运行,第二个代码在3.3秒内运行,,, amazin'!

Answer 1

在Python中,字典键查找的平均时间复杂度为O(1),因为它们是作为哈希表实现的.列表中查找的时间复杂度平均为O(n).在你的代码中,这会在行中产生差异if tmp not in num:,因为在列表的情况下,Python需要搜索整个列表以检测成员资格,而在dict情况下,它不会除了绝对最坏的情况.

有关更多详细信息,请查看TimeComplexity.

Answer 2

如果与速度有关，则不应创建任何列表：

n = 100000
factors = ((frozenset(factors(i)), i) for i in range(2, n+1))
num = {k:v for k,v in factors if len(k)==2}
suma = sum(num.values())

Answer 3

在列表中，代码if tmp not in num:是 O(n) ，而在 dict 中是 O(lgn)。

编辑：字典基于散列，因此它比线性列表搜索快得多。感谢@user2357112 指出这一点。