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

问题描述

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

使用列表：

  n = 100000 
 num = [] 
 suma = 0 
 for i in range（n，1，-1）：
 tmp = tuple（set（[n for n in factors （i）]））
如果len（tmp）！= 2：continue 
如果tmp不在num中：
 num.append（tmp）
 suma + = i 
  

使用字典：

<$对于我在范围（n，1，-1）中的i：



$ b $ = tuple（set（[n for n in factors（i）]））
如果len（tmp）！= 2：continue
如果tmp不在num中：
num [tmp] = i
suma + = i

我只关心性能。为什么使用字典的第二个例子运行速度比第一个具有列表的示例快得多。我们使用n = 1000000测试了这两个代码，第一个代码运行在1032秒，第二个代码运行在只需3.3秒,,, amazin'！

解决方案

在Python中，字典键查找的平均时间复杂度为O（1 ），因为它们被实现为哈希表。列表中查找的时间复杂度平均为O（n）。在你的代码中，如果tmp不在num：中，那么在行中有所不同，因为在列表中，Python需要搜索整个列表来检测成员资格，而在dict案例中，除绝对最坏的情况外，它除外。

有关详细信息，请查看。

I was coding a Euler problem, and I ran into question that sparked my curiosity. I have two snippets of code. One is with lists the other uses dictionaries.

using lists:

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

using dictionaries:

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

I am only concerned about performance. Why does the second example using dictionaries run incredibly fast, faster than the first example with lists. the example with dictionaries runs almost thirty-fold faster!

I tested these 2 code using n=1000000, and the first code run in 1032 seconds and the second one run in just 3.3 second,,, amazin'!

解决方案

In Python, the average time complexity of a dictionary key lookup is O(1), since they are implemented as hash tables. The time complexity of lookup in a list is O(n) on average. In your code, this makes a difference in the line if tmp not in num:, since in the list case, Python needs to search through the whole list to detect membership, whereas in the dict case it does not except for the absolute worst case.

For more details, check out TimeComplexity.

这篇关于Python字典vs列表，哪个更快？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！