2

X 是一个文本文件，包含100000相同大小（500 个元素）的位向量（即每行是一个包含 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 的内存，对于文本输出的文件大小，可能需要加倍。你真的需要整个矩阵吗？（您也可以并行化计算，但这需要的不仅仅是 numpy。）

于 2012-01-10T15:01:29.130 回答
0

我有一种预感，可以通过使用矩阵运算在没有显式 python 循环的情况下计算距离矩阵。

其转置的外积X似乎很有希望，因为它执行每对向量的内积并将结果留在生成的 100.000 x 100.000 矩阵的每个单元格中，并且内积与欧几里德距离（或其正方形）。

所以我想这是一个调整以获得两个向量之间的欧几里得距离而不是内积的问题。我的直觉告诉我，复数在这里可能有用。

也许一些更聪明的头脑可以在这里点亮一些光。

于 2012-01-10T16:40:39.667 回答