提高Python中超大字典的性能

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

我怀疑的问题是，在字典不知道在初始时间按键的数量，它不是做一些很聪明的，所以也许存储的碰撞变得相当频繁，它会减慢。

如果我知道按键的数量和什么是那些键，有在python没有办法让一个字典（或哈希表）更有效地工作？我隐约记得，如果你知道密钥，你可以巧妙地设计哈希函数（完美哈希？）并预先分配空间。

2013-04-27 szli

可以通过消除/减少碰撞来提高散列表的性能。这可以通过预先分配最佳数量的桶或通过一组已知密钥创建完美的散列函数来实现。不幸的是，Python字典不能让你对哈希表的内部进行低级访问，所以你不能以这种方式对它们进行微调。 – 2013-04-27 21:34:17

这个字典需要多少内存？（你是否说这些列表的大小在增加？）它可以用[pympler]（http://packages.python.org/Pympler/）来衡量。如果大小导致Python触发交换内存，您可能会看到戏剧性的减速。 – unutbu 2013-04-27 22:13:09

如果我知道按键的数量和什么是那些键，有在python没有办法让一个字典（或哈希表）的工作更高效？我隐约记得，如果你知道密钥，你可以巧妙地设计哈希函数（完美哈希？），并预先分配空间。

Python不公开预选选项以加快词典的“成长阶段”，也不提供任何直接控制词典中的“位置”的操作。

也就是说，如果密钥总是事先知道，那么可以将它们存储在set中，并使用dict.fromkeys()从集合中构建您的字典。那类方法是optimized to pre-size the dictionary based on the set size，它可以填充字典，没有任何新的调用__hash __（）：

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

如果减少碰撞是你的目标，你可以在字典中的插入，以尽量减少堆积的运行试验。（在Knuth的TAOCP中查看Brent's variation on Algorithm D以了解这是如何完成的）。

通过插对于字典一个纯Python模型（如this one），有可能进行计数探针的加权平均数的替代广告订单。例如，插入dict.fromkeys([11100, 22200, 44400, 33300])平均每个查找1.75个探针。这比dict.fromkeys([33300, 22200, 11100, 44400])每次查找的平均探测次数要高出2.25次。

另一个“绝招”是愚弄它来增加spareness在完全填充的字典到increasing its size without adding new key S：

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）。

来源

2013-04-27 21:56:13

Sheesh，为什么这没有得到更多的票？我猜雷雷已经有足够的分数:)。 – 2014-09-17 16:38:39

提高Python中超大字典的性能

回答

相关问题