python - 查找从一个列表中的点到另一个列表中的点的最小距离之和？

Question

我有两个列表，分别包含 x 和 y 个 n 维点。我必须计算列表一中每个点(包含 x 点)与第二个列表中每个点(包含 y 点)的最小距离之和。我正在计算的距离是欧氏距离。需要优化的解决方案。

我已经在 Python 中实现了它的原始解决方案。但它的时间复杂度太高，无法在任何地方使用。会有优化的可能。这个问题的时间复杂度是否可以比我已经实现的降低？

我正在读这个paper我正在尝试实现。在这方面，他们遇到了类似的问题，他们表示这是 Earth Mover Distance 的特殊情况。 .由于没有给出代码，因此无法知道它是如何实现的。因此我天真的实现，上面的代码对于 11k 文档的数据集来说太慢了。我使用 Google Colab 来执行我的代码。

# Calculating Euclidean distance between two points
def euclidean_dist(x,y):
  dd = 0.0
  #len(x) is number of dimensions. Basically x and y is a 
  #list which contains coordinates of a point
  for i in range(len(x)):
    dd = dd+(x[i]-y[i])**2
  return dd**(1/2)

# Calculating the desired solution to our problem
def dist(l1,l2):
  min_dd = 0.0
  dd = euclidean_dist(l1[0],l2[0])
  for j in range(len(l1)):
    for k in range(len(l2)):
      temp = euclidean_dist(l1[j],l2[k])
      if dd > temp:
        dd = temp
    min_dd = min_dd+dd
    dd = euclidean_dist(l1[j],l2[0])
  return min_dd  

Answer 1

为了减少运行时间，我建议找到曼哈顿距离(delta x + delta y)，对每个点的结果数组进行排序，然后创建一个缓冲区 +20% 的最低曼哈顿距离，如果排序列表中的值在在 +20% 的范围内，您可以计算欧氏距离并找到正确/最小的欧氏答案。

这会减少一些时间，但如果点都靠得很近，20% 的数字可能不会减少时间，因为它们中的大多数都适合缓冲区，请尝试微调 20% 参数以查看最适合的参数你的数据集。请记住，由于欧几里德距离与曼哈顿距离的性质，将它减少太多可能会导致不准确的答案。