Warum ist die binäre Suche schneller als die ternäre Suche?

Das Durchsuchen eines Arrays von Elementen mit der binären Suche erfordert im schlimmsten Fall Iterationen, da wir bei jedem Schritt die Hälfte unseres Suchraums abschneiden. Wenn wir stattdessen 'ternäre Suche' verwenden würden, würden wir bei jeder Iteration zwei Drittel unseres Suchraums , daher sollte der schlimmste Fall Iterationen ... $N$ $\log_2 N$ $\log_3 N < \log_2 N$

Es scheint, dass die ternäre Suche schneller ist. Warum verwenden wir also die binäre Suche?

algorithms algorithm-analysis runtime-analysis search-algorithms binary-search Der mittlere Platz
quelle

Könnte man nicht die gleiche Argumentation für die quartäre Suche verwenden? Oder sogar Dezimalsuche ... oder irgendetwas

Größeres

Bitte lesen Sie über B + Trees

Arunmoezhi

Die lineare Suche ist bei kleinen bis mittleren Problemen auf moderner Hardware oft schneller als die binäre Suche, da sie cachekohärent ist und fast alle Zweige korrekt vorhergesagt werden.

Pseudonym

Auch 2 * log_3 (N) = log_3 (N ^ 2), wenn es zu Ihrer Intuition spricht.

PawelP

Lassen Sie uns dies intuitiv ausdrücken. Wenn die Verwendung einer 3-basierten Suche schneller ist, weil der Suchraum bei jeder Iteration größer wird, ist die Verwendung einer millionenbasierten Suche dann nicht schneller? Sie können jedoch leicht erkennen, dass Sie durchschnittlich 500.000 Überprüfungen in jeder Iteration durchführen müssen, um den 1-millionsten Slice zu ermitteln, der das Ziel enthielt. Wenn Sie den Suchraum bei jeder Iteration halbieren und nicht mehr, erhalten Sie die meisten Informationen zuverlässig in einem einzigen Schritt.

ErikE

Antworten:

Wenn Sie die binäre Suche anwenden, haben Sie viele Vergleiche. Wenn Sie die ternäre Suche anwenden, haben Sie viele Vergleiche, da Sie in jedem Schritt 2 Vergleiche durchführen müssen, um den Suchraum in drei Teile zu unterteilen. Wenn Sie nun , können Sie feststellen, dass: Da wir wissen, dass , erhalten wir tatsächlich mehr Vergleiche mit der ternären Suche.

\log_{2} (n) + O (1)

$\log_2(n)+O(1)$

2 \cdot \log_{3} (n) + O (1)

$2 \cdot \log_3(n) + O(1)$

2 \cdot \log_{3} (n) + O (1) = 2 \cdot \frac{\log (2)}{\log (3)} \log_{2} (n) + O (1)

$2 \cdot \log_3(n) + O(1) = 2 \cdot \frac{\log(2)}{\log(3)} \log_2(n)+ O(1)$

2 \cdot \frac{\log (2)}{\log (3)} > 1

$2 \cdot \frac{\log(2)}{\log(3)} > 1$

Übrigens: Eine fache Suche kann sehr sinnvoll sein, wenn Vergleiche sehr kostspielig sind und parallelisiert werden können, da dann parallele Computer angewendet werden können. $n$

Beachten Sie, dass das Argument leicht auf die fache Suche verallgemeinert werden kann. Sie müssen nur zeigen, dass die Funktion für ganzzahlige Werte von streng monoton ansteigt . $n$ $f(k) = (k-1) \cdot \frac{\log(2)}{\log(k)}$ $k$

DCTLib
quelle

Und LHS ist linear und RHS ist logarithmisch, so dass es für kein Quartär oder etwas anderes hilfreich ist .... Nette Erklärungen .... Danke

The Mean Square

Der Vollständigkeit halber sei angemerkt, dass ein abstraktes Maß wie die Anzahl der Elementvergleiche die tatsächliche Laufzeit möglicherweise dominiert oder nicht. Insbesondere müssen Sie möglicherweise berücksichtigen, wie viele Cache-Fehler bei beiden Suchvorgängen wahrscheinlich auf langen Arrays auftreten. (Hier stimmen sie überein. Ich stelle dies nur deshalb fest, weil das OP fragt: "Warum ist es schneller?", Und das mit einem abstrakten Maß zu beantworten, kann für einige Algorithmen irreführend sein.)

Raphael

Bei einer ternären Suche benötigen Sie 1/3 der Zeit nur 1 Vergleich (machen Sie einen niedrigeren Vergleich: Wenn Sie sich im unteren Drittel befinden, brauchen Sie keinen zweiten Vergleich). Das macht ternary nur etwa 5% langsamer als 25% (in dieser Welt, in der es uns nur um Vergleichszahlen geht). Ich bin mir nicht sicher, wie ich das auf n-ary verallgemeinern soll, obwohl ich vermute, dass es nie schneller als binär wird.

Aaron Dufour

@AaronDufour: Da eine quaternäre Suche durchgeführt werden kann, indem zuerst der Vergleich mit dem mittleren Element durchgeführt und dann das Ergebnis der anderen Vergleiche ignoriert wird, ist die einzige Möglichkeit, wie die quaternäre Suche schneller durchgeführt werden kann, die parallele Durchführung von drei Vergleichen günstiger als zwei Vergleiche könnte sequentiell durchgeführt werden.

