隣接行列の最適化計算

Question

Xは、同じサイズ（500要素）のビットベクトル（つまり、各行は500要素のベクトル）の100000ビットを含むテキストファイルです。私は以下のコードを使用して隣接行列（100000×100000）を生成していますが、最適化されず、非常に時間がかかりません。どうすればそれを改善できますか？

import numpy as np 
import scipy.spatial.distance 


readFrom = "vector.txt" 
fout = open("adjacencymatrix.txt","a") 

X = np.genfromtxt(readFrom, dtype=None) 

for outer in range(0,100000): 
    for inner in range(0,100000): 
     dis = scipy.spatial.distance.euclidean(X[outer],X[inner]) 
     tmp += str(dis)+" " 
    tmp += "\n"   
    fout.write(tmp) 
fout.close() 

ありがとうございます。

Answer 1

編集：完全な質問をよく理解した上で書き直してください。データのサイズなどを考えると、これは難しいです。私はこれまでのところ、以下でスピードアップで私の最高の結果を得た：

import time 
import numpy as np 
from scipy import spatial 
import multiprocessing as mp 

pool = mp.Pool(4) 

test_data = np.random.random(100000*500).reshape([100000,500]) 

outfile = open('/tmp/test.out','w') 

def split(data,size): 
    for i in xrange(0, len(data), size): 
     yield data[i:i+size] 

def distance(vecs): 
    return spatial.distance.cdist(vecs,test_data) 

chunks = list(split(test_data,100)) 
for chunk in chunks: 
    t0 = time.time() 
    distances = spatial.distance.cdist(chunk,test_data) 
    outfile.write(' '.join([str(x) for x in distances])) 
    print 'estimated: %.2f secs'%((time.time()-t0)*len(chunks)) 

は、だから私は、メモリのオーバーヘッド対データセットの各チャンクの大きさのバランスを取るしようとしました。これで、私は6,600秒の終わりまで、または約110分になった。マルチプロセッシングプールを使用して並列化できるかどうかもわかり始めました。私の戦略は、各チャンクを非同期的に処理して別のテキストファイルに保存し、その後にファイルを連結することでしたが、仕事に戻る必要があります。

Answer 2

（あなたは、Python 2.xのを使用している場合は、代わりにrangeのxrangeを使用しています。）

計算するには、使用することができます：100,000×10万行列を格納するための

diff_matrix = numpy.subtract.outer(X, X) 
result = numpy.sqrt(numpy.abs(diff_matrix)) 
# output the result. 

注意doubleの場合、74.5 GBのメモリが必要になります。テキスト出力のファイルサイズの2倍になります。あなたは本当に行列全体が必要ですか？ （また、計算を並列化するが、それはnumpyのより多くを必要とする。）

Answer 3

いくつかの小さな最適化をあなたのコードの上に（と私はあなたは、Python 2.xのを使用していると仮定しています）：

import numpy as np 
import scipy.spatial.distance 

X = np.genfromtxt("vector.txt", dtype=None) 
fout = open("adjacencymatrix.txt", "a") 

for outer in xrange(0, 100000): 
    fout.write(" ".join(str(scipy.spatial.distance.euclidean(X[outer], X[inner])) for inner in xrange(0, 100000)) + "\n") 

fout.close() 

の前にの行列全体を事前に計算することはお勧めしませんが、そうすることで問題のシムメトリを利用して要素の半分だけを反復することができますが、多くのメモリを消費します。私はあなたが持っていたことを固執しています - 計算されるとすぐに各行が書かれます。

実際の問題は、入力データが膨大で、距離計算が100,000 x 100,000 = 10,000,000,000回実行され、マイクロ最適化の量がそれを変更しないことです。 は行列全体を計算する必要がありますか？

Answer 4

私は、行列演算を使って明示的なpythonループなしで距離行列を計算するかもしれないことに驚きました。

Xの転位を有する外積は、各組のベクトルの内積を実行し、得られた100000×100.000行列の各セルに結果を残すので有望であり、内積は、ユークリッド距離（またはその正方形）。

だから私は、内側の製品ではなく、2つのベクトルの間のユークリッド距離を取得することを調整することが重要だと思います。私の本能は、複素数がここで役に立つかもしれないと私に伝えます。

多少明るい気がすると、ここで少し明るくなることがあります。