Python 字典迭代器性能 [英] Python dictionary iterator performance
问题描述
在 Python 中使用字典时，此页面表示遍历字典的时间复杂度字典的元素是 O(n)，其中 n 是字典的最大大小.
When working with dictionaries in Python, this page says that the time complexity of iterating through the element of the dictionary is O(n), where n is the largest size the dictionary has been.
但是，我认为没有明显的方法可以遍历哈希表的元素.我可以在遍历哈希表的元素时假设 dict.iteritems() 的良好性能，而不会产生太多开销吗?
However, I don't think that there is an obvious way to iterate through the elements of a hash table. Can I assume good performance of dict.iteritems() when iterating through element of a hash table, without too much overhead?
由于字典在 Python 中被大量使用，我假设这是以某种聪明的方式实现的.不过，我需要确保.
Since dictionaries are used a lot in Python, I assume that this is implemented in some smart way. Still, I need to make sure.
推荐答案
如果你查看 Python 字典源码的注释，我认为相关的有以下几点:
If you look at the notes on Python's dictionary source code, I think the relevant points are the following:
这些方法(迭代和键列表)遍历每个潜在的条目
Those methods (iteration and key listing) loop over every potential entry
作为最大大小的函数(该字典中存储的最大数量的键)，将有多少潜在条目?查看同一个文档中的以下两个部分:
How many potential entries will there be, as a function of largest size (largest number of keys ever stored in that dictionary)? Look at the following two sections in the same document:
PyDict_SetItem 中的最大字典负载.当前设置为 2/3
Maximum dictionary load in PyDict_SetItem. Currently set to 2/3
达到最大负载时的增长率.当前设置为 *2.
Growth rate upon hitting maximum load. Currently set to *2.
这表明字典的稀疏性将在 1/3~2/3 左右(除非增长率设置为 *4，否则为 1/6~2/3).所以基本上你要为每个键检查多达 3 个(如果 *4 则为 6 个)潜在条目.
This would suggest that the sparsity of a dictionary is going to be somewhere around 1/3~2/3 (unless growth rate is set to *4, then it's 1/6~2/3). So basically you're going to be checking upto 3 (or 6 if *4) potential entries for every key.
当然，无论是 3 个条目还是 1000 个条目，它仍然是 O(n)，但 3 似乎是一个非常可接受的常数因子.
Of course, whether it's 3 entries or 1000, it's still O(n) but 3 seems like a pretty acceptable constant factor.
顺便说一下，这里是其余的源代码文档，包括 DictObject 的文档:
Incidentally here are the rest of the source & documentation, including that of the DictObject:
http://svn.python.org/projects/python/trunk/对象/
这篇关于Python 字典迭代器性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
