使用Numpy在Python中快速计算多点间最小二乘距离的最优方案

场景描述 #

我们有一个XY空间内的均匀网格节点“海洋”，节点坐标存储在两个数组中（实际场景中节点数超100万）：

import numpy as np

# 示例网格：5x5的均匀节点，实际场景节点数超1,000,000
node_x_values = np.array([0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4])  
node_y_values = np.array([0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4,4,4])

另有一个数组标记了船只所在的节点索引（实际场景中船只数量超200艘）：

boat_list = np.array([3,7,18])  # 3艘船分别位于节点3、7、18

通过索引可直接获取船只坐标：

boat_x = node_x_values[7]
boat_y = node_y_values[7]

需求 #

需要高效计算所有节点中距离任意一艘船最近的节点。

单艘船的距离计算很容易实现：

# 计算所有节点到某艘船的距离，找出最近节点
boat_distances = (((node_x_values - boat_x)**2) + ((node_y_values - boat_y)**2))**0.5
node_with_min_distance = np.argmin(boat_distances)

但现有遍历所有船只的循环方法在大场景下性能极差，即使使用numba和多线程优化仍运行缓慢：

temp_accumulator_array = np.full(node_x_values.size, float('inf'), dtype=np.float32)
for boat in boat_list:
   boat_x = node_x_values[boat]
   boat_y = node_y_values[boat]
   boat_distances = (((node_x_values - boat_x)**2) + ((node_y_values - boat_y)**2))**0.5
   temp_accumulator_array = np.minimum(temp_accumulator_array, boat_distances)

node_with_least_distance_to_boat = np.argmin(temp_accumulator_array)

问题 #

除了上述循环遍历的方法，有没有更高效的实现方式？

内容的提问来源于stack exchange，提问作者PMG