python - 提高 Python 中超大字典的性能

Question

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

我怀疑问题是，字典在初始化时不知道键的数量并且它没有做一些非常聪明的事情，所以存储冲突可能变得非常频繁并且它变慢了。

如果我知道键的数量以及这些键的确切含义是什么，那么 python 中是否有任何方法可以使字典（或哈希表）更有效地工作？依稀记得，如果知道key，就可以巧妙地设计hash函数（完美hash？），提前分配空间。

Answer 1

如果我知道键的数量以及这些键的确切含义是什么，那么 python 中是否有任何方法可以使字典（或哈希表）更有效地工作？依稀记得，如果知道key，就可以巧妙地设计hash函数（完美hash？），提前分配空间。

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

也就是说，如果密钥总是事先知道，您可以将它们存储在一个集合中，并使用dict.fromkeys()从集合中构建您的字典。该类方法经过优化，可根据设置的大小预先调整字典的大小，并且无需对 __hash__() 进行任何新调用即可填充字典：

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

如果减少冲突是您的目标，您可以对字典中的插入顺序进行实验，以尽量减少堆积。（查看Brent 在 Knuth 的 TAOCP 中对算法 D 的变体，以了解这是如何完成的）。

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

另一个“技巧”是通过欺骗它来增加它的大小而不添加新的 key来增加完全填充字典的备用性：

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