Как чрезвычайно быстро изменить значения многомерного массива numpy? ⇐ Python

[Anonymous]

Я работаю над проектом, который предполагает отслеживание тысяч точек по сетке (640, 640).
При отслеживании этих точек я сохраняю их движение в формате линейной массив векторов, объясняющий изменение положения каждой точки, в следующем формате:

Код: Выделить всё

v = [starting_x, starting_y, distance_x, distance_y]

Мне (ради проекта) нужно создать векторное поле размером с вышеупомянутую сетку (640, 640). Однако предоставленный мне объем данных охватывает лишь несколько точек этой сетки. Поэтому Я просматриваю всю эту сетку, вычисляя расстояния между каждой отдельной точкой и всеми векторами, хранящимися внутри массива. Затем я нахожу индекс ближайшего вектора по расстоянию и заменяю значение этого пикселя значениями [dx, dy] этого вектора.
Сначала я использовал для этого умножение матрицы и произведение Адамара, но недавно объем данных внезапно увеличился с ~300 до более чем 2000, что вызвало массовое переполнение памяти, поскольку размер матрицы, над которой я работал, достиг почти 13 ГБ. (Чтобы правильно вычесть координаты для всех точек, мне пришлось сгенерировать массив размером 640x640x2000x2, содержащий координаты каждой точки.)
Учитывая, что мой проект в будущем должен был работать на гораздо больших наборах данных, я изменил первоначальный метод к простой итерации с тремя вложенными циклами (да, я понимаю, как ужасно это звучит). Таким образом, с помощью нескольких оптимизаций и предварительных расчетов я ограничил объем активно используемых данных с 13 ГБ до максимум 2,5 ГБ с тем же набором данных.
Однако время обработки увеличилось. резко возрос с прежних ~10 секунд до ~100 минут, что я бы не стал считать повышением уровня.
Следовательно, мне нужно найти способ обработки такого огромного количества данных с гораздо большей эффективностью.
[Редактировать №1]:
Вот функция в ее текущей форме:

Код: Выделить всё

def spread_vectors_by_least_distance(mainvectors: np.array):
length = mainvectors.shape[0]   # this is the amount of vectors we're working with
# Pre-calculating repetitive data:
mvectors_help = np.zeros((length, 3), np.uint16)
for z in range(length):
y_, x_ = mainvectors[z, :2]
mvectors_help[z] = (y_*y_ + x_*x_, 2*y_, 2*x_)

width, height = 640, 640
deltas = np.zeros((height, width, length), np.uint16)

for y in range(height):
ysqr = y*y
for x in range(width):
xsqr = x*x
xsqr_ysqr = ysqr + xsqr

delta_min = 999_999_999
index = 0
for z in range(length):
xy_sqr, y_dbl, x_dbl = mvectors_help[z]
# delta = (x-x_)^2 + (y-y_)^2, which simplifies to:
delta = xy_sqr + xsqr_ysqr - y*y_dbl - x*x_dbl

# We only need the smallest distance
if delta_min > delta:
delta_min = delta
index = z

# The point's value is the closest vector's value:
deltas[y, x] = mainvectors[index, 2:]
return deltas

Мне известны два (2) пути, которыми я теперь могу воспользоваться для решения своей проблемы:
1. Я могу найти встроенный способ перебора этого массива, оптимизированный с помощью numpy до такой степени, что выполнение около 800_000_000 алгебраических операций И ​​замены элементов массива займет разумное количество времени.2. Я могу использовать привязку Python-C или Python-C++, чтобы выполнять всю эту обработку данных на гораздо более быстром языке (в десять или даже в сто раз быстрее, насколько я понял), однако это означало бы бесчисленные затраты часы изучения нового модуля для Python (например, cython) и отладки кода на языке, который мне гораздо менее понятен.
Поэтому я обращаюсь ко всем вдохновителям Python со всего мира. , в поиске самого простого, но наиболее эффективного решения моей проблемы.
[Редактировать №2] В ответ на комментарий @jared, вот данные о времени, которые я получен с помощью timeit на pythonanywhere.com/try-ipython:

Код: Выделить всё

In [1]: import numpy as np

In [2]: def func(mainvectors: np.array):
...:     length = mainvectors.shape[0]
...:     mvectors_help = np.zeros((length, 3), np.uint32)
...:     for z in range(length):
...:         y_, x_ = mainvectors[z, :2]
...:         mvectors_help[z] = (y_*y_ + x_*x_, 2*y_, 2*x_)
...:     width, height = 640, 640
...:     deltas = np.zeros((height, width, 2), np.uint32)
...:     for y in range(height):
...:         ysqr = y*y
...:         for x in range(width):
...:             xsqr = x*x
...:             xsqr_ysqr = ysqr + xsqr
...:             delta_min = 999_999_999
...:             index = 0
...:             for z in range(length):
...:                 xy_sqr, y_dbl, x_dbl = mvectors_help[z]
...:                 delta = xy_sqr + xsqr_ysqr - y*y_dbl - x*x_dbl
...:                 if delta_min > delta:
...:                     delta_ming = delta
...:                     index = z
...:             deltas[y, x] = mainvectors[index, 2:]
...:     return deltas
...:

In [3]: def generate_vector_arr(size: int):
...:     temp = np.arange(size*4).reshape((size, 4))
...:     return temp

In [4]: %timeit for x in range(1, 2): func(generate_vector_arr(x))
3.79 s ± 46.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [5]: %timeit for x in range(1, 5): func(generate_vector_arr(x))
35.9 s ± 632 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Обратите внимание, что входные данные в этом моделировании состоят всего из 1–5 векторов, тогда как на самом деле их количество исчисляется сотнями, если не тысячами.
Я также создал изображения, которые помогут объяснить, что должен делать алгоритм:
Вот сетка, содержащая около 700 векторов
А вот представление результатов со случайными цветами вместо векторных значений.
Чтобы внести ясность: каждая фигура определенного цвета представляет собой набор точек, которые наиболее близки к соответствующим фигурам. вектор.

Подробнее здесь: https://stackoverflow.com/questions/787 ... umpy-array