Как ускорить алгоритм поиска

Question

У меня есть два разных каталога (data_in и data_out) с x,y координатами многих точек.Как показано ниже, мне нужно найти все data_in точки, которые близки к data_out точкам, в частности все data_in точки в окружности радиуса r_search, центрированные на каждой data_out точках.

Этот маленький скрипт работает отлично, но он очень медленный.Есть способ ускорить процесс?

import numpy as np

data_in = np.genfromtxt(file_in)
x_in = np.array(data_in[:,1])
y_in = np.array(data_in[:,2])

data_out = np.genfromtxt(file_out)
x_out = np.array(data_out[:,1])
y_out = np.array(data_out[:,2])

r_search = 5

a=0
for i in range(len(x_out)):
    for j in range(len(x_in)):
                delta_x = abs(x_in[j] - x_out[i])
                delta_y = abs(y_in[j] - y_out[i])
                r_tmp = np.sqrt(np.power(delta_x,2) + np.power(delta_y,2))
                if (r_tmp <= r_search):
                    a=a+1

X = np.zeros(a)
Y = np.zeros(a)
a=0
for i in range(len(x_out)):
    for j in range(len(x_in)):
                delta_x = abs(x_in[j] - x_out[i])
                delta_y = abs(y_in[j] - y_out[i])
                r_tmp = np.sqrt(np.power(delta_x,2) + np.power(delta_y,2))
                if (r_tmp <= r_search):
                    X[a] = x_in[j]
                    Y[a] = y_in[j]
                    a=a+1

Answer 1

Одной из возможных оптимизаций является удаление (дорогого) квадратного корня из вычисления расстояния и сравнение с квадратом радиуса поиска, так что:

r_tmp = np.sqrt(np.power(delta_x,2) + np.power(delta_y,2))
if (r_tmp <= r_search):

становится:

r_tmp = np.power(delta_x,2) + np.power(delta_y,2)
if (r_tmp <= r_search*r_search):

Answer 2

Самым быстрым алгоритмом для описываемого вами приложения является k-мерное дерево , в частности, 2-мерное дерево, более известное как quad-tree .Это работает путем разбиения большого массива на меньшие массивы, содержащие группы точек закрытия.

Реализация его самостоятельно возможна, но не рекомендуется, поскольку есть библиотеки, которые более оптимизированы, чем вы сами.Несколько лет назад было некоторое обсуждение о том, что является лучшим.Но теперь можно сказать, что эта библиотека - лучшая.