使用 Python 有效计算数组中所有点之间的距离

Question

我有一个像这样的 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。我也在尝试使用 numpy 和 scipy，但我在替换循环和使用正确方法时遇到了一些麻烦。

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

Answer 1

numpythonic解决方案

使用 Numpy 的全部功能来计算您的距离，然后去做快得多：

将你的 points 转换为 Numpy 数组：
```
 pts = np.array(points)
```

然后运行:

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

这里的结果是一个方形数组。但是如果你想得到对角线以上元素的 list，就像您的代码生成的一样，您可以运行:

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 倍”，即它生成 full 数组，而结果的下对角线部分是“镜子查看”上对角线部分（计算您的代码的内容）。

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

使用 Python 有效计算数组中所有点之间的距离

Compute distances between all points in array efficiently using Python

python

numpy

distance

scipy

numpythonic解决方案

我的代码有多快