Gibt es eine Studie oder Theorie hinter der Kombination von binärer Suche und Interpolationssuche?

14

Ich habe gerade gelesen Kann dieser Algorithmus immer noch als Algorithmus für die binäre Suche betrachtet werden? und erinnerte mich, dass ich vor ein paar Jahren einen Indexer / eine Suche nach Protokolldateien geschrieben habe, um Protokolleinträge in großen Nur-Text-Dateien nach Datum / Zeit-Fenster zu finden.

Währenddessen habe ich mich für die Interpolationssuche entschieden (ich wusste nicht, dass es so heißt, ich bin selbst auf die Idee gestoßen). Dann fuhr ich aus irgendeinem Grund mit der Idee fort, die Interpolationsschritte mit den binären Teilungsschritten abzuwechseln: Bei Schritt 0 würde ich interpolieren, um den Testpunkt zu bestimmen, dann würde ich bei Schritt 1 den genauen Mittelpunkt usw. nehmen.

Anschließend habe ich das System mit der reinen Interpolationssuche, der reinen Binärsuche und meinem Kombinationsversuch verglichen. Der Wechselansatz war sowohl in Bezug auf die Zeit als auch auf die Anzahl der erforderlichen Tests ein klarer Gewinner, bevor ein Satz zufällig ausgewählter Zeiten gefunden wurde.

Inspiriert von der verknüpften Frage habe ich gerade eine schnelle Suche nach "abwechselnder Interpolationssuche und binärer Suche" durchgeführt und nichts gefunden. Ich habe auch "Hedged Interpolation Search" ausprobiert, wie in meinem Kommentar zu einer der Antworten vorgeschlagen.

Habe ich über eine bekannte Sache gestolpert? Gibt es eine theoretische Rechtfertigung dafür, dass bestimmte Datentypen schneller sind? Die Protokolldateien waren für die Zeit in der Regel groß (z. B. 1 bis 2 GB Text mit möglicherweise 10 Millionen zu durchsuchenden Zeilen), und die Verteilung der Daten / Zeiten in ihnen war komplex, mit starken Aktivitätsschüben, allgemeinen Stoßzeiten und Ruhezeiten. Meine Benchmark-Tests ermittelten Stichproben aus einer gleichmäßigen Verteilung der Zielzeiten.

Neil Slater
quelle

Antworten:

5

Habe ich über eine bekannte Sache gestolpert?

Es gibt verschiedene Methoden, die auf einer Mischung aus Interpolationssuche und Binärsuche basieren, mit a Ö(lÖG lÖG n) durchschnittliche Fallzugriffszeit (gleichmäßige Verteilung) und Ö(lÖG n) Worst-Case-Zeit (Werte ungleich verteilt):

  • Die introspektive Suche ist Ihre Methode (zwischen einer Interpolationssuche und einer binären Suche wechseln). Ich habe keine weiteren Details.
  • Interpolation-Binary Search (IBS) von N. Santoro, JB Sidney (1985).

    Die allgemeine Idee ist, dass die Interpolationssuche nur dann nützlich ist, wenn das gesuchte Array größer als ein vorgegebener Schwellenwert ist. Wenn das betrachtete Suchsegment kleiner als ein benutzerdefinierter Schwellenwert ist, wird die binäre Suche bedingungslos angewendet. Umgekehrt wird über diesem Schwellenwert ein Interpolationssuchschritt angewendet, auf den schließlich ein binärer Suchschritt folgt.

    Dies hat viele Gemeinsamkeiten mit Ihrem Ansatz.

  • Adaptive Suche (AS) von Biagio Bonasera, Emilio Ferrara, Giacomo Fiumara, Francesco Pagano und Alessandro Provetti

    Mit den Worten der Autoren:

    [Interpolation-Binary Search] entwickelte eine ähnliche Lösung, die Interpolation und Binary Search kombiniert (aber nicht mischt). Obwohl die asymptotische Komplexität gleich ist, gibt es einige deutliche Unterschiede.

    [SCHNITT]

    Somit ist es möglich zu zeigen, dass für jeden Eingang AS nicht mehr Elementaroperationen als IBS benötigt.

    Der Algorithmus kann bis zu die doppelte Anzahl von Operationen als die "einfache" Interpolationssuche aufwenden, um die beste Halbierung des Suchsegments sorgfältig herauszufinden, was wiederum bedeutet, dass weniger Iterationen erforderlich sind, um die Suche abzuschließen (aber Sie haben einen noch größeren Overhead). .

Manlio
quelle
6

