dalla lista di numeri interi, ottenere il numero più vicino ad un dato valore

Question

Dato un elenco di numeri interi, voglio trovare quale numero è più vicino a un numero dò in ingresso:

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

C'è un modo rapido per fare questo?

Answer 1

Se non siamo sicuri che la lista è ordinata, potremmo usare la built-in min() function, di trovare l'elemento che ha la distanza minima dal numero specificato.

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

noti che funziona anche con dicts con chiavi int, come {1: "a", 2: "b"}. Questo metodo richiede O (n) tempo.

---

Se la lista è già ordinato, o si può pagare il prezzo di ordinare l'array una sola volta, utilizzare il metodo di bisezione illustrato in @Lauritz's answer cui solo prende O (log n) (nota però controllare se un elenco è già ordinato è O (n) e l'ordinamento è O (n log n).)

Answer 2

iterare la lista e confrontare il numero più vicino corrente con 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 

Answer 3

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

un lambda è un modo speciale di scrivere una funzione di "anonymous" (una funzione che non ha un nome) . Puoi assegnargli qualsiasi nome tu voglia perché un lambda è un'espressione.

Il modo più "lungo" di scrivere il quanto sopra sarebbe:

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

Answer 4

Se vuoi dire veloce da eseguire come oppone a quick-to-write, min dovrebbe non essere la vostra arma di scelta, tranne in un caso d'uso molto stretto. La soluzione min deve esaminare ogni numero nell'elenco e eseguire un calcolo per ciascun numero. L'utilizzo di bisect.bisect_left invece è quasi sempre più veloce.

Il "quasi" deriva dal fatto che bisect_left richiede che l'elenco sia ordinato per funzionare. Spero che il tuo caso d'uso sia tale da poter ordinare l'elenco una sola volta e lasciarlo da solo. Anche se non lo è, purché non sia necessario prima di ordinare ogni volta che si chiama takeClosest, è probabile che il modulo bisect esca in cima. Se sei in dubbio, prova entrambi e guarda la differenza nel mondo reale.

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. 
    """ 
    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 funziona ripetutamente dimezzare un elenco e scoprire che la metà myNumber deve essere in guardando il valore medio. Ciò significa che ha un tempo di esecuzione di O (log n) in contrapposizione al tempo di esecuzione O (n) dello highest voted answer. Se mettiamo a confronto i due metodi e forniamo entrambi con un ordinato myList, questi sono i risultati:

 
$ python -m timeit -s " 
from closest import takeClosest 
from random import randint 
a = range(-1000, 1000, 10)" "takeClosest(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 

Quindi, in questo particolare test, bisect è quasi 20 volte più veloce. Per gli elenchi più lunghi, la differenza sarà maggiore.

Cosa succede se livelliamo il campo di gioco rimuovendo il presupposto che deve essere ordinato myList? Diciamo che ordiniamo una copia della lista ogni volta che viene chiamatotakeClosest, lasciando inalterata la soluzione min. Utilizzando l'elenco di 200 voci nel test precedente, la soluzione bisect è ancora la più veloce, anche se solo del 30% circa.

Questo è uno strano risultato, considerando che il passo di smistamento è O (n log (n))! L'unica ragione per cui lo min è ancora in perdita è che l'ordinamento viene eseguito in un codice c ottimizzato, mentre min deve arrangiare chiamando una funzione lambda per ogni elemento. Con lo sviluppo della dimensione myList, la soluzione min sarà più veloce. Si noti che abbiamo dovuto impilare tutto a suo favore per la soluzione min per vincere.

Answer 5

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

    return aux.index(min(aux)) 

Questo codice fornirà l'indice del numero più vicino di Numero nell'elenco.

La soluzione data dalla KennyTM è il migliore in assoluto, ma nei casi non è possibile utilizzare esso (come Brython), questa funzione farà il lavoro

Answer 6

E 'importante notare che l'idea suggerimento di Lauritz di utilizzare bisect non lo fa in realtà trova il valore più vicino in MyList a MyNumber. Invece, bisect trova il valore successivo in ordina dopo MyNumber in MyList. Quindi, nel caso del PO si sarebbe effettivamente ottenere la posizione di 44 ha restituito invece che la posizione del 4.

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

Per ottenere il valore che è più vicino a 5 si potrebbe provare a convertire l'elenco in un array e utilizzando argmin da numpy così.

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

Non so quanto veloce sarebbe, però, la mia ipotesi sarebbe "non molto".

Answer 7

Espansione della risposta di Gustavo Lima. La stessa cosa può essere fatta senza creare una lista completamente nuova. I valori nell'elenco possono essere sostituiti con i differenziali man mano che il ciclo FOR avanza.

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.