Gibt es eine Bibliotheksfunktion, die eine binäre Suche in einer Liste / einem Tupel durchführt und die Position des Elements zurückgibt, wenn es gefunden wird, und 'False' (-1, None, etc.), wenn nicht?
Ich habe die Funktionen bisect_left / right im bisect-Modul gefunden , aber sie geben immer noch eine Position zurück, auch wenn das Element nicht in der Liste enthalten ist. Das ist für den beabsichtigten Gebrauch vollkommen in Ordnung, aber ich möchte nur wissen, ob ein Element in der Liste enthalten ist oder nicht (ich möchte nichts einfügen).
Ich habe darüber nachgedacht, zu verwenden bisect_left
und dann zu überprüfen, ob das Element an dieser Position dem entspricht, was ich suche, aber das scheint umständlich zu sein (und ich muss auch Grenzen prüfen, ob die Anzahl größer sein kann als die größte Zahl in meiner Liste). Wenn es eine schönere Methode gibt, würde ich gerne davon erfahren.
Bearbeiten Um zu verdeutlichen, wofür ich dies benötige: Ich bin mir bewusst, dass ein Wörterbuch dafür sehr gut geeignet wäre, aber ich versuche, den Speicherverbrauch so gering wie möglich zu halten. Meine beabsichtigte Verwendung wäre eine Art Doppel-Nachschlagetabelle. Ich habe in der Tabelle eine Liste von Werten und muss in der Lage sein, auf die Werte basierend auf ihrem Index zuzugreifen. Außerdem möchte ich in der Lage sein, den Index eines bestimmten Werts oder None zu finden, wenn der Wert nicht in der Liste enthalten ist.
Die Verwendung eines Wörterbuchs hierfür wäre der schnellste Weg, würde jedoch den Speicherbedarf (ungefähr) verdoppeln.
Ich habe diese Frage gestellt, weil ich dachte, ich hätte etwas in den Python-Bibliotheken übersehen. Es scheint, dass ich meinen eigenen Code schreiben muss, wie Moe vorgeschlagen hat.
quelle
np.searchsorted
ist dies nützlich. docs.scipy.org/doc/numpy/reference/generated/…Antworten:
quelle
if hi is None: hi = len(a)
Schauen Sie sich den Code für bisect_left / right an und passen Sie ihn an Ihren Zweck an.
so was:
quelle
hi = mid - 1
in der seinelif
?hi = mid
zuhi = mid-1
undhi = len(a)
zuhi = len(a)-1
undwhile lo < hi:
zu ändernwhile lo <= hi
, und es wäre gleichwertig korrektbisect.bisect_left()
eher als diese verwenden.Dies ist ein wenig abseits des Themas (da Moes Antwort auf die Frage des OP vollständig zu sein scheint), aber es könnte sich lohnen, die Komplexität Ihres gesamten Verfahrens von Ende zu Ende zu betrachten. Wenn Sie etwas in einer sortierten Liste speichern (wo eine binäre Suche hilfreich wäre) und dann nur auf Existenz prüfen, entsteht etwas (im schlimmsten Fall, sofern nicht anders angegeben):
Sortierte Listen
Während mit einem
set()
, Sie entstehenEine sortierte Liste bringt Ihnen wirklich "nächste", "vorherige" und "Bereiche" (einschließlich Einfügen oder Löschen von Bereichen), die bei einem Startindex O (1) oder O (| Bereich |) sind. Wenn Sie diese Art von Vorgängen nicht häufig verwenden, ist das Speichern als Sets und das Sortieren für die Anzeige insgesamt möglicherweise besser.
set()
In Python entsteht nur sehr wenig zusätzlicher Aufwand.quelle
Es könnte erwähnenswert sein, dass die bisect-Dokumente jetzt Suchbeispiele enthalten: http://docs.python.org/library/bisect.html#searching-sorted-lists
(Das Erhöhen von ValueError anstelle von -1 oder None ist pythonischer - list.index () tut dies zum Beispiel. Aber natürlich können Sie die Beispiele an Ihre Bedürfnisse anpassen.)
quelle
Am einfachsten ist es, die Halbierung zu verwenden und eine Position zurück zu überprüfen , um festzustellen , ob der Gegenstand vorhanden ist:
quelle
Dies ist direkt aus dem Handbuch:
http://docs.python.org/2/library/bisect.html
8.5.1. Suche nach sortierten Listen
Die obigen bisect () -Funktionen sind nützlich, um Einfügepunkte zu finden, können jedoch für allgemeine Suchaufgaben schwierig oder umständlich zu verwenden sein. Die folgenden fünf Funktionen zeigen, wie Sie sie in Standard-Lookups für sortierte Listen umwandeln können:
Mit der geringfügigen Änderung sollte Ihr Code also sein:
quelle
Ich bin damit einverstanden, dass die Antwort von @ DaveAbrahams mit dem Halbierungsmodul der richtige Ansatz ist. In seiner Antwort erwähnte er kein wichtiges Detail.
Aus den Dokumenten
bisect.bisect_left(a, x, lo=0, hi=len(a))
Das Halbierungsmodul erfordert nicht, dass das Sucharray vorab berechnet wird. Sie können die Endpunkte einfach
bisect.bisect_left
mit den Standardeinstellungen von0
und präsentierenlen(a)
.Noch wichtiger für meine Verwendung ist die Suche nach einem Wert X, so dass der Fehler einer bestimmten Funktion minimiert wird. Dazu brauchte ich eine Möglichkeit, dass der Algorithmus von bisect_left stattdessen meine Berechnung aufruft. Das ist wirklich einfach.
Geben Sie einfach ein Objekt an, das definiert
__getitem__
alsa
Zum Beispiel könnten wir den Halbierungsalgorithmus verwenden, um eine Quadratwurzel mit beliebiger Genauigkeit zu finden!
quelle
scipy.optimize
dazu.Wenn Sie nur sehen möchten, ob es vorhanden ist, versuchen Sie, die Liste in ein Diktat umzuwandeln:
Auf meinem Computer dauerte "wenn n in l" 37 Sekunden, während "wenn n in d" 0,4 Sekunden dauerte.
quelle
Dieser ist:
quelle
Die Lösung von Dave Abrahams ist gut. Obwohl ich es minimalistisch gemacht hätte:
quelle
Während es in Python keinen expliziten binären Suchalgorithmus gibt, gibt es ein Modul
bisect
, mit dem die Einfügemarke für ein Element in einer sortierten Liste mithilfe einer binären Suche ermittelt werden kann. Dies kann dazu gebracht werden, eine binäre Suche durchzuführen. Der größte Vorteil davon ist der gleiche Vorteil, den der meiste Bibliothekscode hat - er ist leistungsstark, gut getestet und funktioniert einfach (insbesondere die erfolgreiche Implementierung von Binärsuchen kann recht schwierig sein - insbesondere, wenn Randfälle nicht sorgfältig werden).Grundtypen
Für Grundtypen wie Strings oder Ints ist es ziemlich einfach - alles, was Sie brauchen, ist das
bisect
Modul und eine sortierte Liste:Sie können dies auch verwenden, um Duplikate zu finden:
Natürlich können Sie bei Bedarf auch nur den Index und nicht den Wert an diesem Index zurückgeben.
Objekte
Bei benutzerdefinierten Typen oder Objekten sind die Dinge etwas schwieriger: Sie müssen sicherstellen, dass umfangreiche Vergleichsmethoden implementiert werden, damit die Halbierung korrekt verglichen werden kann.
Dies sollte mindestens in Python 2.7 -> 3.3 funktionieren
quelle
Wenn Sie ein Diktat verwenden, möchten Sie Ihren Speicherbedarf nicht verdoppeln, es sei denn, die von Ihnen gespeicherten Objekte sind wirklich winzig, da die Werte nur Zeiger auf die tatsächlichen Objekte sind:
In diesem Beispiel wird 'foo' nur einmal gespeichert. Macht das einen Unterschied für Sie? Und über wie viele Dinge sprechen wir überhaupt?
quelle
Dieser Code arbeitet rekursiv mit Ganzzahllisten. Sucht nach dem einfachsten Szenario: Listenlänge kleiner als 2. Dies bedeutet, dass die Antwort bereits vorhanden ist und ein Test durchgeführt wird, um die richtige Antwort zu finden. Wenn nicht, wird ein mittlerer Wert eingestellt und auf die Richtigkeit geprüft. Wenn dies nicht der Fall ist, wird die Halbierung durchgeführt, indem die Funktion erneut aufgerufen wird, der mittlere Wert jedoch als obere oder untere Grenze festgelegt wird, indem er nach links oder rechts verschoben wird
quelle
Schauen Sie sich die Beispiele auf Wikipedia an: http://en.wikipedia.org/wiki/Binary_search_algorithm
quelle
Ich denke, das ist viel besser und effektiver. bitte korrigiere mich :). Danke dir
quelle
s
ist eine Liste.binary(s, 0, len(s) - 1, find)
ist der erste Anruf.Die Funktion gibt einen Index des abgefragten Elements zurück. Wenn es keinen solchen Artikel gibt, wird er zurückgegeben
-1
.quelle
quelle
Binäre Suche :
// Um die obige Funktion aufzurufen, benutze:
quelle
Ich brauchte eine binäre Suche in Python und generisch für Django-Modelle. In Django-Modellen kann ein Modell einen Fremdschlüssel für ein anderes Modell haben, und ich wollte eine Suche nach den abgerufenen Modellobjekten durchführen. Ich habe folgende Funktion geschrieben, die Sie verwenden können.
quelle
Viele gute Lösungen oben, aber ich habe keine einfache (KISS halte es einfach (weil ich bin) dumme Verwendung der in Python eingebauten / generischen Halbierungsfunktion gesehen, um eine binäre Suche durchzuführen. Mit ein bisschen Code um die Halbierungsfunktion herum, Ich glaube, ich habe unten ein Beispiel, in dem ich alle Fälle auf ein kleines String-Array von Namen getestet habe. Einige der oben genannten Lösungen spielen darauf an / sagen dies, aber hoffentlich hilft der einfache Code unten jedem, der so verwirrt ist wie ich.
Python-Halbierung wird verwendet, um anzugeben, wo ein neuer Wert / ein neues Suchelement in eine sortierte Liste eingefügt werden soll. Der folgende Code verwendet bisect_left, der den Index des Treffers zurückgibt, wenn das Suchelement in der Liste / im Array gefunden wird. (Beachten Sie, dass bisect und bisect_right den Index des Elements nach dem Treffer oder der Übereinstimmung als Einfügemarke zurückgeben.) Wenn nicht gefunden , bisect_left gibt einen Index zum nächsten Element in der sortierten Liste zurück, der den Suchwert nicht ==. Der einzige andere Fall ist, wo das Suchelement am Ende der Liste steht, wo der zurückgegebene Index über dem Ende der Liste / des Arrays liegt und was im Code unter dem frühen Beenden von Python mit "und" Logikhandles. (erste Bedingung False Python überprüft keine nachfolgenden Bedingungen)
quelle