numpy布尔数组的高效序列化

Question

我有数十万个NumPy布尔数组,我想用它作为字典的键.(这个字典的值是我们观察每个数组的次数.)由于NumPy数组不可清除,因此不能用作键本身.我想尽可能高效地序列化这些数组.

我们有两个效率要求定义,这里:

1. 内存使用效率; 越小越好
2. 计算时间序列化和重构数组的效率; 时间越少越好

我希望在这两个相互竞争的利益之间取得良好的平衡,但是,有效的内存使用对我来说更重要,我愿意牺牲计算时间.

我希望有两个属性可以使这项任务更容易:

1. 我可以保证所有阵列都具有相同的大小和形状
2. 数组是布尔值,这意味着可以简单地将它们表示为1s和0s的序列,即一个位序列

是否有一个高效的Python(2.7,或者,如果可能的话,2.6)数据结构,我可以将它们序列化为(可能是某种字节结构),并且你能提供一个数组和这个结构之间的转换的例子,以及结构回到原来的数组？

请注意,不必存储有关每个索引是否为True或的信息False; 一个简单地存储数组所在索引的结构True就足以重构数组.

一个充分的解决方案适用于一维数组,但一个好的解决方案也适用于二维数组,一个很好的解决方案适用于更高维度的数组.

Answer 1

我有三个建议.我的第一个是赤裸裸被盗AIX.问题是,bitarray对象是可变的,他们的hash上课内容都是独立(即,bitarray b,hash(b) == id(b)).这可以解决,正如aix的答案所示,但事实上你根本不需要bitarrays - 你可以使用tostring!

In [1]: import numpy
In [2]: a = numpy.arange(25).reshape((5, 5))
In [3]: (a > 10).tostring()
Out[3]: '\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\x01
         \x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01'

现在我们有一个不可变的字节串,非常适合用作字典键.为了清楚起见,请注意那些转义不会被转义,因此这样可以在没有bitstring样式序列化的情况下获得.

In [4]: len((a > 10).tostring())
Out[4]: 25

转换回来既简单又快捷:

In [5]: numpy.fromstring((a > 10).tostring(), dtype=bool).reshape(5, 5)
Out[5]: 
array([[False, False, False, False, False],
       [False, False, False, False, False],
       [False,  True,  True,  True,  True],
       [ True,  True,  True,  True,  True],
       [ True,  True,  True,  True,  True]], dtype=bool)
In [6]: %timeit numpy.fromstring((a > 10).tostring(), dtype=bool).reshape(5, 5)
100000 loops, best of 3: 5.75 us per loop

像aix一样,我无法弄清楚如何以简单的方式存储维度信息.如果你必须拥有它,那么你可能不得不忍受更长的钥匙.cPickle虽然看起来是个不错的选择.不过,它的产量仍然是10倍......

In [7]: import cPickle
In [8]: len(cPickle.dumps(a > 10))
Out[8]: 255

它也慢了:

In [9]: cPickle.loads(cPickle.dumps(a > 10))
Out[9]: 
array([[False, False, False, False, False],
       [False, False, False, False, False],
       [False,  True,  True,  True,  True],
       [ True,  True,  True,  True,  True],
       [ True,  True,  True,  True,  True]], dtype=bool)
In [10]: %timeit cPickle.loads(cPickle.dumps(a > 10))
10000 loops, best of 3: 45.8 us per loop

我的第三个建议是使用bitstrings - 特别是bitstring.ConstBitArray.它的精神与aix解决方案类似,但是ConstBitArray它们是不可改变的,所以它们按照你想要的方式hash行事.

In [11]: import bitstring

你必须明确地展平numpy数组:

In [12]: b = bitstring.ConstBitArray((a > 10).flat)
In [13]: b.bin
Out[13]: '0b0000000000011111111111111'

它是不可变的,所以它很好:

In [14]: hash(b)
Out[14]: 12144

转换回数组非常容易,但同样,形状信息也会丢失.

In [15]: numpy.array(b).reshape(5, 5)
Out[15]: 
array([[False, False, False, False, False],
       [False, False, False, False, False],
       [False,  True,  True,  True,  True],
       [ True,  True,  True,  True,  True],
       [ True,  True,  True,  True,  True]], dtype=bool)

