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

我正在编写一个欧拉问题，我碰到了问题，引发了我的好奇心。我有两个代码片段。一个是列出其他使用字典。Python字典vs列表，哪个更快？

使用列表：

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'！

来源

2016-08-12 froycard

你的代码中直接从你的IDE粘贴，突出了这一切，然后按Ctrl + K – Cody

@Cody问题是不是与缩进，但事实上他将代码块放在列表中。我已更正待处理编辑中的格式。 – Tagc

@Tagc我没有看到代码，所以我只是猜测。那么好的修复。 – Cody

在一个列表中，代码if tmp not in num:是O（n） ~~，而它在代码~~ 中是O（lgn）。

编辑：该词典是基于散列，所以它比直线列表搜索快得多。感谢@ user2357112指出这一点。

来源

2016-08-12 23:54:52 citaret

所以，是这样吗？如果是这样（我想知道为什么），这诱使我使用字典而不是列表，为表现有关我只是想找到一种更好的方式来加快我的编码，这只是吹了我的脑海... – froycard

这是错误的。字典基于散列，而不是比较。他们的查找性能不是O（log（n））。 – user2357112

@ user2357112：是的，你是对的。 – citaret

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

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

字典只是要找到第一个“旋转木马”有问题的键 - >值对并返回，因此速度...

基本上，一组关键的测试会员 - >值对比搜索整个列表更快。你的列表越大，它会变得越慢......但这并不总是这种情况，有些情况下列表会更快......但我相信这可能是你正在寻找的答案

来源

2016-08-13 00:04:37 lopezdp

谢谢......我想我需要继续研究这个问题,,,我第一次碰到这个......我想知道我在哪里可以找到关于这个特定情况的更多信息？ – froycard

上周我在想这件事情，并且保存了这个链接。我想这是为你发芽：https://wiki.python.org/moin/PythonSpeed – lopezdp

在Python中，字典密钥查找的平均时间复杂度为O（1），因为它们被实现为散列表。查找列表的时间复杂度平均为O（n）。在你的代码中，这在if tmp not in num:行中有所不同，因为在列表案例中，Python需要搜索整个列表来检测成员资格，而在dict情况下，除了绝对最坏的情况外，它不会。

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

来源

2016-08-13 00:10:35 Karin

非常感谢，您的评论刚刚指出我正确的方向，那些TimeComplexity表派上用场，必须考虑到当我尝试在我的代码中加快速度时。再次感谢 – froycard

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

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

来源

2016-08-13 06:14:26 Daniel

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

回答

相关问题