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

Question

我正在编写一个Euler问题，我遇到了一个激发我好奇心的问题。我有两段代码。一个是用列表，另一个用字典。

使用列表：

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

我只关心表演。为什么使用字典的第二个示例运行得非常快，比第一个使用列表的示例运行得更快。字典的例子快了将近30倍！

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

Answer 1

我几乎可以肯定，使用字典的“魔法酱”在于字典由键-值对组成。

在列表中，您要处理数组，这意味着for循环必须从列表中的索引0开始，以便循环遍历每个记录。

字典只需在第一个“转到”时找到有问题的键-值对并将其返回，因此速度。。。

基本上，在一组键-值对中测试成员身份要比在整个列表中搜索值快得多。你的单子越大就越慢。。。但情况并非总是如此，有些情况下列表会更快。。。但我相信这可能是你想要的答案

Answer 2

在Python中，字典键查找的平均时间复杂度为O（1），因为它们是作为哈希表实现的。列表中查找的时间复杂度平均为O（n）。在您的代码中，这会对if tmp not in num:行产生影响，因为在列表情况下，Python需要搜索整个列表来检测成员身份，而在dict情况下，它除了绝对最坏的情况外，没有其他情况。

有关详细信息，请查看TimeComplexity。

Answer 3

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

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())