Supercat

@AaronDufour Aber du amortisierst über Elemente, nach denen du suchen musst, und mir ist nicht klar, warum das in Ordnung ist. Im schlimmsten Fall können beide Vergleiche bei jedem Schritt durchgeführt werden.

Sasho Nikolov

DCTLib ist richtig, aber vergessen Sie die Mathematik für eine Sekunde.

Nach Ihrer Logik sollte n -ary dann am schnellsten sein. Aber wenn Sie darüber nachdenken, entspricht n -ary genau einer regulären Iterationssuche (nur 1-mal-1-Iteration durch die Liste, jedoch in umgekehrter Reihenfolge). Zuerst wählen Sie das letzte (oder vorletzte) Element in der Liste aus und vergleichen diesen Wert mit Ihrem Vergleichswert. Dann entfernen Sie dieses Element aus Ihrer Liste und wählen dann das letzte Element in der neuen Liste aus, bei dem es sich nur um den vorletzten Wert im Array handelt. Jedes Mal eliminieren Sie immer nur 1 Wert, bis Sie Ihren Wert gefunden haben.

Stattdessen sollten Sie sich das so überlegen - wie entferne ich die meisten Werte aus der Liste bei jeder Iteration? Bei einer binären Suche eliminieren Sie immer die Hälfte der Liste. Bei einer ternären Suche besteht die Möglichkeit, dass Sie 2/3 der Liste entfernen (33,33% Wahrscheinlichkeit), bei einer noch größeren Wahrscheinlichkeit (66,66%), dass Sie nur 1/3 der Liste entfernen. Um O (n) zu berechnen, müssen Sie sich das Worst-Case-Szenario ansehen, das 1/3, weniger als 1/2 ist. Je näher man sich n nähert, desto schlimmer wird es.

Durch die binäre Suche wird nicht nur das Worst-Case-Szenario verbessert, sondern auch Ihre durchschnittliche Zeit. Wenn wir den erwarteten Wert betrachten (welchen Teil der Liste können wir durchschnittlich entfernen), verwenden wir diese Formel:

(P_lower) x (Anteil, den wir entfernen können, wenn er niedriger ist) + (P_higher) x (Anteil, den wir entfernen können, wenn er höher ist) = E

Bei der binären Suche ist dies .5x.5 + .5x.5 = .5 (wir entfernen immer die Hälfte der Liste). Bei ternären Suchvorgängen beträgt dieser Wert .666x.333 + .333x.666 = 0,44, oder bei jedem Schritt werden wahrscheinlich nur 44% der Liste entfernt, was sie im Durchschnitt weniger effizient als die binäre Suche macht. Dieser Wert erreicht die Spitze bei 1/2 (die Hälfte der Liste) und nimmt ab, je näher Sie an n (umgekehrte Iteration) und 0 (reguläre Iteration) gelangen.

Ok, also habe ich gelogen ... es ist ein bisschen Mathe dabei, aber ich hoffe, das hilft!

dberm22
quelle

Das ist eine großartige Antwort.

The_Sympathizer

Ihre Grenzanalyse hilft, harte Mathematik zu verstehen! Die n-fache sequentielle Suche hat die gleichen Kosten für die lineare Suche O (n).

Shuva

-2

Bitte beachten Sie, dass das Argument log (N) vs 2 log (N) Vergleiche auf einer naiven Interpretation des Algorithmus basiert. Wenn ich mich tatsächlich hinsetzen und dies in x86-Assembly schreiben würde, würden die Ergebnisse invertiert. Das Problem ist die Verwendung von Ganzzahlen für Testfälle in Kombination mit einem nicht ausreichend intelligenten Compiler, der die redundanten Vergleiche nicht entfernen kann. Versuchen Sie es erneut mit Zeichenfolgen und einer geeigneten Zeichenfolgenvergleichsfunktion, und codieren Sie sie, um die Vergleichsfunktion einmal pro Schleife aufzurufen. Sie werden feststellen, dass die ternäre Suche wieder schneller ist.

Joshua
quelle

Natürlich wäre die ternäre Suche schneller, wenn Sie nur einen Vergleich pro Iteration durchführen könnten. Aber egal ob Zeichenketten oder ganze Zahlen, Sie können nicht.

FrankW

Die Vergleiche wären nicht redundant und das Problem hat nichts mit dem Compiler zu tun. Um den Suchraum in drei Teile zu unterteilen, benötigen Sie 2 Vergleiche. Bei einer binären Suche müssen Sie nur mit dem mittleren Element vergleichen und wissen dann, in welcher Hälfte des Suchraums das Ergebnis liegen würde. Bei der ternären Suche müssen Sie mit dem Element 1/3 des Weges durch das vergleichen Liste UND das 2/3 des Weges durch die Liste. Welche Art von Daten Sie vergleichen oder welche Sprache Sie verwenden, spielt keine Rolle. Zugegeben, wenn sich der Artikel im 1. 3. befindet, könnten Sie nach 1 Vergleich aufhören.

Reirab

Auf einigen Plattformen kann die ternäre Suche schneller sein, da die CPU mehr Zeit hat, um die Operanden aus dem RAM abzurufen, bevor sie zum Vergleich benötigt werden. Dies hängt jedoch vollständig von der verwendeten Plattform und ihren Latenzen und Caches ab.

jpa

Darn it - falsche Definition der ternären Suche.

Joshua