計算を高速化する方法は？

Question

私は疎な行列を埋めるために100万回* 1百万回の計算を計算する必要があります。しかし、行ごとに行列を埋めるためにループを使うと、ちょうど100 * 100の計算を行うのに6分かかります。タスクは解決されません。プロセスをスピードアップする方法はありますか？

import numpy as np 
from scipy.sparse import lil_matrix 
import pandas as pd 
tp = pd.read_csv('F:\\SogouDownload\\train.csv', iterator=True, chunksize=1000) 
data = pd.concat(tp, ignore_index=True) 
matrix=lil_matrix((1862220,1862220)) 
for i in range(1,1862220): 
    for j in range(1,1862220): 
     matrix[i-1,j-1]=np.sum(data[data['source_node']==i].destination_node.isin(data[data['source_node']==j].destination_node)) 

Answer 1

、これはどちらか恐ろしく遅いではありませんスパース行列を構築する最速の方法ではないが、少なくともlil割り当てステップではない：

In [204]: N=100 
In [205]: M=sparse.lil_matrix((N,N)) 
In [206]: for i in range(N): 
    ...:  for j in range(N): 
    ...:   M[i,j]=(i==j) 
In [207]: M 
Out[207]: 
<100x100 sparse matrix of type '<class 'numpy.float64'>' 
    with 100 stored elements in LInked List format> 

それはMにちょうどゼロ以外の値を保存しました。私はループ中の遅延をほとんど見かけませんでした。

だから私の推測では、ほとんどの時間はpanadasインデックス式に費やされていることである。

np.sum(data[data['source_node']==i].destination_node.isin(data[data['source_node']==j].destination_node)) 

の変換データは、多くの場合、スパース行列が頻繁に来るcoocuranceカウントに、テキスト形式。それらは学習コード、パターン検索などで使用されます。scikit-learnがよく使用されます。またtensorflow。 = 1000

In [212]: %%timeit 
    ...: M=sparse.lil_matrix((N,N)) 
    ...: for i in range(N): 
    ...:  for j in range(N): 
    ...:   M[i,j]=(i==j) 
    ...: 
1 loop, best of 3: 7.31 s per loop 

Nについて

---

を反復高密度アレイにこれらの値を代入すると、我々は終わりにスパースへの変換を含む場合であっても、高速です。

In [213]: %%timeit 
    ...: M=np.zeros((N,N)) 
    ...: for i in range(N): 
    ...:  for j in range(N): 
    ...:   M[i,j]=(i==j) 
    ...: 
1 loop, best of 3: 353 ms per loop 

In [214]: %%timeit 
    ...: M=np.zeros((N,N)) 
    ...: for i in range(N): 
    ...:  for j in range(N): 
    ...:   M[i,j]=(i==j) 
    ...: M = sparse.lil_matrix(M) 
    ...: 
1 loop, best of 3: 353 ms per loop 

非常に大きなケースでは、その中間の高密度アレイを作成すると、メモリの問題が発生する可能性があります。

Answer 2

ここで使用する手法は、疎マトリックス乗算です。しかし、そのテクニックでは、まずソースノードと宛先ノードをマッピングするバイナリ行列が必要です（ノードラベルは非ゼロエントリのインデックスになります）。

from scipy.sparse import csr_matrix 

I = data['source_node'] - 1 
J = data['destination_node'] - 1 
values = np.ones(len(data), int) 
shape = (np.max(I) + 1, np.max(J) + 1) 
mapping = csr_matrix((values, (I, J)), shape) 

技術自体は、単にその転置この行列の行列乗算である（また、this question参照）。

cooccurrence = mapping.dot(mapping.T) 

唯一の潜在的な問題は、結果の行列はスパースではないかもしれないということであり、すべてのあなたのRAMを消費します。