是否有一种有效的算法可以在不重复计算的情况下找到多个2d点之间的距离？
是否有一种有效的算法可以在不重复计算的情况下找到多个2d点之间的距离？
提问于 2019-11-30 20:18:10
我试图创建一个Python函数，它将以x坐标和y坐标作为输入，并计算所有数据点之间的距离。距离应该存储为一个列表(或数组)，并传递回调用程序。我开始使用的算法如下所示。
def distance(x, y):
dist = []
for j in range(len(x)):
for i in range(len(y)):
"""
Don't calculate the distance between the same point
since it will obviously be zero
"""
if j != i:
mag = (x[j] - x[i]) ** 2.0 + (y[j] - y[i]) ** 2.0
dist.append(np.sqrt(mag))
return dist
x_vals = [2.3, 3.6, 1.8]
y_vals = [1.6, 4.8, 2.8]
vals = distance(x_vals, y_vals)
print(vals)该算法将计算点1-2、1-3、2-1、2-3、3-1和3-2之间的距离，并返回以下列表
[3.4539832078341086, 1.2999999999999996, 3.4539832078341086, 2.6907248094147422, 1.2999999999999996, 2.6907248094147422]虽然结果是正确的，但该算法重复测量。你可以看到，1-2点的距离和2-1点的距离相同，1-3点的距离和3-1点的距离相同，2-3点的距离与3-2点的距离相同。换句话说，我想要创建一个更有效的算法，它只计算1-2、1-3和2-3之间的值。虽然此示例只包含3个数据点(即3对x和y坐标)，但我希望该算法适用于更多的数据点，并尽可能有效，因为这可以应用于大量数据点。
回答 4
Stack Overflow用户
回答已采纳
发布于 2019-11-30 22:46:22
这应该更快，因为它不使用显式的循环。
from itertools import combinations
from math import sqrt
def dist(x_vals, y_vals):
" Distance of pair combinations of x_vals & y_vals "
# Distance between zipped pairs
dist2 = lambda z: sqrt((z[0][0] - z[1][0]) ** 2.0 + (z[0][1]- z[1][1]) ** 2.)
# Use combinations to create desired distance pairs (i.e. 1-2, 1-3, 2-3, etc.)
return list(map(dist2, combinations(zip(x_vals, y_vals), 2)))测试
x_vals = [2.3, 3.6, 1.8]
y_vals = [1.6, 4.8, 2.8]
print(dist(x_vals, y_vals))
# >> [3.4539832078341086, 1.2999999999999996, 2.69072480941474227422]性能测试
小数据测试
比较张贴的解决方案--基于地图的列表理解(6502个发布)和当前发布(darrlg) &组合在小数据集中是最快的。
Original Data (Small):
x_vals = [2.3, 3.6, 1.8]
y_vals = [1.6, 4.8, 2.8]- 原始发帖：22.5s±853ns/圈(平均±std )。dev.7次运行中，每一次循环10000次)
- 乔恩更新：19.5秒/圈±700 ns (平均±std )。dev.7次运行中，每一次循环100000次)
- 18.8 s±929 ns /圈(平均±std )。dev.7次运行中，每一次循环10000次)
- 5.85s±239 ns /循环(平均±std )。dev.7次运行中，每一次循环100000次)
- 目前的解决方案：5.74s±195 ns /环(平均±std )。dev.7次运行中，每一次循环100000次)
大数据测试(向量长度1000)
结果:对于较大的数据集来说，Scipy要快得多。
Data
N = 1000
x_vals = [random.randrange(N) for _ in range(N)]
y_vals = [random.randrange(N) for _ in range(N)]- 原始代码：3.2s/循环±20 ms (平均±std )。dev.7次运行，每一次循环1次)
- 更新代码：1.77s±39.6ms/圈(平均±std )。dev.7次运行，每一次循环1次)
- 7.65ms±80.1s/圈(平均±std )。dev.7次运行中，每一次循环100次)
- 910 ms±16.5ms/圈(平均±std )。dev.7次运行，每一次循环1次)
- 目前解决方案：687ms±7.92ms/环(平均±std )。dev.7次运行，每一次循环1次)
Stack Overflow用户
发布于 2019-11-30 23:21:40
一个简单的解决方案是使用带有两个循环的理解。
dist = [((x_vals[i] - x_vals[j])**2 + (y_vals[i] - y_vals[j])**2)**0.5
for i in range(len(x_vals))
for j in range(i+1, len(x_vals))]Stack Overflow用户
发布于 2019-12-01 00:05:36
你能用scipy吗？如果是这样的话，scipy.spatial.distance模块有一个函数来计算各种距离度量，并且聪明地不计算冗余对：scipy.spatial.distance.pdist。这将返回唯一的距离集。您可以选择使用助手函数方形来获得冗余，如果这样可以使后续处理更容易。对于您给定的数据：
import scipy.spatial
scipy.spatial.distance.pdist(np.array([x_vals,y_vals]).T,metric='euclidean')
# returns the unique answers array([3.45398321, 1.3 , 2.69072481])
scipy.spatial.distance.squareform(_)
# returns array([[0. , 3.45398321, 1.3 ],
# [3.45398321, 0. , 2.69072481],
# [1.3 , 2.69072481, 0. ]])页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/59119893
复制相关文章
相似问题
腾讯云开发者
