Обойти проблему с ошибкой памяти в списках Python или более умный способ в Numpy - PullRequest
Новая
       44

Обойти проблему с ошибкой памяти в списках Python или более умный способ в Numpy

0 голосов
/ 24 октября 2018

Я пытаюсь вычислить матрицу расстояний DTW, которая будет рассматривать 150 000 временных рядов, каждый из которых имеет от 13 до 24 наблюдений, то есть полученная матрица расстояний будет представлять собой список размером приблизительно (150 000 x 150 000) / 2 =11 250 000 000.

Я запускаю это на большом кластере данных размером 200 ГБ, но получаю ошибку памяти.

Я использую библиотеку dtaidisatance и использовал distance_matrix_fast функция, которую я мог бы передать всем временным рядам одновременно в списке, но у меня была похожая ошибка памяти, но выходящая из пакета.ошибка была сброшена сразу же, как только я ее запустил.Я также использовал блочную функцию в пакете, но, похоже, он не может взять все временные ряды сразу, чтобы начать с.

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

Файл "/root/anaconda2/test/final_clustering_2.py", строка 93, в distance_matrix_scaled.append (dtw.distance_fast (Series_scaled [i], Series_scaled [j])) MemoryError

Вот мой код ниже: 

distance_matrix_scaled = []

m=len(Series_scaled)
#m=100000
for i in range(0, m - 1):
    for j in range(i + 1, m):

distance_matrix_scaled.append(dtw.distance_fast(Series_scaled[i], Series_scaled[j]))

# save it to the disk
np.save('distance_entire',  distance_matrix_scaled)

Не могли бы вы помочь ответить, почему я получаю эту ошибку памяти?это предел списка Python или размер моего кластера, вызывающий это?Есть ли какой-нибудь умный способ или формат в numpy, который я мог бы использовать для решения этой проблемы?

Ответы [ 2 ]

0 голосов
/ 24 октября 2018

Если вы вычисляете что-то вроде евклидова расстояния, посмотрите на стоимость памяти вашей вычислительной задачи, вы сгенерируете промежуточный временный массив размером 150000*149999/2*(13~24) где

  • 150000*149999/2 представляет количество неупорядоченных пар среди 150000 временных рядов (исключая самосопряженную пару)

  • 13~24 представляет разницу между двумя векторами временных рядов, которые будут norm отредактированы позжеи уменьшите до одного числа на пару.

Каждое число обычно представляет собой число с плавающей запятой или двойное число, которое составляет 4 или 8 байт.Следовательно, алгоритм будет занимать 1T ~ 4T памяти, что, очевидно, приведет к взрыву 200G.

Для сокращения стоимости памяти доступно несколько приемов, помимо ручного разделения на более мелкие задачи:

  • Если вы настаиваете на numpy, определенно выберите меньшие dtype с, например float32.Если ваш номер маленький, вы можете даже рассмотреть такие вещи, как int16 или int8.Не используйте float16, поскольку он не поддерживает вычисления на процессоре (очень медленно).

  • Если это не так, вы можете рассмотреть numba, что позволяет компилироватьцикл Python для высокоэффективного кода ЦП и запуска его на всех ядрах, что должно быть оптимальным решением для ЦП (для этого не нужно создавать временный массив).

  • У Сципи также естьscipy.spatial.distance.pdict.Не совсем уверен, как он будет работать с точки зрения памяти, но вы можете попробовать.

0 голосов
/ 24 октября 2018

Ваш двойной цикл for имеет 4999950000 итераций.Вы добавляете это много раз в список.Все еще странно?

Если расстояние скалярное, тогда вы действительно можете сэкономить память, предварительно выделив такой большой массив (и надеясь на лучшее, с точки зрения памяти): 

import numpy as np

m = 100000
distances = np.empty(m*(m-1)/2) # size: 4999950000
k = 0
for i in range(0, m - 1):
    for j in range(i + 1, m):
         distances[k] = dtw.distance_fast(Series_scaled[i], Series_scaled[j])
         k += 1

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

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

Небольшое замечание: заполняемый нами массив (при условии 64-разрядных двойных чисел) занимает примерно 37 ГБ ОЗУ.Это много.и если вы сможете уместить это в своей памяти, вам придется ждать 5 миллиардов итераций цикла Python (double).Это займет ... много времени.Не задерживай дыхание.

...