Как оптимизировать поиск ближайших значений в массиве python?

Question

[voronin_denis]

Есть метод который ищет минимальное отклонение от заданной долготы и широты в массиве и выдает индексы значений наиболее близких к заданным. Но так как shape массива входных параметров (4800 4800) , а shape искомых (1200 1370) перебор занимает продолжительное время. Подскажите как можно оптимизировать перебор значений?

@jit(nopython=True, parallel=True)
def get_indexes_argmin(tx, ty, lat_array, lon_array):
    return (np.abs(lat_array - round(ty, 6) + np.abs(lon_array - round(tx, 6)))).argmin()

def get_unravel_coord(tx, ty, lat_array, lon_array):
    return np.unravel_index(get_indexes_argmin(tx, ty, lat_array, lon_array), lat_array.shape, order='F')

for y in range(4795):
     ta = tranform_array[x][y]
     tx = ta[0]
     ty = ta[1]
     coord = get_unravel_coord(ty, tx, lat_array, lon_array

Comments

[Griboks]

Убрать цикл.
Использовать везде векторы np. Он их вычисляет на си или сразу на процессоре. А так питон каждое значение вычисляет отдельно.

[Griboks]

Ах, да. Ещё есть профайлер. Запустите и посмотрите.

[voronin_denis]

Griboks, Вы имеете ввиду унарные операции над массивом целиком? не совсем понял, как с помощью векторов применить функцию get_unravel_coord() ?

[Griboks]

voronin_denis, я в общих чертах. Как переписать эту функцию, я не знаю. Но знаю, что надо переписать цикл.

Answer 1

[voronin_denis]

Кажется нашел решение. Использовать scipy.spatial.distance.cdist() https://docs.scipy.org/doc/scipy/reference/generat...

Answer 2

[res2001]

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

Answer 3

[devalone]

Если я правильно понял задачу, то тебе подойдёт какое-нибудь дерево, например k-d tree https://en.wikipedia.org/wiki/K-d_tree