提高 Python 中超大型字典的性能

小开

最佳答案

如果我知道钥匙的数量以及具体是什么钥匙在 python 中任何方法都可以使一个 dict (或 hashtable)工作得更好有效率? 我依稀记得，如果你知道钥匙，你就可以巧妙地设计哈希函数(完美的哈希?)并分配空间。

Python 没有提供一个预调整大小的选项来加速字典的“增长阶段”，也没有提供对字典中“位置”的任何直接控制。

也就是说，如果总是提前知道这些键，那么可以将它们存储在 < em > set 中，并使用 < em > dict.fromkeys () 从该集合构建字典。这个类方法是根据设置的大小预先调整字典的大小，它不需要对 _ _ hash _ _ ()进行任何新的调用就可以填充字典:

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

如果您的目标是减少冲突，那么您可以在字典中对插入顺序进行实验，以尽量减少堆积。(看看 Knuth 的 TAOCP 中的布伦特变异算法 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 _ _ () ，目标是消除所有冲突(可能使用完美的散列生成器，如 < em > gperf )。