非常に大きなスパース行列の高速構築

Question

各行が列に対応する非ゼロ要素を1つしか持たず、各列の要素数がゼロでない（平均して）等しい非常に大きなスパース行列の構成を高速化する方法はありますか？

IサイズN1行列N2の巨大な（スパース）行列を有する、各行がランダムnumpy.random.choice(numpy.arange(N2),size=N2,replace=False)によって交換することなく選択される唯一の非ゼロ要素が含まサイズ1e8行列5e4の例えば言います。

私が知る限り、私が行列を構築する唯一の方法は、ループN1回でnumpy.random.choice()を実行することです。

それでも

import numpy as np 
from scipy import weave 
from scipy.weave import converters 
import scipy.sparse as sparse # Cython import 

def weave_sparse(N1,N2,w): 
    conn_matrix = sparse.dok_matrix((N1,N2)) 
    fac = lambda N : np.random.choice(np.arange(N), size=N, replace=False)[0] 
    code = """ 
      int i; 
      py::tuple arg(1); 
      arg[0] = N2; 
      for(i=0;i<N1;i++) conn_matrix[i,(int) fac.call(arg)] = w; 
      """ 
    weave.inline(code,['conn_matrix','N1','N2', 'w', 'fac'], 
       compiler='gcc',extra_compile_args=['-std=c++11 -Ofast'],force=0) 
    return conn_matrix 

を、N1は1e6に近づいて、コードを超えて、それが完了に時間がかかりすぎてのために：N1として私はscipy.weaveを使用しています物事をスピードアップするために、非常に大きいです。私はスパース行列を構築するためにはるかに効率的な方法があると思う。人間が読める時間にマトリックスをスピードアップして構築するための他の戦略

Answer 1

これを効率的に行うには、weaveは必要ありません。ここにあなたのために働くべき例があります。私はN1とN2の小さな値を使って結果を簡単に調べました。私はcsr_matrixも使用しましたが、scipyの疎な行列型はほとんど変更を加えずに動作するはずです。

In [50]: from scipy.sparse import csr_matrix 

N1、N2アレイw基本的に入力されています。 wは、長さがN1の配列です。各行に入れる値を保持します。ここでは、私が今作成1.

In [51]: N1 = 15 

In [52]: N2 = 12 

In [53]: w = np.empty(N1, dtype=int) 

In [54]: w[:] = 1 

でwを埋めるcsr_matrix：

In [55]: rows = np.arange(N1) 

In [56]: cols = np.random.randint(0, N2, size=N1) 

In [57]: conn_matrix = csr_matrix((w, (rows, cols)), shape=(N1, N2), dtype=int) 

.A属性は.toarray()方法のためだけのショートカットです。

In [58]: conn_matrix.A 
Out[58]: 
array([[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0], 
     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], 
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]], dtype=int64) 

Answer 2

だから、ここの速度の問題が非常に大きい疎行列を構築する効率的な問題として書き直すことができます：それは通常のnumpyの配列を返します。 @Warrenは、すべてN1要素の上にあるnp.random.choice(np.arange(N2),size=N2,replace=False)がまだランダムな順列の問題であると指摘しています。だから、いくつかの考え、上記最終的には、以下のことができための簡潔な実装後：

N1 = 10000000 #1e8 
N2 = 5000 
rows = np.arange(N1) 
cols = (np.floor(np.random.permutation(N1)/float(N1)*N2)).astype(int) # Randomly pick N1 objects and assign to N2 categories in almost equal proportion 
w = np.ones(N1) 
conn_matrix = sparse.csr_matrix((w, (rows, cols)), shape=(N1, N2), dtype=int)