将每个列表的数量舍入到另一个列表中最接近的数字

Question

假设我有一个x带有数字的特定列表,另一个y带有其他数字的列表.元素y应该是元素x,但由于测量中的噪声,它们有点不同.我想找到,对于每个值y,它的值x最接近它.

我可以通过一些循环来检查,并检查每个元素y[i],哪个元素x[j]最小化abs(x[j]-y[i]),但我很确定有一个更容易,更简洁的方法来做到这一点.列表可能很大,所以我在这里寻找有效的代码.

我到目前为止编写的代码是:

x_in = [1.1, 2.2, 3, 4, 6.2]
y_in = [0.9, 2, 1.9, 6, 5, 6, 6.2, 0.5, 0, 3.1]
desired_output = [1.1, 2.2, 2.2, 6.2, 4, 6.2, 6.2, 1.1, 1.1, 3]

y_out = []

for y in y_in:
    aux = [abs(l - y) for l in x_in]
    mn,idx = min( (aux[i],i) for i in range(len(aux)) )
    y_out.append(x_in[idx])

>>> y_out == desired_output
True

但我不知道是否有更有效的方法来做到这一点......

编辑:

由于我的无知,我忘了根据我收到的评论澄清一些可能相关的内容.

• 该x列表进行排序.
• x唯一可以具有相当大尺寸的列表:一般来说,在500,000到1,000,000个元素之间.y通常会非常小,少于10个元素.

Answer 1

鉴于已x排序，最有效的方法是bisect搜索最接近的值。只需创建 x 值之间的中点列表并对其运行 bisect：

In [69]: mid_points = [(x1+x2)/2 for x1, x2 in zip(x[1:], x[:-1])]

In [70]: mid_points
Out[70]: [1.5, 2.5, 3.5, 4.5]

In [72]: [x[bisect.bisect(mid_points, v)] for v in y]
Out[72]: [1, 1, 4, 5, 2]

O(Mlog(N)+N)这将在 `M=len(y), N=len(x) 的时间运行

（对于python2做或在计算中from __future__ import division使用）float(x1+x2)/2mid_points