2

Xは、等しいサイズ（500要素）のビットベクトルを含むテキストファイルです100000（つまり、各行は500要素のベクトルです）。以下のコードを使用して隣接行列（100000 X 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()

ありがとうございました。

4

4 に答える 4

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 回実行され、マイクロ最適化の量がそれを変更しないことです。行列全体を計算する必要がありますか?

于 2012-01-10T15:45:14.510 に答える
2

編集：質問をよりよく理解した後、完全に書き直しました。データのサイズなどを考えると、これは注意が必要です。これまでのところ、次の高速化で最高の結果が得られました。

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 分かかりました。マルチプロセッシング プールを使用して並列化できるかどうかも調べ始めたことがわかります。私の戦略は、各チャンクを非同期的に処理して別のテキスト ファイルに保存し、後でファイルを連結することでしたが、仕事に戻らなければなりませんでした。

于 2012-01-10T19:23:52.620 に答える
0

(Python 2.x を使用している場合は、xrange代わりに を使用しrangeます。)

計算するには、次を使用できます。

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

100,000 × 100,000 の行列を格納するにはdouble、74.5 GB のメモリが必要であり、テキスト出力のファイルサイズの場合はその 2 倍になることに注意してください。マトリックス全体が本当に必要ですか? (計算を並列化することもできますが、それには numpy 以上のものが必要になります。)

于 2012-01-10T15:01:29.130 に答える
0

行列演算を使用して、明示的な python ループを使用せずに距離行列を計算できるという予感があります。

ベクトルの各ペアの内積Xを実行し、結果の 100.000 x 100.000 行列の各セルに結果を残し、内積はユークリッド距離 (またはその四角）。

したがって、内積ではなく2つのベクトル間のユークリッド距離を取得するには、微調整の問題だと思います。私の本能は、複素数がここで役立つかもしれないと教えてくれます。

たぶん、明るい心がここに光を投げかけるかもしれません。

于 2012-01-10T16:40:39.667 に答える