wake-up-neo.com

Warum binäre Suche verwenden, wenn es ternäre Suche gibt?

Ich habe kürzlich von der ternären Suche gehört, bei der wir ein Array in drei Teile aufteilen und vergleichen. Hier wird es zwei Vergleiche geben, aber es reduziert das Array auf n/3. Warum nutzen die Leute nicht so viel?

39
mousey

Tatsächlich verwenden Leute k-ary Bäume für beliebiges k.

Dies ist jedoch ein Kompromiss.

Um ein Element in einem k-ary-Baum zu finden, benötigen Sie ungefähr k * ln (N)/ln (k) -Operationen (denken Sie an die Basisänderungsformel). Je größer Ihr k ist, desto mehr Operationen benötigen Sie insgesamt.

Die logische Erweiterung dessen, was Sie sagen, lautet: "Warum verwenden Leute keinen N-ary-Baum für N Datenelemente?". Was natürlich ein Array wäre.

41
Borealid

Bei einer ternären Suche erhalten Sie immer noch dieselbe asymptotische Komplexität O (log N) Suchzeit und erhöhen die Komplexität der Implementierung.

Dasselbe Argument lässt sich sagen, warum Sie keine Quad-Suche oder eine andere höhere Ordnung wünschen.

26
Akusete

Das Durchsuchen von 1 Milliarde (eine Milliarde US-Dollar - 1.000.000.000) sortierter Elemente würde durchschnittlich 15 Vergleiche mit der binären Suche und 9 Vergleiche mit einer ternären Suche erfordern - kein großer Vorteil. Beachten Sie, dass jeder "ternäre Vergleich" zwei tatsächliche Vergleiche beinhalten kann.

25
Michael Burr

Beeindruckend. Ich denke, die am besten bewerteten Antworten vermissen das Boot.

Ihre CPU unterstützt die ternäre Logik nicht als Einzeloperation. es teilt die ternäre Logik in mehrere Schritte der binären Logik auf. Der optimalste Code für die CPU ist die binäre Logik. Wenn Chips üblich waren, die ternäre Logik als Einzeloperation unterstützten, hätten Sie recht.

B-Bäume können an jedem Knoten mehrere Zweige haben. Ein Ordnung-3-B-Baum ist eine ternäre Logik. Jeder Schritt in der Baumstruktur erfordert zwei Vergleiche statt eines, und dies führt wahrscheinlich zu einer langsameren CPU-Zeit. 

B-Bäume sind jedoch ziemlich häufig. Wenn Sie davon ausgehen, dass jeder Knoten in der Struktur an einem anderen Ort auf der Festplatte gespeichert wird, verbringen Sie die meiste Zeit damit, von der Festplatte zu lesen ... und die CPU ist kein Engpass, aber die Festplatte wird es sein. Sie nehmen also einen B-Baum mit 100.000 Kindern pro Knoten, oder was sonst noch kaum in einen Speicherblock passt. B-Bäume mit einem solchen Verzweigungsfaktor würden selten mehr als drei Knoten hoch sein, und Sie hätten nur drei Plattenlesevorgänge - drei Stopps an einem Engpass -, um einen riesigen, riesigen Datensatz zu durchsuchen.

Überprüfung:

  • Ternäre Bäume werden von der Hardware nicht unterstützt, daher laufen sie weniger schnell.
  • B-Tress mit Aufträgen, die viel, viel, viel höher als 3 sind, ist für die Plattenoptimierung großer Datensätze üblich. Sobald Sie 2 überschritten haben, gehen Sie höher als 3.
9
Dean J

