在Python中稀疏LIL矩阵中极慢的总和操作

我已经用Python写了这段代码，它给出了预期的结果，但是速度极其缓慢。瓶颈是对scipy.sparse.lil_matrix的多行进行求和。我怎样才能让它快速？在Python中稀疏LIL矩阵中极慢的总和操作

# 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,:]

请让我知道是否还有别的东西不是非常优化。

来源

2016-05-14 Sonu Mishra

顺便说一句，“律”是短期的“名单 - 的 - 名单”，而不是“小”（虽然我不喜欢的想法一个可爱的'稀疏矩阵） –

感谢您的信息。编辑标题 –

“邻居”的典型大小是多少？与密集阵列相比，无论格式如何，对稀疏矩阵进行索引操作都比较慢。 – hpaulj

先用一个非常小的矩阵

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

，或者如果我preconvert企业社会责任：

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

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

仍相对密度慢。

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

稀疏矩阵通过做一个列或行矩阵为1的矩阵乘积来计算行或列。我只是用同样的答案回答了另一个问题。

https://stackoverflow.com/a/37120235/901925 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],:]行选择实际上是一个矩阵的产品来完成。它构建了一个“提取”企业社会责任矩阵，看起来像

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

https://stackoverflow.com/a/37245105/901925

来源

2016-05-14 21:06:54 hpaulj

完美！代码现在变得更快了！ –

在Python中稀疏LIL矩阵中极慢的总和操作

回答

相关问题