时间戳

首页 > 解决方案 > 如何加快搜索算法

python - 如何加快搜索算法

问题描述

我有两个不同的目录（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

标签： pythonarraysnumpy

解决方案

一种可能的优化是从距离计算中删除（昂贵的）平方根并与平方搜索半径进行比较，因此：

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

推荐阅读