Warum binäre Verwendung suchen, wenn es ternäre suchen?

https://stackoverflow.com/questions/3498382

29-09-2019
|

Frage

ich über Ternary Suche vor kurzem gehört, in dem wir ein Array in 3 Teile und vergleichen Sie unterteilen. Hier wird es zwei Vergleiche, aber es reduziert das Array n / 3. Warum nutzen die Menschen nicht so viel?

Lösung

Eigentlich Menschen tun Gebrauch k-ary Bäume für beliebige k.

Dies ist jedoch ein Kompromiss.

Um ein Element in einem k-ary Baum zu finden, müssen Sie um k * ln (N) / ln (k) Operationen (erinnere dich an die Change-of-Basisformel). Je größer k ist, desto mehr Gesamt Operationen, die Sie benötigen.

Die logische Erweiterung von dem, was Sie sagen, ist „warum Menschen einen N-ary Baum nicht für N Datenelemente verwenden?“. Was natürlich wäre ein Array sein.

Andere Tipps

Eine ternäre Suche werden Sie noch geben die gleiche asymptotische Komplexität O (log N) Suchzeit und erhöht die Komplexität der Implementierung.

Das gleiche Argument kann gesagt werden, warum sollen Sie nicht eine Quad-Suche oder andere höhere Ordnung werden sollen.

Searching 1 Milliarde (ein US-Milliarden - 1000000000) sortierten Artikel im Durchschnitt etwa 15 vergleicht mit binärer Suche dauern würden und etwa 9 vergleicht mit einer ternären Suche - nicht einen sehr großer Vorteil. Und beachten Sie, dass jeder ‚ternären vergleichen‘ 2 Ist-Vergleiche beinhalten könnten.

Wow. Die Top voted Antworten vermissen das Boot auf diesem, glaube ich.

Ihre CPU nicht ternäre Logik als eine einzelne Operation unterstützen; es bricht ternäre Logik in mehrere Schritte von binärer Logik. Der optimalste Code für die CPU ist binäre Logik. Wenn Chips waren üblich, die ternäre Logik als eine einzelne Operation unterstützt, haben Sie Recht.

B-Bäume können an jedem Knoten mehrere Verzweigungen aufweisen; ein Reihenfolge-3 B-Baum ist ternäre Logik. Jeder Schritt auf den Baum nimmt zwei Vergleiche statt einen, und dies wird wahrscheinlich dazu führen, dass langsamer in CPU-Zeit zu sein.

B-Bäume sind jedoch ziemlich häufig. Wenn Sie davon ausgehen, dass wird jeder Knoten im Baum irgendwo auf der Festplatte separat gespeichert werden, dann werden Sie die meisten Ihrer Zeit mit dem Lesen von der Festplatte verbringen ... und die CPU wird nicht zu einem Engpass, aber die Platte sein wird. So haben Sie einen B-Baum mit 100.000 Kindern pro Knoten nehmen, oder was auch immer sonst Willen kaum paßt in einen Speicherblock. B-Bäume mit dieser Art Faktor der Verzweigung mehr als drei Knoten selten hoch wären, und Sie würden nur drei Platte liest haben - zu einem Engpass drei Stationen -. Eine enorme, enorme Datenmenge suchen

Überprüfen:

Ternary Bäume werden nicht von der Hardware unterstützt, so dass sie weniger schnell ausgeführt werden.
B-Strähne mit Aufträgen viel, viel, viel höher als 3 sind gemeinsam für Disk-Optimierung von großen Datensätzen; wenn Sie nach 2 gegangen sind, gehen mehr als 3.

Der einzige Weg, eine ternäre Suche schneller sein kann als eine binäre Suche ist, wenn ein 3-Wege-Partition Bestimmung kann für weniger getan werden als etwa 1,55-fache der Kosten eines 2-Wege-Vergleich. Wenn die Elemente in einer sortierten Array gespeichert sind, wird die 3-Wege-Bestimmung im Durchschnitt 1,66 Mal als 2-Wege-Bestimmung so teuer sein. Wenn Informationen in einem Baum gespeichert ist, jedoch die Kosteninformationen zu holen ist hoch im Vergleich zu den Kosten der tatsächlich zu vergleichen, und Cache-Ort bedeutet, dass die Kosten von zufällig ein Paar von verwandten Daten-Abruf nicht viel schlechter als die Kosten für das Abrufen ist ein einziger Datum, ein ternärer oder n-Wege-Baum Effizienz erheblich verbessern kann.

Was macht Sie denken, sollte Ternary Suche schneller sein?

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

Schlimmste Anzahl der Vergleiche:

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

So sieht es aus wie ternäre Suche ist noch schlimmer.

Beachten Sie auch, dass diese Sequenz verallgemeinert auf lineare Suche, wenn wir gehen auf

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

