Ermitteln Sie aus der Liste der Ganzzahlen die Zahl, die einem bestimmten Wert am nächsten kommt

158

Bei einer Liste von ganzen Zahlen möchte ich herausfinden, welche Zahl einer Zahl, die ich bei der Eingabe gebe, am nächsten kommt:

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

Gibt es eine schnelle Möglichkeit, dies zu tun?

Ricky Robinson
quelle
2
Was ist mit der Rückgabe des Index, dass dies in der Liste passiert ist?
Charlie Parker
1
@ sancho.s Schön entdeckt. Obwohl die Antworten auf diese Frage viel besser sind als die auf dieser anderen Frage. Also werde ich abstimmen, um das andere als Duplikat dieses zu schließen.
Jean-François Corbett

Antworten:

325

Wenn wir nicht sicher sind, ob die Liste sortiert ist, können wir die integrierte min()Funktion verwenden , um das Element zu finden, das den Mindestabstand von der angegebenen Anzahl hat.

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

Beachten Sie, dass es auch mit Diktaten mit int-Tasten funktioniert, wie z {1: "a", 2: "b"}. Diese Methode benötigt O (n) Zeit.


Wenn die Liste bereits sortiert ist oder Sie den Preis für das Sortieren des Arrays nur einmal bezahlen können, verwenden Sie die in @ Lauritz 'Antwort dargestellte Halbierungsmethode, die nur O (log n) Zeit benötigt (beachten Sie jedoch, dass die Überprüfung, ob eine Liste bereits sortiert ist, O ist (n) und Sortieren ist O (n log n).)

kennytm
quelle
13
In der Komplexität ist dies der Punkt O(n), an dem Sie durch ein wenig Hacken bisecteine massive Verbesserung erzielen O(log n)(wenn Ihr Eingabearray sortiert ist).
mic_e
5
@mic_e: Das ist nur Lauritz 'Antwort .
Kennytm
3
Was ist mit der Rückgabe des Index, dass dies in der Liste passiert ist?
Charlie Parker
@CharlieParker Erstellen Sie Ihre eigene Implementierung von min, führen Sie sie über ein Dictionary ( items()) anstelle einer Liste aus und geben Sie am Ende den Schlüssel anstelle des Werts zurück.
Dustin Oprea
2
Oder verwenden Sie numpy.argminanstelle von min, um den Index anstelle des Werts abzurufen.
148

Ich werde die Funktion umbenennen take_closest, um sie den PEP8-Namenskonventionen anzupassen.

Wenn Sie schnell ausführen und nicht schnell schreiben möchten, minsollte dies nicht die Waffe Ihrer Wahl sein, außer in einem sehr engen Anwendungsfall. Die minLösung muss jede Zahl in der Liste untersuchen und für jede Zahl eine Berechnung durchführen. Mit bisect.bisect_leftstattdessen ist fast immer schneller.

Das "fast" kommt von der Tatsache, bisect_leftdass die Liste sortiert werden muss, um zu funktionieren. Hoffentlich ist Ihr Anwendungsfall so, dass Sie die Liste einmal sortieren und dann in Ruhe lassen können. Selbst wenn nicht, solange Sie nicht vor jedem Anruf sortieren müssen take_closest, wird das bisectModul wahrscheinlich die Nase vorn haben. Wenn Sie Zweifel haben, versuchen Sie beides und sehen Sie sich den Unterschied in der realen Welt an.

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 halbiert wiederholt eine Liste und ermittelt myNumberanhand des Mittelwerts , in welcher Hälfte sich die Hälfte befinden muss. Dies bedeutet, dass es eine Laufzeit von O (log n) hat, im Gegensatz zur Laufzeit von O (n) der Antwort mit der höchsten Abstimmung . Wenn wir die beiden Methoden vergleichen und beide sortiert liefern myList, sind dies die Ergebnisse:

$ python -m timeit -s "
vom nächsten Import take_closest
von zufälligen Import Randint
a = Bereich (-1000, 1000, 10) take_closest (a, randint (-1100, 1100))

100000 Schleifen, am besten 3: 2,22 usec pro Schleife

$ python -m timeit -s "
vom nächsten Import mit_min
von zufälligen Import Randint
a = Bereich (-1000, 1000, 10) with_min (a, Randint (-1100, 1100))

10000 Schleifen, am besten 3: 43,9 usec pro Schleife

Also in diesem speziellen Test bisectist fast 20 mal schneller. Bei längeren Listen ist der Unterschied größer.

Was ist, wenn wir das Spielfeld ausgleichen, indem wir die myListzu sortierende Voraussetzung entfernen ? Nehmen wir an, wir sortieren bei jedem take_closest Aufruf eine Kopie der Liste , während die minLösung unverändert bleibt . Unter Verwendung der 200-Punkte-Liste im obigen Test ist die bisectLösung immer noch die schnellste, wenn auch nur um etwa 30%.

Dies ist ein seltsames Ergebnis, wenn man bedenkt, dass der Sortierschritt O (n log (n)) ist ! Der einzige Grund, der minimmer noch verloren geht, ist, dass die Sortierung minin hochoptimiertem c-Code erfolgt, während für jedes Element eine Lambda-Funktion aufgerufen werden muss. Mit myListzunehmender Größe wird die minLösung möglicherweise schneller. Beachten Sie, dass wir alles zu seinen Gunsten stapeln mussten, damit die minLösung gewinnt.

Lauritz V. Thaulow
quelle
2
Das Sortieren selbst benötigt O (N log N), daher ist es langsamer, wenn N groß wird. Wenn Sie zum Beispiel verwenden, werden Sie a=range(-1000,1000,2);random.shuffle(a)feststellen, dass takeClosest(sorted(a), b)dies langsamer wird.
Kennytm
3
@KennyTM Das werde ich dir gewähren und in meiner Antwort darauf hinweisen. Solange getClosestjedoch für jede Sorte mehr als einmal aufgerufen werden kann, ist dies schneller, und für den Anwendungsfall "Einmal sortieren" ist dies ein Kinderspiel.
Lauritz V. Thaulow
Was ist mit der Rückgabe des Index, dass dies in der Liste passiert ist?
Charlie Parker
Wenn myListist schon eine np.arraydann Verwendung np.searchsortedanstelle von bisectist schneller.
Michael Hall
8
>>> takeClosest = lambda num,collection:min(collection,key=lambda x:abs(x-num))
>>> takeClosest(5,[4,1,88,44,3])
4

Ein Lambda ist eine spezielle Art, eine "anonyme" Funktion zu schreiben (eine Funktion, die keinen Namen hat). Sie können ihm einen beliebigen Namen zuweisen, da ein Lambda ein Ausdruck ist.

Die "lange" Art, das Obige zu schreiben, wäre:

def takeClosest(num,collection):
   return min(collection,key=lambda x:abs(x-num))
Burhan Khalid
quelle
2
Beachten Sie jedoch, dass gemäß PEP 8 davon abgeraten wird, Lambdas Namen zuzuweisen .
Evert Heylen