查找两个数组之间最短距离的有效方法？

我想找到两组数组之间的最短距离。 x数组是相同的，只是包含整数。以下是我正在尝试执行的一个示例：查找两个数组之间最短距离的有效方法？

import numpy as np 
x1 = x2 = np.linspace(-1000, 1000, 2001) 
y1 = (lambda x, a, b: a*x + b)(x1, 2, 1) 
y2 = (lambda x, a, b: a*(x-2)**2 + b)(x2, 2, 10) 

def dis(x1, y1, x2, y2): 
    return sqrt((y2-y1)**2+(x2-x1)**2) 

min_distance = np.inf 
for a, b in zip(x1, y1): 
    for c, d in zip(x2, y2): 
     if dis(a, b, c, d) < min_distance: 
      min_distance = dis(a, b, c, d) 

>>> min_distance 
2.2360679774997898

此解决方案有效，但问题在于运行时。如果x的长度大约为10,000，那么解决方案就不可行，因为程序运行时间为O（n^2）。现在，我尝试了一些近似值来加快程序的运行速度：

for a, b in zip(x1, y1): 
    cut = (x2 > a-20)*(x2 < a+20) 
    for c, d in zip(x2, y2): 
     if dis(a, b, c, d) < min_distance: 
      min_distance = dis(a, b, c, d)

但是程序仍然比我想要的要长。现在，从我的理解来看，循环遍历数组通常是低效的，所以我相信还有改进的余地。关于如何加快此计划的任何想法？

来源

2016-07-29 Josh Tik

可能重复的[如何用numpy计算欧几里德距离？]（http://stackoverflow.com/questions/1401712/how-can-the-euclidean-distance-be-calculated-with-numpy） – tmthydvnprt

[有效检查Python中大量对象的欧几里得距离]的可能副本（http://stackoverflow.com/q/29885212/1461210） –

这是一个难题，如果您愿意接受近似值，这可能会有所帮助。我会检查一下像Spottify的annoy。

来源

2016-07-29 22:51:43 homer

你的问题也可以表示为2d碰撞检测，所以quadtree可能会有所帮助。插入和查询都在O（log n）时间内运行，因此整个搜索将在O（n log n）中运行。

还有一个建议，由于sqrt是单调的，因此可以比较距离的平方而不是距离本身，这将为您节省n^2平方根计算。

来源

2016-07-29 22:58:14 user3080953

scipy具有cdist function其计算所有点对间的距离：

from scipy.spatial.distance import cdist 
import numpy as np 

x1 = x2 = np.linspace(-1000, 1000, 2001) 
y1 = (lambda x, a, b: a*x + b)(x1, 2, 1) 
y2 = (lambda x, a, b: a*(x-2)**2 + b)(x2, 2, 10) 

R1 = np.vstack((x1,y1)).T 
R2 = np.vstack((x2,y2)).T 

dists = cdist(R1,R2) # find all mutual distances 

print (dists.min()) 
# output: 2.2360679774997898

这将运行比原来的for循环快250倍以上。

来源

2016-07-30 05:42:55 Mahdi

查找两个数组之间最短距离的有效方法？

回答

相关问题