Also, in einem n-stufigen suchen, werden wir haben „man nur VERGLEICH“, die n Ist-Vergleiche bis könnte nehmen.

„Terinary“ (ternäre?) Suche ist effizienter, im besten Fall, die für das erste Element der Suche würde bedeuten, (oder vielleicht die letzten, je nachdem, welchem ??Vergleich Sie zuerst tun). Für Elemente weiter vom Ende zuerst Sie überprüfen, während zwei Vergleiche jedes Mal das Array von 2/3 verengen würden, die gleichen zwei Vergleiche mit binärer Suche würden den Suchraum von 04.03 verengen.

In dem, ist binäre Suche einfacher. Sie haben soeben vergleichen und eine Hälfte oder das andere bekommen, anstatt zu vergleichen, wenn weniger als das erste Drittel bekommen, sonst vergleichen, wenn weniger als das zweite Drittel zu bekommen, sonst das letzte Drittel erhalten.

Ternary Suche kann effektiv auf parallele Architekturen verwendet werden - FPGAs und ASICs. Zum Beispiel, wenn interner FPGA-Speicher für die Suche erforderlich ist weniger als die Hälfte der FPGA-Ressourcen, können Sie einen doppelten Speicherblock zu machen. Dies würde es ermöglichen, gleichzeitig Zugriff zwei verschiedene Speicheradressen und tut alle Vergleiche in einem einzigen Taktzyklus. Dies ist einer der Gründe, warum 100MHz FPGA kann das 4-GHz-CPU manchmal übertreffen:)

Hier einige zufällige experimentelle Hinweise darauf, dass ich nicht bei allen geprüft zeigt, dass es langsamer als binäre Suche.

Fast alle Lehrbücher und Webseiten auf binäre Suchbäume reden nicht wirklich über Binärbäumen! Sie zeigen Ihnen Ternary Suchbäume! Echte binäre Bäume speichern Daten in ihren Blättern nicht innerer Knoten (mit Ausnahme der Tasten zu navigieren). Manche nennen diese Laubbäume und machen die Unterscheidung zwischen Knoten Bäume in den Lehrbüchern dargestellt:

J. Nievergelt, C.-K. Wong: Upper Bounds für die Gesamtpfadlänge von Binary Trees, Journal ACM 20 (1973) 1-6.

Die folgenden daran ist, von Peter Brass Buch über Datenstrukturen.

2.1 Zwei Modelle aus Suchbäumen

In der Gliederung nur gegeben, unterdrückt wir einen wichtigen Punkt, dass auf den ersten Blick trivial, aber in der Tat kommt es zu zwei verschiedenen Modellen von Suchbäume, entweder von die mit wesentlich aus folgendem Material kombiniert werden, aber von denen ist stark bevorzugt.

Wenn wir in jedem Knoten der Abfrageschlüssel mit dem Schlüssel in dem Vergleich enthielten Knoten und dem linken Zweig folgen, wenn die Abfrage Schlüssel kleiner ist und der rechte Ast wenn die Abfrage Schlüssel größer ist, dann passiert was, wenn sie gleich sind? Die beiden Modelle von Suchbäume sind wie folgt:

Nehmen Sie links Zweig, wenn Abfrageschlüssel ist kleiner als Knotenschlüssel; sonst nehmen die rechtser Zweig, bis Sie ein Blatt des Baumes erreichen. Die Tasten in dem inneren Knoten nur zum Vergleich des Baumes sind; alle Objekte sind in den Blättern.
Nehmen Sie links Zweig, wenn Abfrageschlüssel ist kleiner als Knotenschlüssel; nehmen Sie den rechten Zweig Wenn die Abfrage Schlüssel ist, größer ist als der Knotenschlüssel; und nehmen das Objekt enthalten in den Knoten, wenn sie gleich sind.

Dieser kleine Punkt hat eine Reihe von Konsequenzen:

