找到数组一中离数组二元素最近的元素

Question

找到数组一中离数组二元素最近的元素

4

这个答案解释了如何高效地找到（排序后的）数组中离一个单一点最近的元素，适用于大型数组（稍作修改）：

def arg_nearest(array, value):
    idx = np.searchsorted(array, value, side="left")
    if idx > 0 and (idx == len(array) or math.fabs(value - array[idx-1]) < math.fabs(value - array[idx])):
        return idx-1
    else:
        return idx

如果我们想要找到离一个点集（即第二个数组）最近的数组元素，除了使用for循环，是否有更高效（对于大型数组而言）的方法来扩展这个问题？

一些测试案例：

>>> xx = [0.2, 0.8, 1.3, 1.5, 2.0, 3.1, 3.8, 3.9, 4.5, 5.1, 5.5]
>>> yy = [1, 2, 3, 4, 5]
>>> of_x_nearest_y(xx, yy)
[0.5, 2.0, 3.1, 3.9, 5.1]

>>> xx = [0.2, 0.8, 1.3, 1.5, 2.0, 3.1, 3.8, 3.9, 4.5, 5.1, 5.5]
>>> yy = [-2, -1, 4.6, 5.8]
>>> of_x_nearest_y(xx, yy)
[0.2, 0.2, 4.5, 5.5]

编辑：假设两个数组已经排序，你可以通过排除已匹配的值来比完全幼稚的for循环更好地处理它们，即：

def args_nearest(options, targets):
    locs = np.zeros(targets.size, dtype=int)
    prev = 0
    for ii, tt in enumerate(targets):
        locs[ii] = prev + arg_nearest(options[prev:], tt)
        prev = locs[ii]
    return locs

- DilithiumMatrix

searchsorted 接受一个值数组进行搜索，因此修改 arg_nearest 以适应您的工作并不太困难。 - user2357112

@user2357112 嗯，说得好！ - DilithiumMatrix

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Divakar · Accepted Answer

您可以做一些更改，将代码扩展到 value 数组中的多个元素，例如：

idx = np.searchsorted(xx, yy, side="left").clip(max=xx.size-1)
mask = (idx > 0) &  \
       ( (idx == len(xx)) | (np.fabs(yy - xx[idx-1]) < np.fabs(yy - xx[idx])) )
out = xx[idx-mask]

说明

术语： array 是我们要将来自 value 的元素放入其中以保持 array 排序性质的数组。

扩展针对单个元素的解决方案以搜索多个元素所需的更改：

1] 将从 np.searchsorted 获得的索引数组 idx 剪切到最大值为 array.size-1，因为对于 value 中大于 array 最大值的元素，我们需要使 idx 可以通过 array 进行索引。

2] 引入 numpy 以替换 math 以向量化地执行这些操作。

3] 用 idx - mask 技巧替换条件语句。在这种情况下，Python 内部会将 mask 上转换为 int 数组以与 idx 的数据类型匹配。因此，所有的 True 元素变成 1，因此对于 True 元素，我们实际上有 idx-1，这是原始代码中 IF 条件语句的 True 情况。