给定两个元组列表，找到它们之间最近的元组(dist.

Question

我有两个带有元组(坐标(的列表，例如：

some_pt1 = [(10.76,2.9),(3.24,4.28),(7.98,1.98),(3.21,9.87)]
some_pt2 = [(11.87,6.87), (67.87,8.88), (44.44, 6.78), (9.81, 1.09), (6.91, 0.56), (8.76, 8.97), (8.21, 71.66)]

• 元组中的每个值都是平面的
• 列表的长度不同

我如何找到两个列表之间的两个最接近点。我不知道怎么做，也许可以使用距离来做到这一点。我希望有一种更有效的方法来做到这一点，因为我需要这个函数尽可能快地工作(它是更大的东西的一部分(。

Answer 1

或者，通过参考Tim Seed的代码。 这可以使用。

from scipy.spatial import distance
some_pt1 = [(10.76,2.9),(3.24,4.28),(7.98,1.98),(3.21,9.87)]
some_pt2 = [(11.87,6.87), (67.87,8.88), (44.44, 6.78), (9.81, 1.09), (6.91, 0.56), (8.76, 8.97), (8.21, 71.66)]
empthy_dict = {}
for i in range(len(some_pt1)):
    for j in range(len(some_pt2)):
        dist = distance.euclidean(some_pt1[i],some_pt2[j])
        empthy_dict[dist] = [some_pt1[i],some_pt2[j]]
shortest = sorted(empthy_dict.keys())[0]
points = empthy_dict[shortest]
print('Shortest distance is ' ,shortest,' and points are ' ,points)

Answer 2

这个怎么样

from pprint import pprint
some_pt1 = [(10.76,2.9),(3.24,4.28),(7.98,1.98),(3.21,9.87)]
some_pt2 = [(11.87,6.87), (67.87,8.88), (44.44, 6.78), (9.81, 1.09), (6.91, 0.56), (8.76, 8.97), (8.21, 71.66)]

distance = {}
for x in some_pt1:
    for y in some_pt2:
        dist =abs(abs(x[0])-abs(y[0]))+abs(abs(x[1])-abs(y[1]))
        distance[dist]=[x,y]
shortest =sorted(distance.keys())[0]
print("Min Distance is {} Objects are  {} {} ".format(shortest, distance[shortest][0],distance[shortest][0]))

Answer 3

通过欧几里得距离：

>>> some_pt1 = [(10.76,2.9),(3.24,4.28),(7.98,1.98),(3.21,9.87)]
>>> some_pt2 = [(11.87,6.87), (67.87,8.88), (44.44, 6.78), (9.81, 1.09), (6.91, 0.56), (8.76, 8.97), (8.21, 71.66)]
>>> 
>>> def dist_sq(p1_p2):
...     p1, p2 = p1_p2
...     return sum(x*y for x,y in zip(p1, p2))
... 
>>> 
>>> min(((p1, p2) for p1 in some_pt1 for p2 in some_pt2), key=dist_sq)
((3.24, 4.28), (6.91, 0.56))

它有运行时 O(n*m((其中 n、m 是列表的长度(。由于您需要查看所有货币对，因此不会比这更好。

请注意，比较平方距离就足够了，无需计算根。

Answer 4

在任何情况下，您都需要进行所有可能的组合，有一些算法可以帮助您以最佳顺序进行组合或避免重复距离。如果你想快速完成它，你应该使用一个特殊的库来帮助编译或预编译数组，这可以用 Numba 或 Cython 来完成。其他库，如scipy，也有特殊的模块，如scipy.spatial.distance。查看这篇文章以获取更多疑问类似的提示。

例：

import scipy.spatial.distance as sd
import numpy as np
some_pt1 = [(10.76,2.9),(3.24,4.28),(7.98,1.98),(3.21,9.87)]
some_pt2 = [(11.87,6.87), (67.87,8.88), (44.44, 6.78), (9.81, 1.09), (6.91, 0.56), (8.76, 8.97), (8.21, 71.66)]
np.unravel_index(np.argmin(sd.cdist(some_pt1, some_pt2)), (len(some_pt1), len(some_pt2)))

结果：(2, 4)

此代码将返回第一个列表和第二个列表中的位置。