Python:减少字典的内存使用量

Question

我正在尝试将几个文件加载到内存中.这些文件具有以下3种格式之一:

• string TAB int
• 字符串TAB浮点数
• int TAB float.

实际上,它们是ngram静态文件,以防这有助于解决方案.例如:

i_love TAB 10
love_you TAB 12

目前,我正在做的伪代码是

loadData(file):
     data = {}
     for line in file:
        first, second = line.split('\t')
        data[first] = int(second) #or float(second)

     return data

令我惊讶的是,虽然磁盘中文件的总大小约为21 MB,但当加载到内存中时,该过程需要120 - 180 MB的内存!(整个python应用程序不会将任何其他数据加载到内存中).

只有不到10个文件,大多数文件在大约50-80k行保持稳定,除了一个目前有数百万行的文件.

所以我想要一个技术/数据结构来减少内存消耗:

• 有关压缩技术的建议吗？
• 如果我仍然使用dict,有没有办法减少内存？是否可以像Java dict中那样设置"加载因子"？
• 如果你有其他一些数据结构,我也愿意交换一些速度来减少内存.然而,这是一个时间敏感的应用程序,所以一旦用户输入他们的查询,我认为花费超过几秒钟来返回结果是不太合理的.关于这一点,我仍然惊讶于谷歌如何设法如此快速地进行谷歌翻译:他们必须使用大量技术+大量服务器的力量？

非常感谢你.我期待着你的建议.

Answer 1

我无法提供有助于改善内存占用的完整策略,但我相信它可能有助于分析究竟是什么占据了这么多内存.

如果你看一下字典的Python实现(这是一个相对直接的哈希表实现),以及内置字符串和整数数据类型的实现,例如这里(特别是object.h,tobject) .h,stringobject.h和dictobject.h,以及../Objects中相应的*.c文件),您可以准确计算出预期的空间要求:

1. 一个整数是一个固定大小的对象,即,它包含一个引用计数,一个类型的指针和实际整数,在总通常至少12个字节在32位的系统上,并且24个字节在64位的系统上,没有考虑到额外的空间可能失去对齐.

2. 甲字符串对象是可变大小的,这意味着它包含

   • 引用计数
   • 类型指针
   • 尺寸信息
   • 懒惰计算的哈希码的空间
   • 状态信息(例如用于实习字符串)
   • 指向动态内容的指针

   总共32位上至少24字节或64位上60字节,不包括字符串本身的空间.

3. 该词典本身由多个动叶的,各自含有

   • 当前存储的对象的哈希码(由于使用了冲突解决策略,无法从桶的位置预测)
   • 指向密钥对象的指针
   • 指向值对象的指针

   在32位上总共至少12个字节,在64位上总共24个字节.

4. 该字典以8个空桶开始,并在达到其容量时通过将条目数加倍来调整大小.

我使用46,461个唯一字符串(337,670字节串联字符串大小)列表进行了测试,每个字符串都与一个整数相关联 - 类似于您在32位计算机上的设置.根据上面的计算,我预计最小内存占用量为

• 46,461*(24 + 12)字节= 1.6 MB的字符串/整数组合
• 337,670 = 0.3 MB的字符串内容
• 65,536*12字节= 1.6 MB的散列桶(调整大小13次后)

总共2.65 MB.(对于64位系统,相应的计算结果为5.5 MB.)

在运行Python解释器空闲时,根据ps-tool的占用空间为4.6 MB.因此,创建字典后的总预期内存消耗约为4.6 + 2.65 = 7.25 MB.我测试中的真实内存占用量(根据ps)为7.6 MB.我想额外的ca. 通过Python的内存分配策略(用于内存竞技场等)生成的开销消耗0.35 MB

当然,很多人现在会指出我ps用来衡量内存占用量是不准确的,而且我对32位和64位系统上指针类型和整数大小的假设可能在许多特定系统上都是错误的.理所当然的.

但是,我认为,关键结论是:

• Python的字典实现消耗一个令人惊讶的小的内存量
• 但是许多int和(特别是)字符串对象占用的空间,用于引用计数,预先计算的哈希码等,比你最初想的要多.
• 有几乎没有办法避免的内存开销,只要您使用Python,并希望表示为单个对象的字符串和整数-至少我看不出怎么能作到
• 寻找(或实现自己)一个Python-C扩展可能是值得的,该扩展实现了一个哈希,它将键和值存储为C指针(而不是Python对象).我不知道这是否存在; 但我相信它可以做到并且可以将内存占用减少一半以上.

Answer 2

1)内存中的SQLite听起来像是一个很好的解决方案,它可以让你在加载后更容易地查询你的数据,这是一种乐趣

sqlite3.connect( ':存储器:')

2)你可能想要一个命名元组 - 我很确定它们比字典更轻,你可以使用点符号访问属性(无论如何我都有美学偏好).

http://docs.python.org/dev/library/collections

3)你可能想看看Redis:https: //github.com/andymccurdy/redis-py

它很快,可以让你轻松地坚持下去,这意味着你不必在每次想要使用它时加载整个集合.

4)trie听起来像个好主意,但在你的工作结束时增加了一些理论上的复杂性.您可以使用Redis来实现和存储它,这将进一步提高您的速度.

但总的来说,命名元组可能就是这里的诀窍.

Answer 3

在磁盘中你只有字符串,当加载到Python时,解释器必须为每个字符串和每个字典创建一个完整的结构,除了字符串本身.

没有办法减少dicts使用的内存,但还有其他方法可以解决这个问题.如果你愿意为内存换取一些速度,你应该考虑从SQLite文件中存储和查询字符串,而不是将所有内容加载到内存中的字典.

Answer 4

听起来像 Trie ( http://en.m.wikipedia.org/wiki/Trie ) 数据结构可能更适合您对内存效率的渴望。

更新：Python dict 的内存效率已成为一个问题，尽管考虑到第三方库的可用性，它被标准库拒绝。请参阅： http: //bugs.python.org/issue9520