改善Python中超大型字典的性能

Question

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

我怀疑问题在于，字典在初始化时不知道键的数量，并且执行的操作也不是很聪明，因此存储冲突可能会变得很频繁并且会减慢速度。

如果我知道键的数量以及这些键的确切含义，python中有什么方法可以使字典（或哈希表）更有效地工作？我隐约记得，如果您知道键，则可以巧妙地设计哈希函数（完美的哈希值？）并预先分配空间。

Answer 1

如果我知道键的数量以及这些键的确切含义，python中有什么方法可以使字典（或哈希表）更有效地工作？我隐约记得，如果您知道键，则可以巧妙地设计哈希函数（完美的哈希值？）并预先分配空间。

Python没有公开预定义大小的选项来加快字典的“成长阶段”，也没有提供对字典中“放置”的任何直接控制。

也就是说，如果始终事先知道键，则可以将它们存储在
集合中，
并使用
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的变化，以了解如何完成此操作）。

通过为字典（例如this）使用纯Python模型，可以计算替代插入顺序的探针的加权平均数。例如，dict.fromkeys([11100, 22200,44400, 33300])每次查询平均插入1.75个探针。超过了每次查找的2.25次平均探查dict.fromkeys([33300, 22200,11100, 44400])。

另一个“窍门”是通过愚弄它以增加其大小而不增加新的键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 ）。