Оптимизация вычисления матрицы смежности

Question

X - текстовый файл, содержащий 0 бит (1024 элемента), содержащий 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

Редактировать: Полное переписано после понимания вопроса лучше. Учитывая размер данных и т. Д., Это сложно. Я получил свои лучшие результаты в ускорении со следующими до сих пор:

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, используйте xrange вместо range.)

Для вычисления, вы можете использовать:

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

Обратите внимание, что для хранения матрицы 100000 × 100000 double вам понадобится 74,5 ГБ памяти и, возможно, вдвое больше, чем размер файла вывода текста. Вам действительно нужна целая матрица? (Вы также можете распараллелить вычисления, но потребуется более 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

У меня есть догадка о том, что матрица расстояний может быть рассчитана без явных циклов питона, используя операции с матрицами.

Внешнее изделие X с его транспонированным материалом кажется многообещающим, поскольку оно выполняет внутренний продукт каждой пары векторов и оставляет результат в каждой ячейке получаемой матрицы 100 000 х 100 000, а внутренний продукт тесно связан с евклидовом расстоянии (или его квадрате).

Так что я думаю, что это вопрос настройки, чтобы получить эвклидовое расстояние между двумя векторами, а не внутренним продуктом. Мой инстинкт подсказывает мне, что здесь могут быть полезны комплексные числа.

Возможно, какой-то более яркий ум мог бы проливать свет здесь.