我试图找到从用户输入的点到我拥有的50,000个点的列表的最接近点（欧几里得距离）。请注意，点列表始终在变化。而最接近的距离取决于用户在何时何地点击该点。

#find the nearest point from a given point to a large list of points

import numpy as np

def distance(pt_1, pt_2):
    pt_1 = np.array((pt_1[0], pt_1[1]))
    pt_2 = np.array((pt_2[0], pt_2[1]))
    return np.linalg.norm(pt_1-pt_2)

def closest_node(node, nodes):
    pt = []
    dist = 9999999
    for n in nodes:
        if distance(node, n) <= dist:
            dist = distance(node, n)
            pt = n
    return pt

a = []
for x in range(50000):
    a.append((np.random.randint(0,1000),np.random.randint(0,1000)))

some_pt = (1, 2)

closest_node(some_pt, a)


评论

我正在研究类似的问题，发现了这一点。同样，Scipy.spatial.KDTree是实现此类方法的方法。
可以对表示“列表始终更改”的部分进行扩展，这可能暗示一些提高代码性能的想法。列表是随机更新的，还是每隔几秒钟添加一些点，而有些点会丢失？
如果必须重复搜索同一组点，则scikit-learn中的球树方法可以有效地做到这一点。这些点在预处理步骤中被分类为树形结构，以更快地找到最接近的点。 scikit-learn.org/stable/modules/generation / ...

#1 楼

如果对距离计算进行矢量化，肯定会更快：

点积函数：

def closest_node(node, nodes):
    nodes = np.asarray(nodes)
    dist_2 = np.sum((nodes - node)**2, axis=1)
    return np.argmin(dist_2)


理想情况下，您已经将点列表放置在数组中，而不是列表，这将大大加快速度。 >

评论

\ $ \ begingroup \ $
感谢您的答复，您介意解释为什么这两种方法更快吗？我很好奇，因为我不是来自CS背景
\ $ \ endgroup \ $
– dassouki
13年7月7日在3:28
\ $ \ begingroup \ $
Python for循环非常慢。在矢量的所有项目上使用numpy运行操作时，在C的幕后运行着隐藏的循环，它们的速度要快得多。
\ $ \ endgroup \ $
– Jaime
13年7月7日，下午3:54

#2 楼

您所有的代码都可以被重写为： />
如果randint(1000)是randint(0, 1000)（默认值），则结果来自randint。因此：

from numpy import random
from scipy.spatial import distance

def closest_node(node, nodes):
    closest_index = distance.cdist([node], nodes).argmin()
    return nodes[closest_index]

a = random.randint(1000, size=(50000, 2))

some_pt = (1, 2)

closest_node(some_pt, a)


结果：

a = []
for x in range(50000):
    a.append((np.random.randint(0,1000),np.random.randint(0,1000)))


它也快很多（在我的测试中快了二十倍） 。


更重要的是，high具有包含None函数的[0, low)模块：


size

计算距离在两个输入集合的每一对之间。


因此不再需要在循环中计算randint。

也可以使用for循环来查找最小值的位置，但这可以通过scipy对象的scipy.spatial.distance方法来完成。

因此，您的cdist函数可以简单地定义为：我比较了此问题中定义的所有cdist(XA, XB, metric='euclidean', p=2, V=None, VI=None, w=None)函数的执行时间：

a = np.random.randint(1000, size=(50000, 2))


所有矢量化函数都执行数百个

distance的性能仅次于Jaime的第二个功能，但只有一点。
肯定是最简单的argmin。