Das Verschachteln von zwei Algorithmen, um das Beste aus beiden Welten zu erzielen, ist eine bekannte Technik, obwohl normalerweise angegeben wird, dass sie "parallel" ablaufen und eine Antwort zurückgeben, sobald eine der beiden beendet wird.

Obwohl theoretisch schneller, hat die Interpolationssuche im Vergleich zur binären Suche zwei Nachteile:

  • Es hat schreckliche (lineare) Worst-Case-Performance

  • Der Aufwand für die Berechnung des Mittelpunkts ist ziemlich groß. Eine binäre Suchiteration ist hunderte Male schneller als eine Interpolationssuchiteration

Ich würde erwarten, dass ein Ansatz, bei dem Sie eine Interpolationssuche durchführen, während der Bereich groß ist, und zu einer binären Suche wechseln, wenn der Bereich klein wird, der effizienteste ist. Es wäre schön, wenn Sie dieses Experiment ausprobieren könnten.

Je kleiner Ihr Datensatz wird, desto größer ist der Unterschied zwischen Logn und LogLogn wird unbedeutend; Logn ist schon richtig klein und LogLognkönnte unmöglich viel kleiner sein. Zu diesem Zeitpunkt lohnt sich der Aufwand für die Durchführung der Interpolationssuche nicht im Vergleich zu den Iterationen, die Sie möglicherweise speichern.

Ich denke, dass Ihre Ergebnisse durch zwei Phänomene erklärt werden können:

  • Durch die Kombination mit der binären Suche können Sie das Worst-Case-Verhalten vermeiden

  • Der positive Effekt des Wechsels zur binären Suche in einem kleinen Datensatz

Tom van der Zanden
quelle
3
Sie haben geschrieben: "Eine binäre Suchiteration ist hunderte Male schneller als eine Interpolationssuchiteration". Beachten Sie, dass im Fall von OP der Unterschied zwischen der Berechnung des Mittelpunkts bei diesen beiden Methoden um die E / A-Zeit in den Schatten gestellt wird, die zum Abrufen des Mittelpunktwerts erforderlich ist.
Liori
@liori: Die ersten paar Iterationen wiederholter binärer Suchvorgänge mit denselben Daten sind möglicherweise cachefreundlicher, da dieselben wenigen Elemente verwendet werden. Es ist also zu erwarten, dass die Viertel und vielleicht Achtel im Cache heiß bleiben. Wenn die Bereiche groß genug sind, kann es sinnvoll sein, mit binär zu beginnen und nach drei Iterationen auf interpoliert umzuschalten. (Oder wenn Sie asynchrone E / A ausführen und das Ergebnis verwenden können, das zuerst eintrifft).
Peter Cordes
Auch bei einer Suche im Speicher hat ein Cache-Fehler (Latenzzeit über 200 Zyklen) die doppelte Latenzzeit einer 64-Bit-Ganzzahldivision (32-96 Zyklen), beispielsweise bei Intel Haswell . Die 32-Bit-Ganzzahldivision ist deutlich schneller (22-29 Zyklen). Die Hauptspeicherbandbreite ist eine gemeinsam genutzte Ressource für alle Kerne, die Ganzzahldivision verwendet jedoch nur Ressourcen, die auf jedem Kern doppelt vorhanden sind.
Peter Cordes
2
Die Speicherlatenz ist jedoch viel schlimmer als die Speicherbandbreite, da selbst mehrere verstreute Zugriffe schneller sind, wenn sie gleichzeitig im Flug sind. Es ist ein Gewinn, beide Möglichkeiten für die NEXT-Iteration (mit prefetcht0Anweisungen ) vorab abzurufen, bevor der aktuelle Mittelpunkt geladen wird, für eine speicherinterne Suche auf moderner x86-Hardware. Sie können dies nicht tun, wenn Sie die nächsten Abrufadressen nicht im Voraus vorhersagen können. So können neben theoretischen Überlegungen auch praktische Details der Implementierung von Bedeutung sein .
Peter Cordes
@liori: Definitiv I / O pro Mittelpunkt war der Hauptfaktor beim Indizieren einer Protokolldatei, da diese bei Bedarf gelesen wurde, um Datensätze zu finden. Es gab wahrscheinlich mehr als zwei Größenordnungen zwischen der Berechnung des Versatzes in der Datei und dem Lesen eines Blocks - daher wäre die Anzahl der berechneten Mittelpunkte der entscheidende Faktor. Ich denke, wenn ich jetzt ohne eine zu indizierende Protokolldatei repliziere - etwas, das ich versuchen werde, hier zu posten -, gibt es möglicherweise keinen messbaren Geschwindigkeitsunterschied, aber möglicherweise einen messbaren Unterschied "Anzahl der benötigten Mittelpunkte".
Neil Slater