Предположим, у меня есть некий список 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 элементов.
x
иy
? Циклы и проверка будут полиномиальной сложности, что не очень хорошо. Если производительность важна, вы, вероятно, могли бы улучшить ее с помощью дерева интервалов. - person wim   schedule 18.07.2018x
, пока вы не найдете элементe
больше, чем текущий элемент вy
, а затем выбрать более близкий из двух (e
или элемент, который следует за ним). Продолжайте с этой позиции вx
, пока не будут обработаны всеy
, что-то вроде сортировки слиянием. - person Dillon Davis   schedule 19.07.2018x
,y
? - person Azat Ibrakov   schedule 19.07.2018y
, весь списокx
определяется заранее. - person Tendero   schedule 19.07.2018