0

我有一个N=3像这样的点列表作为输入： points = [[1, 1], [2, 2], [4, 4]]

我编写了这段代码来计算列表中所有元素之间的所有可能距离points，如下所示dist = min(∣x1−x2∣,∣y1−y2∣)：

distances = []
for i in range(N-1):
    for j in range(i+1,N):
        dist = min((abs(points[i][0]-points[j][0]), abs(points[i][1]-points[j][1])))
        distances.append(dist)
print(distances)

我的输出将是其中distances保存了所有距离的数组：[1, 3, 2]

它适用于N=3，但我想以更有效的方式计算它并且可以自由设置N=10^5。我也在尝试使用numpyand scipy，但是在替换循环和使用正确的方法时遇到了一些麻烦。

有人可以帮我吗？提前致谢

4

1 回答 1

1

numpythonic解决方案

要使用Numpy的全部功能计算您的距离，并大大加快速度：

  1. 将您的点转换为Numpy数组：

     pts = np.array(points)

  2. 然后运行：

     dist = np.abs(pts[np.newaxis, :, :] - pts[:, np.newaxis, :]).min(axis=2)

这里的结果是一个方形数组。但是，如果您想获取对角线上方的元素列表，就像您的代码生成的一样，您可以运行：

dist2 = dist[np.triu_indices(pts.shape[0], 1)].tolist()

我为以下9点运行此代码：

points = [[1, 1], [2, 2], [4, 4], [3, 5], [2, 8], [4, 10], [3, 7], [2, 9], [4, 7]]

对于上述数据，dist（一个全数组）中保存的结果为：

array([[0, 1, 3, 2, 1, 3, 2, 1, 3],
       [1, 0, 2, 1, 0, 2, 1, 0, 2],
       [3, 2, 0, 1, 2, 0, 1, 2, 0],
       [2, 1, 1, 0, 1, 1, 0, 1, 1],
       [1, 0, 2, 1, 0, 2, 1, 0, 1],
       [3, 2, 0, 1, 2, 0, 1, 1, 0],
       [2, 1, 1, 0, 1, 1, 0, 1, 0],
       [1, 0, 2, 1, 0, 1, 1, 0, 2],
       [3, 2, 0, 1, 1, 0, 0, 2, 0]])

上对角线部分的元素列表是：

[1, 3, 2, 1, 3, 2, 1, 3, 2, 1, 0, 2, 1, 0, 2, 1, 2, 0, 1, 2, 0, 1, 1, 0, 1, 1,
  2, 1, 0, 1, 1, 1, 0, 1, 0, 2]

我的代码有多快

事实证明，即使对于像我这样使用的小样本（9 分），我的代码运行速度也快了2 倍。对于 18 个点的样本（此处未提供） -快6倍。

即使我的函数计算“比需要的多 2 倍”（即它生成一个完整的 数组），也已经获得了这种速度差异，而结果的下对角部分在上对角部分的“镜像视图”中（计算你的代码）。

对于更大的点数，差异应该更大。在更大的点样本（比如 100 点）上进行测试，并编写我的代码快多少倍。

于 2020-08-31T17:58:28.393 回答