存储和检索大型稀疏矩阵

Question

我有一个相当大的稀疏矩阵,我估计,当加载到内存中时会占用1Gb.

我不需要一直访问整个矩阵,因此某种内存映射可以工作; 然而,似乎不可能使用numpy或spicy(我熟悉的工具)来记忆映射稀疏矩阵.

它可以很容易地融入内存,但如果我每次运行程序时都必须加载它,那将会非常痛苦.也许某种方式可以在运行之间保持内存？

所以,你有什么建议:1.找到一种记忆映射稀疏矩阵的方法; 2.每次只需将整个思想加载到内存中.

Answer 1

以下可能是一般概念,但您必须弄清楚很多细节......您应该首先熟悉CSR格式,其中数组的所有信息都存储在3个数组中,两个长度非零条目的数量,一个长度为行数加一:

>>> import scipy.sparse as sps
>>> a = sps.rand(10, 10, density=0.05, format='csr')
>>> a.toarray()
array([[ 0.        ,  0.46531486,  0.03849468,  0.51743202,  0.        ],
       [ 0.        ,  0.67028033,  0.        ,  0.        ,  0.        ],
       [ 0.        ,  0.        ,  0.        ,  0.        ,  0.        ],
       [ 0.        ,  0.        ,  0.        ,  0.        ,  0.9967058 ],
       [ 0.        ,  0.        ,  0.        ,  0.        ,  0.        ]])
>>> a.data
array([ 0.46531486,  0.03849468,  0.51743202,  0.67028033,  0.9967058 ])
>>> a.indices
array([1, 2, 3, 1, 4])
>>> a.indptr
array([0, 3, 4, 4, 5, 5])

所以a.data有非零项,以行优先顺序,a.indices有诺诺的非零项的相应列的索引,并a.indptr有开始索引到其他两个阵列,其中的每一行数据开始,如a.indptr[3] = 4和a.indptr[3+1] = 5,所以非零项在第四行是a.data[4:5],和他们的列索引a.indices[4:5].

因此,您可以将这三个数组存储在磁盘中,并将其作为memmaps进行访问,然后您可以按如下方式检索行m到n:

ip = indptr[m:n+1].copy()
d = data[ip[0]:ip[-1]]
i = indices[ip[0]:ip[-1]]
ip -= ip[0]
rows = sps.csr_matrix((d, i, ip))

作为概念的一般证明:

>>> c = sps.rand(1000, 10, density=0.5, format='csr')
>>> ip = c.indptr[20:25+1].copy()
>>> d = c.data[ip[0]:ip[-1]]
>>> i = c.indices[ip[0]:ip[-1]]
>>> ip -= ip[0]
>>> rows = sps.csr_matrix((d, i, ip))
>>> rows.toarray()
array([[ 0.        ,  0.        ,  0.        ,  0.        ,  0.55683501,
         0.61426248,  0.        ,  0.        ,  0.        ,  0.        ],
       [ 0.        ,  0.        ,  0.67789204,  0.        ,  0.71821363,
         0.01409666,  0.        ,  0.        ,  0.58965142,  0.        ],
       [ 0.        ,  0.        ,  0.        ,  0.1575835 ,  0.08172986,
         0.41741147,  0.72044269,  0.        ,  0.72148343,  0.        ],
       [ 0.        ,  0.73040998,  0.81507086,  0.13405909,  0.        ,
         0.        ,  0.82930945,  0.71799358,  0.8813616 ,  0.51874795],
       [ 0.43353831,  0.00658204,  0.        ,  0.        ,  0.        ,
         0.10863725,  0.        ,  0.        ,  0.        ,  0.57231074]])
>>> c[20:25].toarray()
array([[ 0.        ,  0.        ,  0.        ,  0.        ,  0.55683501,
         0.61426248,  0.        ,  0.        ,  0.        ,  0.        ],
       [ 0.        ,  0.        ,  0.67789204,  0.        ,  0.71821363,
         0.01409666,  0.        ,  0.        ,  0.58965142,  0.        ],
       [ 0.        ,  0.        ,  0.        ,  0.1575835 ,  0.08172986,
         0.41741147,  0.72044269,  0.        ,  0.72148343,  0.        ],
       [ 0.        ,  0.73040998,  0.81507086,  0.13405909,  0.        ,
         0.        ,  0.82930945,  0.71799358,  0.8813616 ,  0.51874795],
       [ 0.43353831,  0.00658204,  0.        ,  0.        ,  0.        ,
         0.10863725,  0.        ,  0.        ,  0.        ,  0.57231074]])

Answer 2

Scipy 支持不同类型的稀疏矩阵。但是您必须编写一个例程才能将其读入内存。您应该使用哪种类型取决于您想用它做什么。

如果您的矩阵非常稀疏，您可以使用struct(row, column, value)模块将元组作为二进制数据保存到磁盘。假设可移植性不是问题，这将使磁盘上的数据更小并且更容易加载。

然后您可以像这样读取数据：

import struct
from functools import partial

fmt = 'IId'
size = struct.calcsize(fmt)

with open('sparse.dat', 'rb') as infile:
    f = partial(infile.read, size)
    for chunk in iter(f, ''):
        row, col, value = struct.unpack(fmt, chunk)
        # put it in your matrix here