PythonのSparse 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に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