Из списка целых чисел, получить номер, ближайший к данному значению

Ответ 1

Если мы не уверены, что список отсортирован, мы можем использовать встроенную функцию min(), чтобы найти элемент, который имеет минимальное расстояние от указанного числа.

>>> min(myList, key=lambda x:abs(x-myNumber))
4

Обратите внимание, что он также работает с dicts с ключами int, например {1: "a", 2: "b"}. Этот метод принимает время O (n).

Если список уже отсортирован или вы можете заплатить цену за сортировку массива один раз, используйте метод bisection, проиллюстрированный в @Lauritz answer, который принимает только O (log n) (обратите внимание, что проверка того, что список уже отсортирован, равен O (n), а сортировка - O (n log n).)

Ответ 2

Я переименую функцию take_closest в соответствии с соглашениями об именах PEP8.

Если вы имеете в виду "быстрое выполнение", а не "быстрое написание", min не должно быть вашим выбором, за исключением одного очень узкого варианта использования. min решение должно проверить каждое число в списке и сделать расчет для каждого числа. bisect.bisect_left этого использование bisect.bisect_left почти всегда быстрее.

"Почти" происходит из-за того, что bisect_left требует, чтобы список был отсортирован для работы. Надеюсь, ваш вариант использования таков, что вы можете отсортировать список один раз, а затем оставить его в покое. Даже если это не так, если вам не нужно выполнять сортировку перед каждым вызовом take_closest, модуль bisect, скорее всего, выйдет на первое место. Если вы сомневаетесь, попробуйте оба и посмотрите на разницу в реальном мире.

from bisect import bisect_left

def take_closest(myList, myNumber):
    """
    Assumes myList is sorted. Returns closest value to myNumber.

    If two numbers are equally close, return the smallest number.
    """
    pos = bisect_left(myList, myNumber)
    if pos == 0:
        return myList[0]
    if pos == len(myList):
        return myList[-1]
    before = myList[pos - 1]
    after = myList[pos]
    if after - myNumber < myNumber - before:
       return after
    else:
       return before

Bisect работает путем многократного деления списка на два и выяснения, какая половина myNumber должна быть myNumber, посмотрев на среднее значение. Это означает, что у него есть время выполнения O (log n), а не время O (n) ответа с наибольшим количеством голосов. Если мы сравним два метода и myList оба отсортированным myList, это результаты:

$ python -m timeit -s "
from closest import take_closest
from random import randint
a = range(-1000, 1000, 10)" "take_closest(a, randint(-1100, 1100))"

100000 loops, best of 3: 2.22 usec per loop

$ python -m timeit -s "
from closest import with_min
from random import randint
a = range(-1000, 1000, 10)" "with_min(a, randint(-1100, 1100))"

10000 loops, best of 3: 43.9 usec per loop

Таким образом, в этом конкретном тесте bisect работает почти в 20 раз быстрее. Для более длинных списков разница будет больше.

Что если мы myList игровое поле, удалив предварительное условие, что myList должен быть отсортирован? Допустим, мы сортируем копию списка каждый раз, take_closest вызывается take_closest, оставляя min решение без изменений. Используя список из 200 пунктов в приведенном выше тесте, решение для bisect на bisect остается самым быстрым, хотя только на 30%.

Это странный результат, учитывая, что шаг сортировки - O (n log (n)) ! Единственная причина, по которой min по-прежнему проигрывает, заключается в том, что сортировка выполняется в высокооптимизированном коде c, в то время как min приходится выполнять лямбда-функцию для каждого элемента. При myList размера myList min решение в конечном итоге будет быстрее. Обратите внимание, что мы должны были сложить все в его пользу, чтобы min решение.

Ответ 3

>>> takeClosest = lambda num,collection:min(collection,key=lambda x:abs(x-num))
>>> takeClosest(5,[4,1,88,44,3])
4

Лямбда - это особый способ написания "анонимной" функции (функции, у которой нет имени). Вы можете присвоить ему любое имя, которое хотите, потому что лямбда - это выражение.

"Длинный" способ написания вышеупомянутого будет:

def takeClosest(num,collection):
   return min(collection,key=lambda x:abs(x-num))

Ответ 4

def closest(list, Number):
    aux = []
    for valor in list:
        aux.append(abs(Number-valor))

    return aux.index(min(aux))

Этот код предоставит вам индекс ближайшего числа Number в списке.

Решение, данное KennyTM, является лучшим в целом, но в тех случаях, когда вы не можете его использовать (например, brython), эта функция будет выполнять работу

Ответ 5

Перейдите по списку и сравните текущий ближайший номер с abs(currentNumber - myNumber):

def takeClosest(myList, myNumber):
    closest = myList[0]
    for i in range(1, len(myList)):
        if abs(i - myNumber) < closest:
            closest = i
    return closest

Ответ 6

Важно отметить, что идея предложения Lauritz об использовании bisect фактически не находит ближайшего значения в MyList для MyNumber. Вместо этого bisect находит следующее значение после MyNumber в MyList. Таким образом, в случае OP вы фактически получили бы позицию 44, вместо позиции 4.

>>> myList = [1, 3, 4, 44, 88] 
>>> myNumber = 5
>>> pos = (bisect_left(myList, myNumber))
>>> myList[pos]
...
44

Чтобы получить значение, самое близкое к 5, вы можете попробовать преобразовать список в массив и использовать argmin из numpy, как это.

>>> import numpy as np
>>> myNumber = 5   
>>> myList = [1, 3, 4, 44, 88] 
>>> myArray = np.array(myList)
>>> pos = (np.abs(myArray-myNumber)).argmin()
>>> myArray[pos]
...
4

Я не знаю, как быстро это будет, но думаю, что "не очень".

Ответ 7

Расширение ответа Густаво Лимы. То же самое можно сделать и без создания совершенно нового списка. Значения в списке могут быть заменены дифференциалами по мере прохождения цикла FOR.

def f_ClosestVal(v_List, v_Number):
"""Takes an unsorted LIST of INTs and RETURNS INDEX of value closest to an INT"""
for _index, i in enumerate(v_List):
    v_List[_index] = abs(v_Number - i)
return v_List.index(min(v_List))

myList = [1, 88, 44, 4, 4, -2, 3]
v_Num = 5
print(f_ClosestVal(myList, v_Num)) ## Gives "3," the index of the first "4" in the list.

Ответ 8

Если я могу добавить к ответу @Lauritz

Чтобы не было ошибки запуска, не забудьте добавить условие перед bisect_left:

if (myNumber > myList[-1] or myNumber < myList[0]):
    return False

поэтому полный код будет выглядеть так:

from bisect import bisect_left

def takeClosest(myList, myNumber):
    """
    Assumes myList is sorted. Returns closest value to myNumber.
    If two numbers are equally close, return the smallest number.
    If number is outside of min or max return False
    """
    if (myNumber > myList[-1] or myNumber < myList[0]):
        return False
    pos = bisect_left(myList, myNumber)
    if pos == 0:
            return myList[0]
    if pos == len(myList):
            return myList[-1]
    before = myList[pos - 1]
    after = myList[pos]
    if after - myNumber < myNumber - before:
       return after
    else:
       return before