Python 中稀疏 LIL 矩阵中的求和行运算非常慢

Question

我在 Python 中编写了这段代码，它给出了预期的结果，但速度非常慢。瓶颈是 scipy.sparse.lil_matrix 的多行求和。我怎样才能让它快点？

# D1 is a 1.5M x 1.3M sparse matrix, read as scipy.sparse.lil_matrix.
# D2 is a 1.5M x 111 matrix, read as numpy.array
# F1 is a csv file, read using csv.reader

for row in F1:
    user_id = row[0]
    clust = D2[user_id, 110]
    neighbors = D2[ D2[:, 110] == clust][:,1]
    score = np.zeros(1300000)

    for neigh in neighbors:
        score = score + D1 [neigh, :] # the most expensive operation

    toBeWritten = np.argsort(score)[:,::-1].A[0,:]

如果还有其他不是很理想的地方，请告诉我。

Answer 1

首先是一个非常小的矩阵演示

In [523]: idx=np.arange(0,8,2)
In [526]: D=np.arange(24).reshape(8,3)
In [527]: Dll=sparse.lil_matrix(D)

In [528]: D[idx,:].sum(axis=0)
Out[528]: array([36, 40, 44])

In [529]: Dll[idx,:].sum(axis=0)
Out[529]: matrix([[36, 40, 44]], dtype=int32)

In [530]: timeit D[idx,:].sum(axis=0)
100000 loops, best of 3: 17.3 µs per loop

In [531]: timeit Dll[idx,:].sum(axis=0)
1000 loops, best of 3: 1.16 ms per loop

In [532]: score=np.zeros(3)      # your looping version
In [533]: for i in idx:
   .....:     score = score + Dll[i,:]

In [534]: score
Out[534]: matrix([[ 36.,  40.,  44.]])

In [535]: %%timeit
   .....: score=np.zeros(3)
   .....: for i in idx:
    score = score + Dll[i,:]
   .....: 
100 loops, best of 3: 2.76 ms per loop

对于某些操作，csr 格式更快：

In [537]: timeit Dll.tocsr()[idx,:].sum(axis=0)
1000 loops, best of 3: 955 µs per loop

或者如果我预先转换为 csr:

In [538]: Dcsr=Dll.tocsr()

In [539]: timeit Dcsr[idx,:].sum(axis=0)
1000 loops, best of 3: 724 µs per loop

相对于密集来说仍然很慢。

我打算讨论如何使用稀疏矩阵的数据属性来更快地选择行。但是，如果选择这些行的唯一目的是对它们的值求和，我们就不需要这样做了。

稀疏矩阵通过与一列或行矩阵进行矩阵乘积来对行或列求和。我刚刚用同样的答案回答了另一个问题。

Efficiently compute columnwise sum of sparse array where every non-zero element is 1

例如：

In [588]: I=np.asmatrix(np.zeros((1,Dll.shape[0])))    
In [589]: I[:,idx]=1
In [590]: I
Out[590]: matrix([[ 1.,  0.,  1.,  0.,  1.,  0.,  1.,  0.]])
In [591]: I*Dll
Out[591]: matrix([[ 36.,  40.,  44.]])

In [592]: %%timeit 
I=np.asmatrix(np.zeros((1,Dll.shape[0])))
I[:,idx]=1
I*Dll
   .....: 
1000 loops, best of 3: 919 µs per loop

对于这个小矩阵，它对速度没有帮助，但随着 Dcsr 时间下降到 215 µs（这对数学来说更好）。对于大型矩阵，此产品版本将得到改进。

=================

我刚刚在另一个问题中发现，A_csr[[1,1,0,3],:] 行选择实际上是用矩阵乘积完成的。它构建了一个 'extractor' csr 矩阵，看起来像

matrix([[0, 1, 0, 0],
       [0, 1, 0, 0],
       [1, 0, 0, 0],
       [0, 0, 0, 1]])

Python 中稀疏 LIL 矩阵中的求和行运算非常慢

Extremely slow sum row operation in Sparse LIL matrix in Python

python

scipy

sparse-matrix