webentwicklung-frage-antwort-db.com.de

Wo wird die binäre Suche in der Praxis eingesetzt?

Jedem Programmierer wird beigebracht, dass die binäre Suche eine gute und schnelle Möglichkeit ist, eine geordnete Liste von Daten zu durchsuchen. Es gibt viele Beispiele für die Verwendung der binären Suche in Spielzeugbüchern, aber was ist mit der realen Programmierung: Wo wird die binäre Suche tatsächlich in realen Programmen verwendet?

25
tjdonaldson

Die binäre Suche wird überall verwendet. Nehmen Sie eine sortierte Sammlung aus einer beliebigen Sprachbibliothek (Java, .NET, C++ STL usw.), und alle verwenden die Binärsuche (oder haben die Option, sie zu verwenden), um Werte zu finden. Es stimmt zwar, dass Sie es nur selten implementieren müssen, Sie müssen jedoch die dahinter stehenden Prinzipien verstehen, um sie nutzen zu können.

26
Grey Panther

Die binäre Suche kann verwendet werden, um schnell auf bestellte Daten zuzugreifen wenn der Speicherplatz knapp ist . Angenommen, Sie möchten eine Menge von 100.000 32-Bit-Ganzzahlen in einer durchsuchbaren, geordneten Datenstruktur speichern, aber Sie werden die Menge nicht häufig ändern. Sie können die Ganzzahlen trivial in einem sortierten Array von 400.000 Bytes speichern, und Sie können die Binärsuche verwenden, um schnell darauf zuzugreifen. Aber wenn Sie sie z. In einem B-Baum, einem RB-Baum oder einer anderen "dynamischeren" Datenstruktur entsteht ein zusätzlicher Speicherbedarf. Zur Veranschaulichung: Wenn Sie die Ganzzahlen in einer beliebigen Baumart speichern, in der Sie untergeordnete und untergeordnete Zeiger links und rechts haben, belegen Sie mindestens 1.200.000 Byte Speicher (unter der Annahme einer 32-Bit-Speicherarchitektur). Sicher, es gibt Optimierungen, die Sie durchführen können, aber so funktioniert es im Allgemeinen.

Da es sehr langsam ist, ein geordnetes Array zu aktualisieren (Einfügen oder Löschen), ist die binäre Suche nicht sinnvoll, wenn sich das Array häufig ändert.

Hier einige praktische Beispiele, bei denen ich die binäre Suche verwendet habe:

  • Implementieren eines "switch () ... case:" - Konstrukts in einer virtuellen Maschine, in der die case-Bezeichnungen einzelne Ganzzahlen sind. Wenn Sie 100 Fälle haben, können Sie den richtigen Eintrag in 6 bis 7 Schritten mithilfe der binären Suche finden, wobei als Folge bedingter Verzweigungen im Durchschnitt 50 Vergleiche erforderlich sind.
  • Schnelle Suche nach Teilzeichenfolgen mithilfe von Suffix-Arrays, die alle Suffixe des Satzes durchsuchbarer Zeichenfolgen in lexiografischer Reihenfolge enthalten (ich wollte Speicher sparen und die Implementierung einfach halten)
  • Suche nach numerischen Lösungen für eine Gleichung (wenn Sie faul sind und keine Lust haben, Newtons Methode zu implementieren)
19
Antti Huima

Jeder Programmierer muss wissen, wie beim Debuggen die Binärsuche verwendet wird.

Wenn Sie ein Programm haben und wissen, dass ein Fehler zu einem bestimmten Zeitpunkt während der Ausführung des Programms sichtbar ist, können Sie die Binärsuche verwenden, um den Ort zu bestimmen, an dem er tatsächlich auftritt. Dies kann viel schneller sein als das einfache Durchlaufen großer Teile des Codes.

15
user25148

Binäre Suche ist ein guter und schneller Weg!

Vor der Einführung von STL und .NET Framework usw. kam es häufig vor, dass Sie auf Situationen stießen, in denen Sie Ihre eigenen angepassten Auflistungsklassen implementieren mussten. Wann immer ein sortiertes Array ein praktikabler Ort zum Speichern der Daten ist, ist die binäre Suche die Methode, um Einträge in diesem Array zu finden.

Ich bin mir ziemlich sicher, dass die binäre Suche auch heute weit verbreitet ist, obwohl sie von der Bibliothek aus Gründen der Benutzerfreundlichkeit "unter der Haube" behandelt wird.

7
SteinNorheim

Ich habe binäre Suchen in BTree-Implementierungen implementiert.

