Python中大型字典的性能提升

Question

我发现如果我在开始时初始化一个空字典，然后在for循环中向字典添加元素（大约110,000个键，每个键的值都是一个列表，在循环中也在增长），速度会随着for循环的进行而下降。

我怀疑问题在于，字典在初始化时不知道键的数量并且没有做一些很聪明的事情，因此存储冲突变得相当频繁，并且会减慢速度。

如果我知道键的数量和确切的键是什么，Python中是否有办法使字典（或哈希表）更有效地工作？我模糊地记得，如果你知道键，你可以聪明地设计哈希函数（完美哈希？）并预先分配空间。

- szli

---

通过减少哈希冲突，可以提高Hashtable的性能。这可以通过预分配最优数量的桶或从一组已知键创建完美的哈希函数来实现。不幸的是，Python字典不提供对哈希表内部的低级访问，因此无法以此方式进行微调。 - Charles Salvia

这个字典需要多少内存？（你说列表的大小在增加吗？）可以使用pympler来测量。如果大小导致Python命中交换内存，你可能会看到明显的减速。 - unutbu

Answer 1

如果我知道键的数量和确切的键是什么，有没有办法在Python中使字典（或哈希表）更有效率？我依稀记得，如果你知道键，可以设计一个聪明的哈希函数（完美哈希？）并预先分配空间。

Python不提供预调整大小选项以加速字典的“增长阶段”，也没有直接控制字典中的“放置”。

话虽如此，如果键始终事先已知，您可以将它们存储在set中，并使用dict.fromkeys()从集合构建字典。该classmethod已经优化为根据集合大小预调整字典的大小，并且可以在不调用__hash __（）的情况下填充字典：

>>> keys = {'red', 'green', 'blue', 'yellow', 'orange', 'pink', 'black'}
>>> d = dict.fromkeys(keys)  # dict is pre-sized to 32 empty slots

如果减少冲突是您的目标，您可以在字典中运行插入顺序实验以最小化堆积。(请参考Knuth的TAOCP中Brent算法D的变体，了解如何执行此操作)。

通过为字典（例如这个）提供纯Python模型进行检测，可以计算替代插入顺序的加权平均探查次数。例如，插入dict.fromkeys([11100, 22200, 44400, 33300])每次查找的平均探查次数为1.75。这比dict.fromkeys([33300, 22200, 11100, 44400])的平均2.25次要好。

另一个“技巧”是通过欺骗完全填充的词典，增加其稀疏性，使其增加大小而不添加新键：

 d = dict.fromkeys(['red', 'green', 'blue', 'yellow', 'orange'])
 d.update(dict(d))     # This makes room for additional keys
                       # and makes the set collision-free.

最后，你可以为你的键引入自定义的 __hash__()，旨在消除所有冲突（可能使用完美哈希生成器，如 gperf）。

- Raymond Hettinger

---

真是的，这篇帖子为什么没得到更多点赞呢？我猜Ray已经有足够的积分了：） - David Sanders