Python字典vs列表，哪个更快？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/38927794/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Python dictionary vs list, which is faster?
提问by froycard
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!
我只关心性能。为什么使用字典的第二个示例运行得非常快，比使用列表的第一个示例快。带有字典的示例运行速度快了近 30 倍！
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'!
我使用 n=1000000 测试了这两个代码，第一个代码在 1032 秒内运行，第二个代码在 3.3 秒内运行，令人惊叹！
回答by Karin
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.
在 Python 中，字典键查找的平均时间复杂度为 O(1)，因为它们是作为哈希表实现的。在列表中查找的时间复杂度平均为 O(n)。在您的代码中，这在 line 中产生了差异if tmp not in num:，因为在列表情况下，Python 需要搜索整个列表以检测成员资格，而在 dict 情况下，除了绝对最坏的情况外，它不会。
For more details, check out TimeComplexity.
有关更多详细信息，请查看TimeComplexity。
回答by Daniel
If it's about speed, you should not create any lists:
如果是关于速度，则不应创建任何列表：
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())
回答by citaret
In a list, the code if tmp not in num:is O(n), while it is O(lgn) in dict.
在列表中，代码if tmp not in num:是 O(n) ，而在 dict 中是 O(lgn)。
Edit: The dict is based on hashing, so it is much quicker than liner list search. Thanks @user2357112 for point this.
编辑： dict 基于散列，因此它比线性列表搜索快得多。感谢@user2357112 指出这一点。
回答by lopezdp
I am almost positive that the "magic sauce" using a dictionary lies in the fact that the dictionary is comprised of key->value pairs.
我几乎肯定使用字典的“魔法酱”在于字典由键-> 值对组成。
in a list, youre dealing with arrays, which means the for loop has to start at index 0 inside of your list in order to loop through every record.
在列表中，您正在处理数组，这意味着 for 循环必须从列表内的索引 0 开始，以便遍历每条记录。
the dictionary just has to find the key->value pair in question on the first 'go-round' and return it, hence the speed...
字典只需要在第一次“循环”中找到有问题的键-> 值对并返回它，因此速度......
basically, testing for membership in a set of key->value pairs is a lot quicker than searching an entire list for a value. the larger your list gets the slower it will be... but this isnt always the case, there are scenarios where a list will be faster... but i believe this may be the answer youre looking for
基本上，测试一组键-> 值对中的成员资格比在整个列表中搜索值要快得多。你的列表越大，它就越慢......但情况并非总是如此，有些情况下列表会更快......但我相信这可能是你正在寻找的答案