Die BTree-Suchalgorithmen wurden verwendet, um den nächsten zu lesenden Knotenblock zu finden, aber innerhalb des 4K-Blocks selbst (der eine Anzahl von Schlüsseln basierend auf der Schlüsselgröße enthielt) wurde die binäre Suche verwendet, um entweder die Datensatznummer (für einen Blattknoten) zu finden ) oder den nächsten Block (für einen Nicht-Blattknoten).

Verglichen mit der sequentiellen Suche ist dies verblüffend schnell, da Sie wie bei ausgeglichenen Binärbäumen bei jeder Überprüfung die Hälfte des verbleibenden Suchraums entfernen.

6
paxdiablo

Beantworten Sie Ihre Frage anhand eines praktischen Beispiels.

In der Programmiersprache R gibt es ein Paket data.table . Es ist aus C-implementierten, kurzen Syntax-, Hochleistungserweiterungen für die Datentransformation bekannt. Es wird die binäre Suche verwendet. Auch ohne binäre Suche skaliert es besser als die Konkurrenz.
Benchmark vs Pythonpandas und vs R dplyr finden Sie im Projekt-Wiki Gruppierung 2E9 - zufällige Auftragsdaten.
Es gibt auch Nice Benchmark vs Datenbanken vs BigData Benchm-Datenbanken .

In der aktuellen data.table-Version (1.9.6) wurde die Binärsuche erweitert und kann nun als Index für jede atomare Spalte verwendet werden.

Ich habe gerade eine nette Zusammenfassung gefunden, der ich absolut zustimme - siehe .

Wer R-Vergleiche durchführt, sollte data.table anstelle von data.frame verwenden. Mehr noch für Benchmarks. data.table ist die beste Datenstruktur/Abfragesprache, die ich in meiner Karriere gefunden habe. Es ist führend in der R-Welt und meiner Meinung nach in allen datenorientierten Sprachen.

Also ja, binäre Suche wird verwendet und die Welt ist viel besser dank ihm.

3
jangorecki

Wir verwenden es immer noch häufig in unserem Code, um Tausende von ACLs viele Tausend Male pro Sekunde zu durchsuchen. Dies ist nützlich, da die ACLs statisch sind, sobald sie aus der Datei eingehen, und wir die Kosten für die Vergrößerung des Arrays tragen müssen, wenn wir sie beim Booten hinzufügen. Es ist unglaublich schnell, wenn es mal läuft.

Wenn Sie ein Array mit 255 Elementen in höchstens 7 Vergleichen/Sprüngen durchsuchen können (511 in 8, 1023 in 9 usw.), können Sie feststellen, dass die binäre Suche in etwa so schnell wie möglich ist.

3
Adam Hawes

Ich habe es einmal (ohne zu wissen, dass dies tatsächlich eine binäre Suche ist) für ein GUI-Steuerelement implementiert, das zweidimensionale Daten in einem Diagramm anzeigt. Klicken mit der Maus sollte den Datencursor auf den Punkt mit dem nächsten x-Wert setzen. Bei einer großen Anzahl von Punkten (mehrere 1000, als x86 erst eine CPU-Frequenz von über 100 MHz erreichte) war dies nicht wirklich interaktiv nutzbar - ich führte von Anfang an eine lineare Suche durch. Nach einigem Überlegen kam mir der Gedanke, dass ich das auf eine getrennte und siegreiche Weise angehen könnte. Ich habe einige Zeit gebraucht, um es unter allen Edge-Fällen zum Laufen zu bringen.

Erst einige Zeit später erfuhr ich, dass dies in der Tat ein grundlegender CS-Algorithmus ist ...

3
mghie

Ein Beispiel ist das stl-Set. Die zugrunde liegende Datenstruktur ist ein ausgeglichener binärer Suchbaum, der das Nachschlagen, Einfügen und Löschen in O (log n) aufgrund der binären Suche unterstützt.

Ein weiteres Beispiel ist ein Ganzzahlteilungsalgorithmus, der in der Protokollzeit ausgeführt wird.

2
MrDatabase

Nun, binäre Suche wird jetzt in 99% der 3D-Spiele und -Anwendungen verwendet. Der Raum ist in eine Baumstruktur unterteilt und eine binäre Suche wird verwendet, um herauszufinden, welche Unterteilungen entsprechend einer 3D-Position und einer Kamera angezeigt werden sollen.

Eines seiner ersten größten Schaufenster war Doom. Binäre Bäume und die damit verbundene Suche haben das Rendering verbessert.

2
karlipoppins

Die binäre Suche kann zum Debuggen mit Git verwendet werden. Es heißt Git Bisect .

2
Sanghyun Lee

Unter anderem habe ich einen Interpreter mit einer Tabelle von Befehlsnamen und einem Zeiger auf die Funktion zur Interpretation dieses Befehls. Es gibt ungefähr 60 Befehle. Die Verwendung einer linearen Suche wäre nicht besonders aufwändig, aber ich verwende eine binäre Suche.

