python - 如何使用 cdist 或 tensorflow 加速最近点比较？

Question

我有两组点，一组是由 x,y 坐标组成的 map ，第二组是 x,y 坐标的路径。我试图找到距离我的路径点最近的 map 点，非常简单。除了我的 map 有 380000 个点之外，我的路径(我有几条)每条路径本身也包含约 350000 个点。除了对数据进行采样以获得更小的数据集之外，我还试图找到一种更快的方法来完成此任务。

基本算法:

import pandas as pd
from scipy.spatial.distance import cdist
...

def closeset_point(point, points):
    return points[cdist([point], points).argmin()]

# log['point'].shape; 333000
# map_data['point'].shape; 380000
closest = [closest_point(log_p, list(map_data['point'])) for log_p in log['point']]

按照这个例子:Find closest point in Pandas DataFrames

将其转换为 tqdm 进度条以查看需要多长时间(因为显然需要一段时间)，我注意到大约需要 10 小时才能完成。

tqdm 循环:

for i in trange(len(log), desc='finding closest points'):
    closest.append(closest_point(log['point'].loc[i], list(map_data['point'])))
>> finding closest points: 5%|   | 16432/333456 [32:11<10:13:52], 8.60it/s

虽然10个小时也不是不可能，但我想知道是否有办法加快速度？我有一个可靠的 GPU/CPU/RAM 可供使用，所以我觉得这应该是可行的。我也在学习 tensorflow (但说实话，我的数学很糟糕，所以我对此一无所知)

关于如何通过多线程、GPU 计算、 tensorflow 或其他某种魔法来加快速度，有什么想法吗？inb4 python 很慢;)

*编辑:图像显示了我正在尝试做的事情。绿色是路径，蓝色是 map ，橙色是我想要找到的。

Answer 1

以下是您正在尝试执行的操作的一个小示例。将变量 coords1 视为变量 log['point'] 并将 coords2 视为变量 log['point'] 。最终结果是最接近 coord2 的 coord1 索引。

from scipy.spatial import distance
import numpy as np
coords1 = [(35.0456, -85.2672),
          (35.1174, -89.9711),
          (35.9728, -83.9422),
          (36.1667, -86.7833)]
coords2 = [(35.0456, -85.2672),
          (35.1174, -89.9711),
          (35.9728, -83.9422),
          (34.9728, -83.9422),
          (36.1667, -86.7833)]


tmp = distance.cdist(coords1, coords2, "sqeuclidean") #  sqeuclidean based on Mark Setchell comment to improve speed further
result = np.argmin(tmp,1)
# result: array([0, 1, 2, 4])

这应该更快，因为它在一次迭代中完成了所有事情。