Die ternäre Suche kann nur dann schneller sein als eine binäre Suche, wenn eine 3-Wege-Partitionsbestimmung für weniger als etwa das 1,5-fache der Kosten eines 2-Wege-Vergleichs durchgeführt werden kann. Wenn die Elemente in einem sortierten Array gespeichert werden, ist die 3-Wege-Bestimmung im Durchschnitt 1,66-mal so teuer wie eine 2-Wege-Bestimmung. Wenn Informationen in einem Baum gespeichert werden, sind die Kosten für das Abrufen von Informationen jedoch relativ zu den Kosten für den tatsächlichen Vergleich hoch, und die Cache-Lokalität bedeutet, dass die Kosten für das zufällige Abrufen eines Paars verwandter Daten nicht viel höher sind als die Kosten für das Abrufen einer einzelnen Datum, ein ternärer oder n-Wege-Baum kann die Effizienz erheblich verbessern.

8
supercat

Warum denken Sie, dass die ternäre Suche schneller sein sollte?

Durchschnittliche Anzahl der Vergleiche:

in ternary search = ((1/3)*1 + (2/3)*2) * ln(n)/ln(3) ~ 1.517*ln(n)
in binary search  =                   1 * ln(n)/ln(2) ~ 1.443*ln(n).

Schlechteste Anzahl von Vergleichen:

in ternary search = 2 * ln(n)/ln(3) ~ 1.820*ln(n)
in binary search  = 1 * ln(n)/ln(2) ~ 1.443*ln(n).

Es sieht also so aus, als sei die ternäre Suche schlechter.

8
Aryabhatta

Beachten Sie auch, dass diese Sequenz zur linearen Suche verallgemeinert wird, wenn wir fortfahren 

Binary search
Ternary search
...
...
n-ary search ≡ linear search

Bei einer n-ary-Suche haben wir also "one only COMPARE", was bis zu n tatsächliche Vergleiche erfordern kann.

4
Lazer

"Terinary" (ternary?) - Suche ist im besten Fall effizienter, was die Suche nach dem ersten Element (oder vielleicht dem letzten Element, je nachdem, welchen Vergleich Sie zuerst durchführen) beinhaltet. Für Elemente, die weiter vom Ende entfernt sind, prüfen Sie zuerst, während zwei Vergleiche das Array jedes Mal um 2/3 einschränken würden, dieselben zwei Vergleiche mit der binären Suche würden den Suchraum um 3/4 einschränken.

Hinzu kommt, dass die binäre Suche einfacher ist. Sie vergleichen nur die Hälfte oder die andere, anstatt zu vergleichen, wenn das erste Drittel weniger ist, sonst zu vergleichen, wenn das zweite Drittel weniger ist, sonst das letzte Drittel.

2
cHao

Die ternäre Suche kann effektiv auf parallelen Architekturen - FPGAs und ASICs - verwendet werden. Wenn beispielsweise der für die Suche erforderliche interne FPGA-Speicher weniger als die Hälfte der FPGA-Ressource ausmacht, können Sie einen doppelten Speicherblock erstellen. Dies würde den gleichzeitigen Zugriff auf zwei verschiedene Speicheradressen ermöglichen und alle Vergleiche in einem einzigen Taktzyklus durchführen. Dies ist einer der Gründe, warum 100-MHz-FPGA manchmal die 4-GHz-CPU übertreffen kann :)

2
Thu

Fast alle Lehrbücher und Websites auf binären Suchbäumen sprechen nicht wirklich von binären Bäumen! Sie zeigen Ihnen ternäre Suchbäume! Echte Binärbäume speichern Daten in ihren Blättern und nicht in internen Knoten (mit Ausnahme der zu navigierenden Tasten). Einige nennen diese Laubbäume und unterscheiden zwischen in Lehrbüchern dargestellten Knotenbäumen:

J. Nievergelt, C.-K. Wong: Obere Grenzen für die Gesamtweglänge von binären Bäumen, Journal ACM 20 (1973) 1–6.

Das Folgende hierzu stammt aus dem Buch über Datenstrukturen von Peter Brass.

2.1 Zwei Modelle von Suchbäumen