1

Die binäre Sortierung ist nützlich, um Schriftarten an die Größe des Texts mit einer konstanten Größe des Textfelds anzupassen

1

Ich hatte ein Programm, das eine Sammlung durchlief, um einige Berechnungen durchzuführen. Ich dachte, dass dies ineffizient ist, also sortierte ich die Sammlung und verwendete dann eine einzelne binäre Suche, um einen Artikel von Interesse zu finden. Ich habe diesen Artikel und die dazugehörigen Nachbarn zurückgegeben. Ich hatte die Sammlung tatsächlich gefiltert.

Dies zu tun war tatsächlich langsamer als die gesamte Sammlung zu durchlaufen und passende Gegenstände herauszufischen.

Ich fügte der Sammlung weiterhin Elemente hinzu, da ich wusste, dass die Sortier- und Suchleistung letztendlich mit der Iteration Schritt halten würde. Es dauerte eine Sammlung von etwa 600 Objekten, bis die Geschwindigkeit identisch war. 1000 Objekte hatten einen deutlichen Leistungsvorteil.

Ich würde auch die Art der Daten berücksichtigen, mit denen Sie arbeiten, die Duplikate und die Verbreitung. Dies wirkt sich auf das Sortieren und Suchen aus.

Meine Antwort ist, beide Methoden auszuprobieren und zeitlich festzulegen.

1
Neil

Es ist die Basis für hg bisect

1
Ken

Halbleitertestprogramme, die zum Messen von digitalen Timing- oder analogen Pegeln verwendet werden, nutzen die binäre Suche in großem Umfang. Automatische Testgeräte (ATE) von Advantest, Teradyne, Verigy und dergleichen können als Wahrheitstabellenprüfgeräte angesehen werden, die Eingangslogik anwenden und Ausgangszustände eines digitalen Teils überprüfen.

Stellen Sie sich ein einfaches Gatter vor, bei dem sich die Eingangslogik zum Zeitpunkt = 0 jedes Zyklus ändert und Xns wechselt, nachdem sich die Eingangslogik geändert hat. Wenn Sie den Ausgang vor T = X takten, stimmt die Logik nicht mit dem erwarteten Wert überein. Strobe nach der Zeit T = X und die Logik stimmt mit dem erwarteten Wert überein. Die binäre Suche wird verwendet, um den Schwellenwert zwischen dem neuesten Wert, mit dem die Logik nicht übereinstimmt, und dem frühesten Teil zu finden, an dem dies der Fall ist. (Ein Teradyne FLEX-System löst das Timing auf eine Auflösung von 39 ps auf, andere Tester sind vergleichbar.) Das ist eine einfache Methode, um die Übergangszeit zu messen. Dieselbe Technik kann verwendet werden, um Rüstzeit, Haltezeit, Betriebsspannungspegel, Spannungsversorgung gegen Verzögerung usw. Zu bestimmen.

Jede Art von Mikroprozessor, Speicher, FPGA, Logik und vielen analogen Mixed-Signal-Schaltkreisen verwendet die binäre Suche beim Testen und Charakterisieren.

-- Mike

1
Mike

Delphi-Anwendungen können die binäre Suche beim Durchsuchen von Zeichenfolgen in der sortierten TStringList nutzen.

0
Michał Niklas

Die binäre Suche bietet eine Funktion, die viele vorgefertigte Karten-/Wörterbuchimplementierungen nicht bieten: das Finden nicht genauer Übereinstimmungen.

Ich habe beispielsweise die binäre Suche verwendet, um Geotagging von Fotos basierend auf GPS-Protokollen zu implementieren: Platzieren Sie alle GPS-Wegpunkte in einem Array, das nach Zeitstempel sortiert ist, und verwenden Sie die binäre Suche, um den Wegpunkt zu identifizieren, der dem Zeitstempel jedes Fotos am nächsten liegt.

0

Ich glaube, dass die .NET SortedDictionary einen binären Baum hinter den Kulissen verwendet (ähnlich wie die STL-Map) ... daher wird eine binäre Suche verwendet, um auf Elemente in der SortedDictionary zuzugreifen.

0
Polaris878

Das Finden der Wurzeln einer Gleichung ist wahrscheinlich eine dieser sehr einfachen Aufgaben, die Sie mit einem sehr einfachen Algorithmus wie der binären Suche ausführen möchten.

0
dirkgently

Die list.sort()-Methode von Python verwendet Timsort , das (AFAIK) die binäre Suche verwendet, um die Positionen von Elementen zu lokalisieren.

0
MAK