z listy liczb całkowitych pobierz liczbę najbliższą podanej wartości

Biorąc pod uwagę listę liczb całkowitych, chcę sprawdzić, która liczba jest najbliższa liczbie podanej w danych wejściowych:

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

Czy można to szybko zrobić?

Jeśli nie jesteśmy pewni, że lista jest sortowana, możemy skorzystać z wbudowanej min()funkcji , aby znaleźć element, który ma minimalną odległość od określonego numeru.

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

Zauważ, że działa również z dyktami z kluczami int, takimi jak {1: "a", 2: "b"}. Ta metoda zajmuje O (n) czasu.

Jeśli lista jest już posortowana lub możesz zapłacić cenę za sortowanie tablicy tylko raz, użyj metody bisekcji zilustrowanej w odpowiedzi @ Lauritza, która zajmuje tylko O ​​(log n) czasu (zwróć jednak uwagę, że sprawdzenie, czy lista jest już posortowana, to O (n) a sortowanie to O (n log n).)

Zmienię nazwę funkcji, take_closestaby była zgodna z konwencjami nazewnictwa PEP8.

Jeśli masz na myśli szybkie wykonanie w przeciwieństwie do szybkiego zapisu, niemin powinno być Twoją ulubioną bronią, z wyjątkiem jednego bardzo wąskiego przypadku użycia. Rozwiązanie musi zbadać każdy numer na liście i wykonać obliczenia dla każdego numeru. Używanie zamiast tego jest prawie zawsze szybsze.minbisect.bisect_left

„Prawie” wynika z faktu, że bisect_leftlista musi być posortowana, aby działała. Mamy nadzieję, że Twój przypadek użycia jest taki, że możesz raz posortować listę, a następnie zostawić ją w spokoju. Nawet jeśli nie, o ile nie musisz sortować danych przed każdym połączeniem take_closest, bisectmoduł prawdopodobnie zajmie pierwsze miejsce. Jeśli masz wątpliwości, spróbuj obu i spójrz na różnicę w świecie rzeczywistym.

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 działa na zasadzie wielokrotnego dzielenia listy na pół i sprawdzania, która połowa myNumbermusi się znaleźć, patrząc na środkową wartość. Oznacza to, że ma czas pracy O (log n) , w przeciwieństwie do O (n) czas pracującym Najwyżej oceniane odpowiedź . Jeśli porównamy te dwie metody i podamy obie z posortowanymi myListwynikami, oto wyniki:

$ python -m timeit -s "
z najbliższego importu take_closest
z losowego importu randint
a = zakres (-1000, 1000, 10) "" take_closest (a, randint (-1100, 1100)) "

100000 pętli, najlepiej 3: 2,22 usek na pętlę

$ python -m timeit -s "
z najbliższego importu z_min
z losowego importu randint
a = zakres (-1000, 1000, 10) "" with_min (a, randint (-1100, 1100)) "

10000 pętli, najlepiej 3: 43,9 usek na pętlę

Więc w tym konkretnym teście bisectjest prawie 20 razy szybszy. W przypadku dłuższych list różnica będzie większa.

A co, jeśli wyrównamy szanse, usuwając warunek wstępny, który myListnależy załatwić? Powiedzmy, że po każdym take_closest wywołaniu sortujemy kopię listy , pozostawiając minniezmienione rozwiązanie. Korzystając z listy 200 pozycji w powyższym teście, bisectrozwiązanie jest nadal najszybsze, choć tylko o około 30%.

Jest to dziwny wynik, biorąc pod uwagę, że krok sortowania to O (n log (n)) ! Jedynym powodem, dla którego minwciąż przegrywa, jest to, że sortowanie odbywa się w wysoce zoptymalizowanym kodzie c, podczas gdy mintrzeba wlecieć w wywołanie funkcji lambda dla każdego elementu. Wraz ze myListwzrostem rozmiaru minrozwiązanie ostatecznie będzie szybsze. Zauważ, że musieliśmy ułożyć wszystko na jego korzyść, aby minrozwiązanie wygrało.

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

Lambda jest specjalny sposób pisania funkcję „anonimowy” (funkcja, która nie ma nazwy). Możesz przypisać mu dowolną nazwę, ponieważ lambda jest wyrażeniem.

„Długie” zapisanie powyższego to:

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

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

    return aux.index(min(aux))

Ten kod daje indeks najbliższej liczby numerów na liście.

Rozwiązanie podane przez KennyTM jest ogólnie najlepsze, ale w przypadkach, gdy nie możesz z niego skorzystać (jak brython), ta funkcja załatwi sprawę

Powtarzaj listę i porównaj aktualną najbliższą liczbę z 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

Ważne jest, aby zauważyć, że pomysł Lauritza dotyczący użycia połowy w rzeczywistości nie znajduje najbliższej wartości w MyList do MyNumber. Zamiast tego funkcja bisect znajduje następną wartość w kolejności po MyNumber w MyList. Tak więc w przypadku OP w rzeczywistości zwrócona zostanie pozycja 44 zamiast pozycji 4.

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

Aby uzyskać wartość najbliższą 5, możesz spróbować przekonwertować listę na tablicę i użyć argmin z numpy w ten sposób.

>>> 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

Nie wiem, jak szybko to by się stało, przypuszczam, że to „niezbyt”.

Rozszerzając odpowiedź Gustavo Limy. To samo można zrobić bez tworzenia zupełnie nowej listy. Wartości na liście można zastąpić różnicami w miarę FORpostępu pętli.

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.

Jeśli mogę dodać do odpowiedzi @ Lauritza

Aby uniknąć błędu uruchamiania, nie zapomnij dodać warunku przed bisect_leftwierszem:

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

więc pełny kod będzie wyglądał następująco:

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