我在下面演示的简短答案是构建新的稀疏矩阵的成本很高。存在很大的开销,该开销不依赖于行数或特定行中非零元素的数量。
稀疏矩阵的数据表示与稠密数组的数据表示有很大不同。数组将数据存储在一一连续的缓冲区中,并有效地使用shape
and strides
迭代选定的值。这些值加上索引,精确定义了它将在缓冲区中找到的数据。复制那些N
从一个位置到另一个位置的字节是整个操作中相对较小的部分。
稀疏矩阵将数据存储在多个数组(或其他结构)中,包含索引和数据。然后选择一行需要查找相关索引,并使用选定的索引和数据构造一个新的稀疏矩阵。稀疏包中有已编译的代码,但底层代码并不像 numpy 数组那么多。
为了说明这一点,我将制作一个小矩阵,并且不是那么密集,因此我们没有很多空行:
In [259]: A = (sparse.rand(5,5,.4,'csr')*20).floor()
In [260]: A
Out[260]:
<5x5 sparse matrix of type '<class 'numpy.float64'>'
with 10 stored elements in Compressed Sparse Row format>
密集等价物和行副本:
In [262]: Ad=A.A
In [263]: Ad
Out[263]:
array([[ 0., 0., 0., 0., 10.],
[ 0., 0., 0., 0., 0.],
[ 17., 16., 14., 19., 6.],
[ 0., 0., 1., 0., 0.],
[ 14., 0., 9., 0., 0.]])
In [264]: Ad[4,:]
Out[264]: array([ 14., 0., 9., 0., 0.])
In [265]: timeit Ad[4,:].copy()
100000 loops, best of 3: 4.58 µs per loop
矩阵行:
In [266]: A[4,:]
Out[266]:
<1x5 sparse matrix of type '<class 'numpy.float64'>'
with 2 stored elements in Compressed Sparse Row format>
看看这个的数据表示csr
矩阵,3 个一维数组:
In [267]: A.data
Out[267]: array([ 0., 10., 17., 16., 14., 19., 6., 1., 14., 9.])
In [268]: A.indices
Out[268]: array([3, 4, 0, 1, 2, 3, 4, 2, 0, 2], dtype=int32)
In [269]: A.indptr
Out[269]: array([ 0, 2, 2, 7, 8, 10], dtype=int32)
以下是选择行的方式(但在编译代码中):
In [270]: A.indices[A.indptr[4]:A.indptr[5]]
Out[270]: array([0, 2], dtype=int32)
In [271]: A.data[A.indptr[4]:A.indptr[5]]
Out[271]: array([ 14., 9.])
“行”是另一个稀疏矩阵,具有相同类型的数据数组:
In [272]: A[4,:].indptr
Out[272]: array([0, 2])
In [273]: A[4,:].indices
Out[273]: array([0, 2])
In [274]: timeit A[4,:]
是的,稀疏矩阵的计时很慢。我不知道实际选择数据花费了多少时间,以及构建新矩阵花费了多少时间。
10000 loops, best of 3: 145 µs per loop
In [275]: timeit Ad[4,:].copy()
100000 loops, best of 3: 4.56 µs per loop
lil
格式可能更容易理解,因为数据和索引存储在子列表中,每行一个。
In [276]: Al=A.tolil()
In [277]: Al.data
Out[277]: array([[0.0, 10.0], [], [17.0, 16.0, 14.0, 19.0, 6.0], [1.0], [14.0, 9.0]], dtype=object)
In [278]: Al.rows
Out[278]: array([[3, 4], [], [0, 1, 2, 3, 4], [2], [0, 2]], dtype=object)
In [279]: Al[4,:].data
Out[279]: array([[14.0, 9.0]], dtype=object)
In [280]: Al[4,:].rows
Out[280]: array([[0, 2]], dtype=object)
在处理紧密编译的代码时,这样的速度比较是有意义的,其中字节从内存的一部分到另一部分的移动会消耗大量时间。将 Python 和编译代码混合在一起numpy
and scipy
你不能只数数O(n)
运营。
=============================
以下是从中选择一行所需的时间估计A
,以及返回新的稀疏矩阵所需的时间:
只需获取数据:
In [292]: %%timeit
d1=A.data[A.indptr[4]:A.indptr[5]]
i1=A.indices[A.indptr[4]:A.indptr[5]]
.....:
100000 loops, best of 3: 4.92 µs per loop
加上制作矩阵所需的时间:
In [293]: %%timeit
d1=A.data[A.indptr[4]:A.indptr[5]]
i1=A.indices[A.indptr[4]:A.indptr[5]]
sparse.csr_matrix((d1,([0,0],i1)),shape=(1,5))
.....:
1000 loops, best of 3: 445 µs per loop
尝试更简单的coo
matrix
In [294]: %%timeit
d1=A.data[A.indptr[4]:A.indptr[5]]
i1=A.indices[A.indptr[4]:A.indptr[5]]
sparse.coo_matrix((d1,([0,0],i1)),shape=(1,5))
.....:
10000 loops, best of 3: 135 µs per loop