{Modell In 1 ist der darunter liegende Baum ein binärer Baum, während im Modell 2, das jeweils Baumknoten ist wirklich ein ternärer Knoten mit einem speziellen mittleren Nachbarn.

{Modell In 1 ist jeder innere Knoten hat einen linken und einen rechten Unterbaum (die jeweils gegebenenfalls eine Blattknoten des Baums), wohingegen in Modell 2, müssen wir unvollständig ermöglichen Knoten, wo links oder rechts Teilstruktur könnte fehlen, und nur die Vergleichsobjekt und Schlüssel sind zu exist garantiert.

So ist die Struktur eines Suchbaum des Modells 1 ist regelmäßiger als die eines Baumes Modell 2; Dies ist zumindest für die Umsetzung eines klaren Vorteil.

{Modell In 1, die einen inneren Knoten durchqueren erfordert nur einen Vergleich, während im Modell 2, mussten wir zwei Vergleiche die drei überprüfen Möglichkeiten.

Tatsächlich Bäume der gleichen Höhe in den Modellen 1 und 2 enthalten höchstens ca. die gleiche Anzahl von Objekten, aber man braucht doppelt so viele Vergleiche in Modell 2 die tiefsten Objekte des Baumes zu erreichen. Natürlich in Modell 2 gibt es auch einige Objekte, die viel früher erreicht werden; das Objekt in der Wurzel gefunden werden mit nur zwei Vergleiche, sind aber fast alle Gegenstände auf oder in der Nähe der tiefsten Ebene.

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

Dieses leicht zu sehen, da der Baum der Höhe h hat als linke und rechte Teilbäume ein höchstens h Baum der Höhe - 1 jeweils, und in Modell 2 ein zusätzliches Objekt zwischen sie.

{Im Modell 1, Schlüssel in inneren Knoten dienen nur für Vergleiche und können zur Identifizierung der Objekte in den Blättern wieder erscheinen. In Modell 2, jeder Taste erscheint nur einmal, zusammen mit seinem Objekt.

Es ist sogar möglich, in Modell 1, dass Schlüssel zum Vergleich herangezogen werden, dass gehört nicht zu einem Objekt, zum Beispiel, wenn das Objekt gelöscht wurde. Durch konzeptuell Trennung dieser Funktionen des Vergleichs und der Identifizierung, diese ist nicht überraschend, und in späteren Strukturen brauchen wir vielleicht sogar künstlich definieren Tests nicht auf ein beliebiges Objekt entspricht, nur eine gute Aufteilung der Suche zu bekommen Raum. Alle Schlüssel zum Vergleich herangezogen werden notwendigerweise anders, weil in einem Modell 1 Baum, jeder innere Knoten nicht leer linken und rechten Teilbäume. Also jede Taste höchstens tritt zweimal, einmal als Vergleich key und einmal als Identifikationsschlüssel in das Blatt.

Modell 2 wurde die bevorzugte Lehrbuch Version, weil in den meisten Lehrbüchern die Unterscheidung zwischen Objekt und seinem Schlüssel wird nicht: Der Schlüssel ist das Objekt. Dann wird es unnatürlich den Schlüssel in der Baumstruktur zu duplizieren. Aber in alle realen Anwendungen ist die Unterscheidung zwischen Schlüssel und Objekt sehr wichtig. Ein fast möchte nie aus nur eine Reihe von Zahlen zu halten; die Zahlen wird in der Regel mit einigen weiteren Informationen verknüpft, die oft viel größer als der Schlüssel selbst.

Sie haben vielleicht gehört in diesen Rätseln ternären Suche verwendet wird, die Dinge auf Skalen beinhalten Wiegen. Diese Skalen können 3 Antworten zurück: links ist leichter, beide sind gleich oder links ist schwerer. So in einem ternären suchen, dauert es nur 1 Vergleich. Allerdings verwenden Computer Boolesche Logik, die nur zwei Antworten gegeben. Um die ternären Suche zu tun, würden Sie tatsächlich haben zwei Vergleiche zu tun statt 1. Ich denke, es gibt einige Fälle, in denen dies noch schneller als früher Poster erwähnt, aber man kann sehen, dass ternäre Suche nicht immer besser ist, und es ist mehr verwirrend und weniger natürlich auf einem Computer zu implementieren.

Theoretisch das Minimum von k/ln(k) bei erreicht e und seit 3 ??näher an e als 2 erfordert es weniger Vergleiche. Sie können diese 3/ln(3) = 2.73.. überprüfen und der Grund, warum 2/ln(2) = 2.88.. binäre Suche schneller sein könnte, ist, dass der Code für es wird weniger Verzweigungen und laufen schneller auf modernen CPUs.

Ich habe gerade gebucht ein bloggen über die ternäre Suche und ich haben einige Ergebnisse gezeigt. Ich habe auch einige erste Level-Implementierungen auf meinem git Repo vorausgesetzt ich total mit jedem über die Theorie Teil zustimmen von die ternäre Suche aber, warum es nicht einen Versuch geben? Gemäß der Implementierung dieses Teil ist einfach genug, wenn Sie die Codierung Erfahrung drei Jahre. Ich fand, dass, wenn Sie große Datenmenge haben und Sie müssen es oft ternäre zur Suche einen Vorteil. Wenn Sie denken, dass Sie mit einem ternären Suche gehen besser kann es.

Auch wenn Sie die gleiche Big-O Komplexität (ln n) in beiden Suchbäumen zu erhalten, ist der Unterschied in den Konstanten. Sie müssen auf jeder Ebene mehr Vergleiche für einen ternären Suchbaum tun. So ist der Unterschied läuft darauf hinaus k / ln (k) für einen k-ary Suchbaum. Dies hat einen Minimalwert bei e = 2,7 und k = 2 liefert das optimale Ergebnis.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow