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

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.

Habe ich über eine bekannte Sache gestolpert?

Es gibt verschiedene Methoden, die auf einer Mischung aus Interpolationssuche und Binärsuche basieren, mit a $O(log\ log\ n)$ durchschnittliche Fallzugriffszeit (gleichmäßige Verteilung) und $O(log\ 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). .

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 $\log n$ und $\log \log n$ wird unbedeutend; $\log n$ ist schon richtig klein und $\log \log n$kö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