在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矩陣中極慢的總和操作

回答

相關問題