n 维中最接近的对

Question

python中有没有高效的库函数可以找到一对closest/farthest的点？输入是位于边缘大小为 1 的 k 维立方体中的点列表。为了找到最接近的，以下代码花费了太多时间。 TC: O( n**2 * k ) 其中 n 是输入的大小。在我的例子中，输入 n 大约是 4000，k 的值大约是 300。

def euclid_dist( p1, p2 ):
    val = 0
    for i in range(len(p1)):
        val += (p1[i]-p2[i])**2
    return val

def find_close_cluster( points ):
    ans1 = 0
    ans2 = 1
    min_dist = 1000000000000
    for i in range( len(clusters) ):
        for j in range( i+1,len(clusters)):
            current_dist = euclid_dist(clusters[i],clusters[j])
            if( current_dist < min_dist ):
                ans1 = i
                ans2 = j
                min_dist = current_dist
    return ( ans1, ans2 )

Answer 1

您应该使用 numpy ndarrays 和 scipy.spatial.distance.cdist 函数。 numpy 为您提供了一个高效的容器来以矢量化形式操作数据，因此代码运行速度比在迭代器或列表上执行循环快得多。 scipy.spatial.distance.cdist 使用 numpy 数组来计算所有元素之间的距离。查看 documentation 了解更多详情。下面的代码应该可以工作：

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

your_data = np.asarray([[first_sample], [second_sample], [...])
d = cdist(your_data, your_data)
number_samples = your_data.shape[0]
# Select d(a_i,a_j), i != j without repetitions
il1 = np.tril_indices(number_samples, k=-1) 
dist = d[il1]
arg_min = dist.argmin()
min = dist.min()
arg_max = dist.argmax()
max = dist.max()

n 维中最接近的对

Closest pair in n dimension

python

algorithm

python-2.7

closest-points