它也是迄今为止最慢的选择:

In [16]: %timeit numpy.array(b).reshape(5, 5)
1000 loops, best of 3: 240 us per loop

这是一些更多的信息.我一直在摆弄并测试一些东西,并想出了以下内容.首先,bitarray是这样的速度比bitstring当你使用它的权利:

In [1]: %timeit numpy.array(bitstring.ConstBitArray(a.flat)).reshape(5, 5)
1000 loops, best of 3: 283 us per loop

In [2]: %timeit numpy.array(bitarray.bitarray(a.flat)).reshape(5, 5)
10000 loops, best of 3: 19.9 us per loop

其次,从上面可以看出,所有tostring恶作剧都是不必要的; 你也可以明确地展平numpy数组.但实际上,aix的方法更快,所以这就是现在修改后的数字所基于的.

所以这里是结果的完整纲要.一,定义:

small_nda = numpy.arange(25).reshape(5, 5) > 10
big_nda = numpy.arange(10000).reshape(100, 100) > 5000
small_barray = bitarray.bitarray(small_nda.flat)
big_barray = bitarray.bitarray(big_nda.flat)
small_bstr = bitstring.ConstBitArray(small_nda.flat)
big_bstr = bitstring.ConstBitArray(big_nda.flat)

keysize是的结果sys.getsizeof({small|big}_nda.tostring()),sys.getsizeof({small|big}_barray) + sys.getsizeof({small|big}_barray.tostring())或者sys.getsizeof({small|big}_bstr) + sys.getsizeof({small|big}_bstr.tobytes())-无论后者方法返回打包成字节位串,所以他们应该是各走各的空间的良好预期.

speed是转换{small|big}_nda为键和返回所需的时间,加上将bitarray对象转换为字符串以进行散列所需的时间,如果您缓存字符串,则为一次性成本;如果您为字符串操作,则为每次dict操作的成本不要缓存它.

         small_nda   big_nda   small_barray   big_barray   small_bstr   big_bstr

keysize  64          10040     148            1394         100          1346

speed    2.05 us     3.15 us   3.81 us        96.3 us      277 us       92.2ms  
                             + 161 ns       + 257 ns 

正如你所看到的,bitarray速度非常快,而且aix对子类的建议bitarray应该很好.当然它比它快得多bitstring.很高兴看到你接受了这个答案.

另一方面,我仍然对这种numpy.array.tostring()方法感到满意.它产生的密钥渐近地是8倍大,但是大型阵列的速度仍然很大 - 我的机器上大型阵列的速度大约是30倍.这是一个很好的权衡.不过,在它成为瓶颈之前,可能还不够麻烦.

Answer 2

最初,我建议使用bitarray.但是,正如@senderle正确指出的那样,因为bitarray它是可变的,所以它不能用于直接键入a dict.

这是一个修订的解决方案(仍然基于bitarray内部):

import bitarray

class BoolArray(object):

  # create from an ndarray
  def __init__(self, array):
    ba = bitarray.bitarray()
    ba.pack(array.tostring())
    self.arr = ba.tostring()
    self.shape = array.shape
    self.size = array.size

  # convert back to an ndarray
  def to_array(self):
    ba = bitarray.bitarray()
    ba.fromstring(self.arr)
    ret = np.fromstring(ba.unpack(), dtype=np.bool)[:self.size]
    return ret.reshape(self.shape)

  def __cmp__(self, other):
    return cmp(self.arr, other.arr)

  def __hash__(self):
    return hash(self.arr)

import numpy as np

x = (np.random.random((2,3,2))>0.5)
b1 = BoolArray(x)
b2 = BoolArray(x)
d = {b1: 12}
d[b2] += 1
print d
print b1.to_array()

这适用于Python 2.5+,每个数组元素需要一位,并支持任何形状/维度的数组.

编辑:在最近的版本中,您必须替换ba.tostring和ba.fromstringto ba.tobytes和ba.frombytes(从版本0.4.0开始不推荐使用).