2

python中是否有任何有效的库函数来查找最近/最远的一对点？输入是位于边大小为 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 )
4

1 回答 1

2

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

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()
于 2017-04-11T18:09:32.173 回答