优化邻接矩阵计算

Question

X是一个文本文件，里面有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()

谢谢。

Answer 1

我有一种感觉，距离矩阵可能可以通过矩阵运算来计算，而不需要用到显式的Python循环。

将X和它的转置进行外积运算看起来很有前景，因为这样可以计算每一对向量的内积，并把结果放在生成的10万乘10万的矩阵的每个单元格里，而内积和欧几里得距离（或者它的平方）是有很大关系的。

所以我想，只需要稍微调整一下，就能得到两个向量之间的欧几里得距离，而不是内积。我的直觉告诉我，复数在这里可能会有用。

也许有更聪明的人能对此提供一些见解。

Answer 2

这里有一些对你代码的小优化建议（我假设你在用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 3

编辑：在更好地理解问题后，我重新写了一遍。考虑到数据的大小等因素，这个问题有点棘手。到目前为止，我在加速方面得到了最佳结果：

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))

所以我尝试平衡数据集每一部分的大小和内存的使用。这让我估计完成的时间缩短到了6600秒，也就是大约110分钟。你可以看到，我还开始尝试使用多进程池来实现并行处理。我的计划是异步处理每一部分数据，并将它们保存到不同的文本文件中，然后再把这些文件合并起来，但我得回去工作了。