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

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

我只关心性能。为什么第二个使用字典的例子运行得非常快，比第一个使用列表的例子快。带有字典的示例运行速度快了将近 30 倍!

我使用 n=1000000 测试了这两个代码，第一个代码运行了 1032 秒，第二个代码运行了 3.3 秒，太棒了!

Answer 1

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

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