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 测试了这 2 个代码，第一个代码运行了 1032 秒，第二个代码运行了 3.3 秒，，，太棒了！

Answer 1

在Python中，字典键查找的平均时间复杂度是O(1)，因为它们是作为哈希表实现的。列表中查找的时间复杂度平均为 O(n)。在您的代码中，这会在

if tmp not in num:

行中产生影响，因为在列表情况下，Python 需要搜索整个列表来检测成员资格，而在 dict 情况下，除了绝对最坏的情况之外，它不会这样做。

有关更多详细信息，请查看时间复杂度。

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 指出这一点。

Answer 4

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

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

字典只需在第一次“循环”时找到相关的键->值对并返回它，因此速度...

基本上，测试一组键->值对中的成员资格比在整个列表中搜索值要快得多。您的列表越大，速度就越慢...但情况并非总是如此，在某些情况下列表会更快...但我相信这可能是您正在寻找的答案

Answer 5

python 列表是索引列表。基于索引的查找比常规链表快得多。甚至上面关于时间复杂度的链接也说列表查找是 O(1)。