为什么defaultdict(int)的dicts使用了这么多内存？(和其他简单的python性能问题)

Question

我确实理解以我的方式查询defaultdict中不存在的键会将项添加到defaultdict.这就是为什么在性能方面将我的第二个代码片段与我的第一个代码片段进行比较是公平的.

import numpy as num
from collections import defaultdict

topKeys = range(16384)
keys = range(8192)

table = dict((k,defaultdict(int)) for k in topKeys)

dat = num.zeros((16384,8192), dtype="int32")

print "looping begins"
#how much memory should this use? I think it shouldn't use more that a few
#times the memory required to hold (16384*8192) int32's (512 mb), but
#it uses 11 GB!
for k in topKeys:
    for j in keys:
        dat[k,j] = table[k][j]

print "done"

这里发生了什么？此外,与第一个相比,这个类似的脚本需要运行,并且还使用了荒谬的内存量.

topKeys = range(16384)
keys = range(8192)
table = [(j,0) for k in topKeys for j in keys]

我猜python int可能是64位整数,这可能是其中的一部分,但这些相对自然和简单的结构真的会产生如此巨大的开销吗？我想这些脚本显示它们确实如此,所以我的问题是:究竟是什么导致第一个脚本中的高内存使用量以及第二个脚本的长运行时和高内存使用率,是否有任何方法可以避免这些成本？

编辑:64位机器上的Python 2.6.4.

编辑2:我可以看到为什么,在第一次近似中,我的表应该占用3 GB 16384*8192*(12 + 12)字节和6GB的defaultdict负载因子,迫使它保留两倍的空间.然后,内存分配效率低下又消耗了2倍.

所以这是我剩下的问题:有没有办法告诉它以某种方式使用32位整数？

为什么我的第二个代码片段与第一个代码片段相比,FOREVER会运行？第一个花了大约一分钟,我在80分钟后杀了第二个.

Answer 1

Python内部在内部表示为C longs(它实际上比这更复杂),但这并不是你问题的根源.

最大的开销是你使用dicts.(默认情况和dicts在本说明书中大致相同).dicts是使用哈希表实现的,这很好,因为它可以快速查找非常通用的密钥.(当你只需要查找顺序数字键时,它就不那么必要了,因为它们可以通过简单的方式布局到达它们.)

一个字典可以有比它有更多的插槽.假设你有一个dx,其中插槽的数量是3x.这些槽中的每一个都需要空间用于指向键的指针和用作链表的末尾的指针.这是数字的6倍,加上你感兴趣的项目的所有指针.考虑到这些指针中的每一个都是系统上的8个字节,并且在这种情况下你有16384个默认值.作为一个粗略的,手动的看待这个,16384 occurrences * (8192 items/occurance) * 7 (pointers/item) * 8 (bytes/pointer) = 7 GB.这是在我得到你正在存储的实际数字之前(每个唯一的数字本身就是一个Python字典),外部字典,numpy数组,或者Python正在试图优化一些的东西.

你的开销听起来比我怀疑的要高一点,我有兴趣知道11GB是用于整个过程,还是你只为表计算它.无论如何,我确实希望这个默认的数据结构的大小比numpy数组表示大几个数量级.

至于"有没有办法避免这些费用？" 答案是"使用numpy存储大型,固定大小的连续数值数组,而不是dicts!" 您必须更加具体和具体地了解为什么您需要这样的结构来获得有关最佳解决方案的更好建议.