在Python中查找列表中最接近的值

Question

我有一个列表的列表：

[[0, 2], [1, 3], [2, 5], [3, 2], [4, 5]]

还有一个列表中的值，比如说：[4,0]

想象一下这就像一个xy坐标网格，我想在这个列表的列表中找到离这个值最近的那个。

我在这里看过 如何在numpy数组中找到最近的值，更具体地说是这一行：idx = np.array([np.linalg.norm(x+y) for (x,y) in array-value]).argmin()

问题是它把x和y加在一起，所以它会说[1,3]是最近的那个，虽然在某些情况下这可能是对的，但并不总是这样。在这个特定的情况下，[3,2]才是更近的。

请帮帮我。

Answer 1

In [4]: arr = np.array([[0, 2], [1, 3], [2, 5], [3, 2], [4, 5]])

In [5]: value = np.array([4,0])

In [6]: np.linalg.norm(arr-value, axis=1)
Out[6]: array([ 4.47213595,  4.24264069,  5.38516481,  2.23606798,  5.        ])

In [7]: np.linalg.norm(arr-value, axis=1).argmin()
Out[7]: 3

In [8]: arr[np.linalg.norm(arr-value, axis=1).argmin()]
Out[8]: array([3, 2])

注意，如果你的 arr 数组非常大，并且你需要计算与很多其他点最接近的点，使用 KDTree 会更高效。因为一旦你把数据放进 KDTree（这一步需要 O(n log n) 的时间），那么查找最近的点只需要 O(log n) 的时间。而使用 arr[norm(...).argmin()] 查找最近的点则需要 O(n) 的时间。

所以如果你有 scipy 库，可以这样找到最近的点：

In [22]: from scipy import spatial

In [23]: tree = spatial.KDTree(arr)

In [24]: distances, indices = tree.query([4, 0])

In [25]: tree.data[indices]
Out[25]: array([3, 2])