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

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

Спасибо.


python optimization adjacency-matrix
person Maggie    schedule 10.01.2012    source источник
comment
Матрица симметрична, поэтому вам нужно вычислить только половину элементов.   -  person nimrodm    schedule 10.01.2012

Ответы (4)


arrow_upward
2
arrow_downward

Изменить: полностью переписано после лучшего понимания вопроса. Учитывая размер данных и т. д., это сложно. На данный момент я получил свои лучшие результаты при ускорении со следующим:

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 минутам. Как видите, я также начал выяснять, смогу ли я распараллелить использование многопроцессорного пула. Моя стратегия заключалась бы в асинхронной обработке каждого фрагмента и сохранении их в другой текстовый файл, а затем в объединении файлов, но мне нужно было вернуться к работе.

person Cyclone    schedule 10.01.2012
comment
Большое спасибо за ответ. он отлично работает. Я пробую многопроцессорную часть, но я совершенно новичок в этом... так что посмотрим, как пойдет... еще раз спасибо :) - person Maggie; 11.01.2012
comment
многопроцессорный пул python великолепен, когда он работает, но я постоянно сталкиваюсь с ограничениями в том, как он реализует сериализацию функции для передачи в потоки пула. Например, функция, передаваемая в пул, должна быть объявлена ​​как глобальная... фу. Использование многопроцессорного пула по умолчанию может быть тупиковым... Также я бы порекомендовал, если вы будете распараллеливать это, чтобы вы либо записывали результаты обратно на диск отдельно, перед объединением, либо использовали массивы с memmapped, numpy имеет довольно хорошую поддержку memmap. - person Cyclone; 13.01.2012

arrow_upward
3
arrow_downward

Некоторые небольшие оптимизации вашего кода (и я предполагаю, что вы используете 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 раз, и никакие микрооптимизации этого не изменят. Вы уверены, что вам нужно вычислять всю матрицу?

person Óscar López    schedule 10.01.2012

arrow_upward
0
arrow_downward

(Если вы используете 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 ГБ памяти и, возможно, вдвое больше для размера файла вывода текста. Вам действительно нужна вся матрица? (Вы также можете распараллелить вычисления, но для этого потребуется нечто большее, чем numpy.)

person kennytm    schedule 10.01.2012

arrow_upward
0
arrow_downward

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

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

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

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

person fortran    schedule 10.01.2012