在python中保存和处理内存中大字典的有效方法

Question

当我做了一点测试时,一个python dict的int => int(不同值)的3000万个项目可以很容易地在我的mac上吃掉> 2G的内存.由于我只使用int到int dict,有没有比使用python dict更好的解决方案？

我需要的一些要求是,

1. 将数百万级的int保存到int项目的内存效率更高
2. 基本的dict方法,比如通过键获取值并迭代所有项
3. 容易序列化为字符串/二进制将是一个加号

更新,4.通过给定的键轻松获取子集,例如d.fromkeys([...])

谢谢.

Answer 1

至少有两种可能性:

阵列

您可以尝试使用两个数组.一个用于键,一个用于值,以便索引(键)==索引(值)

更新2017-01-05:在数组中使用4字节整数.

数组将使用更少的内存.在使用clang编译的python的64位FreeBSD机器上,一个3000万个整数的数组使用大约117 MiB.

这些是我使用的python命令:

Python 2.7.13 (default, Dec 28 2016, 20:51:25) 
[GCC 4.2.1 Compatible FreeBSD Clang 3.8.0 (tags/RELEASE_380/final 262564)] on freebsd11
Type "help", "copyright", "credits" or "license" for more information.
>>> from array import array
>>> a = array('i', xrange(30000000))
>>> a.itemsize
4

导入数组后,ps报告:

USER     PID %CPU %MEM   VSZ  RSS TT  STAT STARTED    TIME COMMAND
 rsmith 81023  0.0  0.2  35480   8100  0  I+   20:35     0:00.03 python (python2.7)

制作阵列后:

USER     PID %CPU %MEM    VSZ    RSS TT  STAT STARTED    TIME COMMAND
rsmith 81023 29.0  3.1 168600 128776  0  S+   20:35     0:04.52 python (python2.7)

居民集大小以1 KiB为单位报告,因此(128776 - 8100)/ 1024 = 117 MiB

使用列表推导,您可以轻松获得密钥满足特定条件的索引列表.然后,您可以使用该列表中的索引来访问相应的值...

numpy的

如果你有numpy可用,使用它更快,有更多的功能,并使用稍微少的RAM:

Python 2.7.5 (default, Jun 10 2013, 19:54:11) 
[GCC 4.2.1 Compatible FreeBSD Clang 3.1 ((branches/release_31 156863))] on freebsd9
Type "help", "copyright", "credits" or "license" for more information.
>>> import numpy as np
>>> a = np.arange(0, 30000000, dtype=np.int32)

来自ps:启动Python后6700 KiB,导入numpy后的17400 KiB和创建阵列后的134824 KiB.这大约是114 MiB.

此外,numpy支持记录数组 ;

Python 2.7.5 (default, Jun 10 2013, 19:54:11) 
[GCC 4.2.1 Compatible FreeBSD Clang 3.1 ((branches/release_31 156863))] on freebsd9
Type "help", "copyright", "credits" or "license" for more information.
>>> import numpy as np
>>> a = np.zeros((10,), dtype=('i4,i4'))
>>> a
array([(0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0),
       (0, 0), (0, 0)], 
      dtype=[('f0', '<i4'), ('f1', '<i4')])
>>> a.dtype.names
('f0', 'f1')
>>> a.dtype.names = ('key', 'value')
>>> a
array([(0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0), (0, 0),
       (0, 0), (0, 0)], 
      dtype=[('key', '<i4'), ('value', '<i4')])
>>> a[3] = (12, 5429)
>>> a
array([(0, 0), (0, 0), (0, 0), (12, 5429), (0, 0), (0, 0), (0, 0), (0, 0),
       (0, 0), (0, 0)], 
      dtype=[('key', '<i4'), ('value', '<i4')])
>>> a[3]['key']
12

在这里,您可以分别访问键和值;

>>> a['key']
array([ 0,  0,  0, 12,  0,  0,  0,  0,  0,  0], dtype=int32)

Answer 2

基于 Judy 数组的解决方案似乎是我应该研究的选项。我仍在寻找一个可以被Python使用的好的实现。稍后会更新。

更新，

最后我在http://code.google.com/p/py-judy/上试验 Judy 数组包装器。那里似乎没有任何文档，但我尝试简单地通过 dir(...) 它的包和对象来找到它的方法，但是它有效。

同样的实验，通过使用 judy.JudyIntObjectMap，它以标准字典的 1/3 消耗了约 986MB。它还提供了 JudyIntSet，在某些特殊情况下，与 JudyIntObjectMap 相比，它不需要引用任何真实的 Python 对象作为值，因此可以节省更多内存。

（如下进一步测试，JudyArray仅使用几MB到几十MB，大约986MB的大部分实际上被Python内存空间中的值对象使用。）

这是一些代码，如果对您有帮助，

>>> import judy
>>> dir(judy)
['JudyIntObjectMap', 'JudyIntSet', '__doc__', '__file__', '__name__', '__package__']
>>> a=judy.JudyIntObjectMap()
>>> dir(a)
['__class__', '__contains__', '__delattr__', '__delitem__', '__doc__', '__format__', '__getattribute__', '__getitem__', '__hash__', '__init__', '__iter__', '__len__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__subclasshook__', '__value_sizeof__', 'by_index', 'clear', 'get', 'iteritems', 'iterkeys', 'itervalues', 'pop']
>>> a[100]=1
>>> a[100]="str"
>>> a["str"]="str"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'non-integer keys not supported'
>>> for i in xrange(30000000):
...     a[i]=i+30000000   #finally eats ~986MB memory
... 

更新，

好的，经过测试，一个 30M int 的 JudyIntSet 。

>>> a=judy.JudyIntSet()
>>> a.add(1111111111111111111111111)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: we only support integers in the range [0, 2**64-1]

它总共仅使用 5.7MB 来存储 30M 顺序 int 数组 [0,30000000)，这可能是由于 JudyArray 的自动压缩所致。高于 709MB 的是 bcz 我使用 range(...) 而不是更合适的 xrange(...) 来生成数据。

所以核心JudyArray的大小为30M int，根本可以忽略不计。

如果有人知道更完整的 Judy Array 包装器实现，请告诉我，因为该包装器仅包装 JudyIntObjectMap 和 JudyIntSet。对于int-int dict，JudyIntObjectMap仍然需要真正的python对象。如果我们只执行 counter_add 并设置值，那么将 int 值存储在 C 空间中而不是使用 python 对象将是一个好主意。希望有人有兴趣创建或介绍一个:)