提高Python中非常大的字典的性能

Question

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

我怀疑问题是,字典在初始化时并不知道密钥的数量而且它没有做一些非常聪明的事情,所以也许存储冲突变得非常频繁而且速度变慢.

如果我知道密钥的数量以及这些密钥究竟是什么,那么在python中是否有任何方法可以使dict(或哈希表)更有效地工作？我依稀记得,如果你知道密钥,你可以巧妙地设计哈希函数(完美哈希？)并预先分配空间.

Answer 1

如果我知道密钥的数量以及这些密钥究竟是什么,那么在python中是否有任何方法可以使dict(或哈希表)更有效地工作？我依稀记得,如果你知道密钥,你可以巧妙地设计哈希函数(完美哈希？)并预先分配空间.

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的变化,以了解如何完成此操作).

通过为字典(例如此字典)设置纯Python模型,可以计算替代插入顺序的加权平均探测数.例如,dict.fromkeys([11100, 22200, 44400, 33300])每次查找插入平均1.75个探针.这比每次查找的平均探测次数高出2.25 dict.fromkeys([33300, 22200, 11100, 44400]).

另一个"技巧"是通过欺骗它增加其大小而不添加新密钥来增加完全填充的字典中的备用:

 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).