In der soeben skizzierten Übersicht haben wir einen wichtigen Punkt unterdrückt, der zunächst Trivial erscheint, tatsächlich führt er jedoch zu zwei verschiedenen Modellen von Suchbäumen, entweder zu , Die mit einem Großteil des Folgenden kombiniert werden können Material, von denen jedoch stark bevorzugt wird.

Wenn wir in jedem Knoten den Abfrageschlüssel mit dem im Knoten Enthaltenen Schlüssel vergleichen und dem linken Zweig folgen, wenn der Abfrageschlüssel kleiner ist, und dem rechten Zweig , Wenn der Abfrageschlüssel größer ist, was dann passiert, wenn sie gleich sind? Die zwei Modelle Von Suchbäumen lauten wie folgt:

  1. Nehmen Sie den linken Zweig, wenn der Abfrageschlüssel kleiner als der Knotenschlüssel ist. ansonsten nimm den rechten Ast, bis du ein Blatt des Baumes erreichst. Die Schlüssel im inneren Knoten Des Baums dienen nur zum Vergleich; Alle Gegenstände befinden sich in den Blättern.

  2. Nehmen Sie den linken Zweig, wenn der Abfrageschlüssel kleiner als der Knotenschlüssel ist. nehmen Sie den rechten Zweig , wenn der Abfrageschlüssel größer als der Knotenschlüssel ist; und nimm das im Knoten enthaltene Objekt , wenn sie gleich sind.

Dieser unbedeutende Punkt hat eine Reihe von Konsequenzen:

{In Modell 1 ist der zugrunde liegende Baum ein binärer Baum, während in - Baumknoten in Modell 2 tatsächlich ein ternärer Knoten mit einem speziellen mittleren Nachbarn ist.

{In Modell 1 hat jeder innere Knoten einen linken und einen rechten Teilbaum (jeder möglicherweise ein Blattknoten des Baums), wohingegen in Modell 2 unvollständige Knoten zulässig sind, sofern dies links ist oder der rechte Teilbaum fehlt möglicherweise, und nur das Vergleichsobjekt und der Schlüssel sind garantiert vorhanden.

Die Struktur eines Suchbaums von Modell 1 ist also regelmäßiger als die eines Baums Von Modell 2; Dies ist zumindest für die Implementierung ein klarer Vorteil.

{In Modell 1 erfordert das Durchlaufen eines inneren Knotens nur einen Vergleich, , Während in Modell 2 zwei Vergleiche erforderlich sind, um die drei - Möglichkeiten zu überprüfen.

Tatsächlich enthalten Bäume gleicher Höhe in den Modellen 1 und 2 höchstens ungefähr Die gleiche Anzahl von Objekten, jedoch benötigt man in Modell 2 doppelt so viele Vergleiche, um die tiefsten Objekte des Baums zu erreichen . Natürlich gibt es in Modell 2 auch einige Objekte, die viel früher erreicht werden. Das Objekt in der Wurzel wird mit nur zwei Vergleichen gefunden , aber fast alle Objekte befinden sich auf oder in der Nähe der tiefsten Ebene.

Satz. Ein Baum der Höhe h und Modell 1 enthält höchstens 2 ^ h Objekte. Ein Baum der Höhe h und Modell 2 enthält höchstens 2 ^ h + 1 - 1 Objekte.

Dies ist leicht zu erkennen, da der Baum der Höhe h als linker und rechter Unterbaum jeweils einen Baum der Höhe höchstens h - 1 und in Modell 2 ein zusätzliches Objekt zwischen Hat.

{In Modell 1 dienen Schlüssel in inneren Knoten nur zum Vergleich und können Zur Identifikation der Objekte in den Blättern wieder erscheinen. In Modell 2 erscheint jede - Taste zusammen mit ihrem Objekt nur einmal.

Es ist sogar möglich, dass in Modell 1 Schlüssel zum Vergleich verwendet werden, die Zu keinem Objekt gehören, z. B. wenn das Objekt gelöscht wurde. Durch die konzeptionelle Trennung dieser Funktionen des Vergleichs und der Identifikation ist Nicht überraschend, und in späteren Strukturen müssen wir möglicherweise sogar künstliche Tests definieren, die keinem Objekt entsprechen, nur zu eine gute Aufteilung des Suchraums erhalten. Alle zum Vergleich verwendeten Schlüssel sind notwendigerweise verschieden, da in einem Baum des Modells 1 jeder innere Knoten nicht leere linke und rechte Unterbäume hat. Jeder Schlüssel Kommt also höchstens zweimal vor, einmal als Vergleichsschlüssel und einmal als Identifikationsschlüssel in Dem Blatt.

Modell 2 wurde zur bevorzugten Version des Lehrbuchs, da in den meisten Lehrbüchern Nicht zwischen dem Objekt und seinem Schlüssel unterschieden wird: Der Schlüssel ist das Objekt. Dann wird es unnatürlich, den Schlüssel in der Baumstruktur zu duplizieren . Aber in Allen realen Anwendungen ist die Unterscheidung zwischen Schlüssel und Objekt ziemlich wichtig. Man möchte fast nie nur eine Menge von Zahlen verfolgen; Die Zahlen sind normalerweise mit einigen weiteren Informationen verknüpft, die oft viel größer sind als der Schlüssel selbst.

1
mszlazak

Hier ist einige zufällige experimentelle Beweise, die ich überhaupt nicht überprüft habe die zeigen, dass es langsamer ist als die binäre Suche.

1

Möglicherweise haben Sie gehört, dass in diesen Rätseln ternäre Suchanfragen verwendet werden, die das Wiegen auf Waagen beinhalten. Diese Skalen können 3 Antworten liefern: Links ist leichter, beide sind gleich oder Links sind schwerer. Bei einer ternären Suche ist daher nur ein Vergleich erforderlich. Computer verwenden jedoch eine boolesche Logik, die nur zwei Antworten hat. Um die ternäre Suche durchzuführen, müssten Sie tatsächlich zwei Vergleiche anstelle von 1 durchführen. Ich denke, es gibt Fälle, in denen dies noch schneller ist als in den vorherigen Plakaten erwähnt, aber Sie können sehen, dass die ternäre Suche keine ist immer besser und es ist verwirrender und weniger natürlich auf einem Computer zu implementieren.

0
muddybruin

Ich habe gerade ein blog über die ternäre Suche gepostet und einige Ergebnisse gezeigt. Ich habe auch einige erste Implementierungen auf meinem git-Repo zur Verfügung gestellt Ich stimme mit jedem über den Theorieteil der ternären Suche völlig überein, aber warum sollte ich es nicht versuchen? In Bezug auf die Implementierung ist dieser Teil leicht genug, wenn Sie über drei Jahre Codierungserfahrung verfügen. Ich habe festgestellt, dass bei großen Datenmengen viele Male gesucht werden muss, da die ternäre Suche von Vorteil ist. Wenn Sie der Meinung sind, dass Sie mit einer ternären Suche besser umgehen können, sollten Sie dies tun.

0
Vraj Pandya

Theoretisch wird das Minimum von k/ln(k) bei e erreicht, und da 3 näher an e als 2 liegt, sind weniger Vergleiche erforderlich. Sie können überprüfen, ob 3/ln(3) = 2.73.. und 2/ln(2) = 2.88... Die binäre Suche könnte schneller sein, weil der Code dafür weniger Verzweigungen aufweist und auf modernen CPUs schneller ausgeführt wird.

0
Daniel Velkov

Obwohl Sie in beiden Suchbäumen die gleiche Big-O-Komplexität (ln n) erhalten, besteht der Unterschied in den Konstanten. Sie müssen auf jeder Ebene mehr Vergleiche für einen ternären Suchbaum durchführen. Der Unterschied läuft also auf k/ln (k) für einen k-ary-Suchbaum. Dies hat einen Mindestwert bei e = 2,7 und k = 2 liefert das optimale Ergebnis.

0
Crashh