将列表中的每个数字四舍五入到另一个列表中最接近的数字
Round each number of list to most near number in another list
假设我有一个包含数字的特定列表 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 个元素。
您可以使用 lambda 函数和列表理解快速完成此操作:
[min(x, key=lambda x:abs(x-a)) for a in y]
这将适用于浮点数、整数等。
所以这是我快速编造的东西,只是获取所有差异,然后将它们从最小到最大排序。取最低的差异,然后从那里开始。
x = [1, 2, 3, 4, 5]
y = [1.1, 1.2, 3.6, 6.2, 2.1]
for y_index in range(len(y)):
value_and_index= {}
for x_index in range(len(x)):
difference= y[y_index]-x[x_index]
difference= difference*-1 if difference<0 else difference
value_and_index[difference]= x_index
y[y_index]= x[value_and_index[sorted(value_and_index.keys())[0]]]
print y # [1, 1, 4, 5, 2]
希望这对您有所帮助,编码愉快!
我的尝试:
首先我对 X 数组进行排序(如果它尚未排序)。循环遍历每个 y 并计算每个 x 的绝对值,直到这个绝对值高于之前的值,然后停止 for 循环(因为数组 X 已排序):
x = sorted([1, 2, 3, 4, 5])
y = [1.1, 1.2, 3.6, 6.2, 2.1]
out = []
while y:
current_value = y.pop()
current_min = float('inf')
current_x_value = None
for v in x:
temp_min = abs(current_value - v)
if temp_min < current_min:
current_min = temp_min
current_x_value = v
if temp_min > current_min: # no need to iterate further, X is sorted
break
out.insert(0, current_x_value)
print(out)
输出:
[1, 1, 4, 5, 2]
鉴于 x
已排序,最有效的方法是使用 bisect
搜索最接近的值。只需在 x 值和 运行 平分这些值之间创建一个中点列表:
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
或在 mid_points
计算中使用 float(x1+x2)/2
)
如果x
排序,使用bisect:
import bisect
test_out=[]
max_x=max(x)
min_x=min(x)
for f in y:
if f>=max_x:
idx=-1
elif f<=min_x:
idx=0
else:
idx=bisect.bisect_left(x,f)
if abs(x[idx-1]-f)<abs(x[idx]-f):
idx-=1
test_out.append(x[idx])
>>> test_out==desired_output
True
下一个假设:
结果顺序无关紧要,
我们正在使用 Python 3.3+.
非常简单的解决方案可能看起来像
from itertools import repeat
def evaluate(expected_values, measurements):
if not expected_values:
raise ValueError('Expected values should be a non-empty sequence.')
expected_values = sorted(expected_values)
measurements = sorted(measurements)
expected_iter = iter(expected_values)
left_value = next(expected_iter)
try:
right_value = next(expected_iter)
except StopIteration:
# there is only one expected value
yield from repeat(left_value,
len(measurements))
return
for evaluated_count, measurement in enumerate(measurements):
while measurement > right_value:
try:
left_value, right_value = right_value, next(expected_iter)
except StopIteration:
# rest of the measurements are closer to max expected value
yield from repeat(right_value,
len(measurements) - evaluated_count)
return
def key(expected_value):
return abs(expected_value - measurement)
yield min([left_value, right_value],
key=key)
对于Python3.3-我们可以替换
yield from repeat(object_, times)
with for
-loop like
for _ in range(times):
yield object_
测试
>>> 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, 7.6, 10.4]
>>> y_out = list(evaluate(x_in, y_in))
>>> y_out
[1.1, 1.1, 1.1, 2.2, 2.2, 3, 4, 6.2, 6.2, 6.2, 6.2, 6.2]
假设我有一个包含数字的特定列表 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 个元素。
您可以使用 lambda 函数和列表理解快速完成此操作:
[min(x, key=lambda x:abs(x-a)) for a in y]
这将适用于浮点数、整数等。
所以这是我快速编造的东西,只是获取所有差异,然后将它们从最小到最大排序。取最低的差异,然后从那里开始。
x = [1, 2, 3, 4, 5]
y = [1.1, 1.2, 3.6, 6.2, 2.1]
for y_index in range(len(y)):
value_and_index= {}
for x_index in range(len(x)):
difference= y[y_index]-x[x_index]
difference= difference*-1 if difference<0 else difference
value_and_index[difference]= x_index
y[y_index]= x[value_and_index[sorted(value_and_index.keys())[0]]]
print y # [1, 1, 4, 5, 2]
希望这对您有所帮助,编码愉快!
我的尝试:
首先我对 X 数组进行排序(如果它尚未排序)。循环遍历每个 y 并计算每个 x 的绝对值,直到这个绝对值高于之前的值,然后停止 for 循环(因为数组 X 已排序):
x = sorted([1, 2, 3, 4, 5])
y = [1.1, 1.2, 3.6, 6.2, 2.1]
out = []
while y:
current_value = y.pop()
current_min = float('inf')
current_x_value = None
for v in x:
temp_min = abs(current_value - v)
if temp_min < current_min:
current_min = temp_min
current_x_value = v
if temp_min > current_min: # no need to iterate further, X is sorted
break
out.insert(0, current_x_value)
print(out)
输出:
[1, 1, 4, 5, 2]
鉴于 x
已排序,最有效的方法是使用 bisect
搜索最接近的值。只需在 x 值和 运行 平分这些值之间创建一个中点列表:
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
或在 mid_points
计算中使用 float(x1+x2)/2
)
如果x
排序,使用bisect:
import bisect
test_out=[]
max_x=max(x)
min_x=min(x)
for f in y:
if f>=max_x:
idx=-1
elif f<=min_x:
idx=0
else:
idx=bisect.bisect_left(x,f)
if abs(x[idx-1]-f)<abs(x[idx]-f):
idx-=1
test_out.append(x[idx])
>>> test_out==desired_output
True
下一个假设:
结果顺序无关紧要,
我们正在使用 Python 3.3+.
非常简单的解决方案可能看起来像
from itertools import repeat
def evaluate(expected_values, measurements):
if not expected_values:
raise ValueError('Expected values should be a non-empty sequence.')
expected_values = sorted(expected_values)
measurements = sorted(measurements)
expected_iter = iter(expected_values)
left_value = next(expected_iter)
try:
right_value = next(expected_iter)
except StopIteration:
# there is only one expected value
yield from repeat(left_value,
len(measurements))
return
for evaluated_count, measurement in enumerate(measurements):
while measurement > right_value:
try:
left_value, right_value = right_value, next(expected_iter)
except StopIteration:
# rest of the measurements are closer to max expected value
yield from repeat(right_value,
len(measurements) - evaluated_count)
return
def key(expected_value):
return abs(expected_value - measurement)
yield min([left_value, right_value],
key=key)
对于Python3.3-我们可以替换
yield from repeat(object_, times)
with for
-loop like
for _ in range(times):
yield object_
测试
>>> 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, 7.6, 10.4]
>>> y_out = list(evaluate(x_in, y_in))
>>> y_out
[1.1, 1.1, 1.1, 2.2, 2.2, 3, 4, 6.2, 6.2, 6.2, 6.2, 6.2]