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

Question

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

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

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

Answer 1

If I know the number of keys and exactly what are those keys, is there any way in python to make a dict (or a hashtable) work more efficiently? I vaguely remember that if you know the keys, you can design the hash function smartly (perfect hash?) and allocate the space beforehand.

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

也就是说，如果 key 总是预先知道，您可以将它们存储在 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 以了解这是如何完成的)。

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

另一个“诀窍”是通过将字典欺骗为 increasing its size without adding new 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.

最后，您可以为您的 key 引入您自己的自定义 __hash__()，以消除所有冲突(可能使用完美的哈希生成器，例如 gperf)。