Interpolationssuche vs binäre Suche

Wann sollte ich die Interpolationssuche anstelle der Binärsuche verwenden?

Ich habe beispielsweise einen sortierten Datensatz. In welchen Situationen würde ich die binäre Suche verwenden, um ein Element in diesem Datensatz zu finden, oder in welchen Situationen sollte ich die Interpolationssuche verwenden?

Welche Eigenschaften des Datensatzes wären ausschlaggebend?

Um eine Interpolationssuche durchzuführen, benötigen Sie natürlich einen Schlüsseltyp, für den mehr als die Reihenfolge bekannt ist. Sie müssen in der Lage sein, Berechnungen mit den Schlüsseln durchzuführen, um eine wahrscheinliche Entfernung abzuschätzen, und nicht nur Schlüssel zu vergleichen, um festzustellen, welche größer oder größer sind geringer.

Was die Eigenschaften des Datensatzes anbelangt, handelt es sich meistens um eine Eigenschaft: eine Wahrscheinlichkeit, dass die Schlüssel über den Bereich der Möglichkeiten hinweg einigermaßen gleichmäßig (oder zumindest vorhersehbar) verteilt sind. Ohne das kann eine Interpolationssuche tatsächlich langsamer sein als eine binäre Suche.

Betrachten Sie beispielsweise einen Datensatz mit Zeichenfolgen aus Kleinbuchstaben als Schlüssel. Angenommen, Sie haben einen Schlüssel, der mit "x" beginnt. Eine Interpolationssuche zeigt deutlich an, dass Sie kurz vor dem Ende des Satzes mit der Suche beginnen sollten. Wenn jedoch die meisten Ihrer Tasten tatsächlich mit 'z' beginnen und fast keine mit 'a' bis 'y', befindet sich die gesuchte Taste möglicherweise sehr nahe am Anfang des Sets. Es kann / kann eine beträchtliche Anzahl von Iterationen dauern, bis sich die Suche dem Anfang nähert, an dem sich die mit 'w' beginnende Zeichenfolge befindet. Jede Iteration würde nur ~ 10% des Datensatzes aus der Betrachtung entfernen, so dass es mehrere Iterationen dauern würde, bis der Anfang erreicht ist, an dem die Schlüssel mit 'w' beginnen.

Im Gegensatz dazu würde eine binäre Suche startet in der Mitte, erhält auf die ein Viertel Zeichen bei der zweiten Iteration, ein Achtel Markierung auf dem dritten und so weiter. Die Leistung würde durch die Neigung der Tasten kaum beeinträchtigt. Bei jeder Iteration wird die Hälfte des Datensatzes aus der Prüfung entfernt, als ob die Schlüssel gleichmäßig verteilt wären.

Ich beeile mich jedoch hinzuzufügen, dass es wirklich eine ziemlich verzerrte Verteilung erfordert, um eine Interpolationssuche merklich schlechter als eine binäre Suche zu machen. Es kann zum Beispiel auch bei relativ vielen lokalisierten Clustern eine recht gute Leistung erbringen.

Ich sollte auch erwähnen, dass eine Interpolationssuche nicht unbedingt eine lineare Interpolation verwenden muss. Wenn beispielsweise bekannt ist, dass Ihre Tasten einer nichtlinearen Verteilung folgen (z. B. einer Glockenkurve), kann dies in der Interpolationsfunktion relativ einfach berücksichtigt werden, um Ergebnisse zu erhalten, die sich kaum von einer gleichmäßigen Verteilung unterscheiden.

Ich denke, die Frage ist wahrscheinlich, wie einfach Sie eine Interpolationsfunktion finden können, die tatsächlich besser ist als die binäre Suche.

Aus Wikipedia über Interpolation Search:

Unter Verwendung der Big-O-Notation ist die Leistung des Interpolationsalgorithmus für einen Datensatz der Größe N O (N); Unter der Annahme einer gleichmäßigen Verteilung der Daten auf der für die Interpolation verwendeten linearen Skala kann gezeigt werden, dass die Leistung 0 ist (log log N).

Die praktische Leistung der Interpolationssuche hängt davon ab, ob die verringerte Anzahl von Sonden durch die komplizierteren Berechnungen aufgewogen wird, die für jede Sonde erforderlich sind. Dies kann nützlich sein, um einen Datensatz in einer großen sortierten Datei auf der Festplatte zu lokalisieren, bei der jeder Test eine Festplattensuche beinhaltet und viel langsamer als die Interpolationsarithmetik ist.

Indexstrukturen wie B-Trees reduzieren auch die Anzahl der Festplattenzugriffe und werden häufiger zum Indizieren von On-Disk-Daten verwendet, da sie viele Datentypen indizieren und online aktualisiert werden können. Die Interpolationssuche kann jedoch hilfreich sein, wenn bestimmte sortierte, aber nicht indizierte Datasets auf der Festplatte durchsucht werden müssen.

Die binäre Suche und die Interpolationssuche werden beide als lineare Suchmethoden betrachtet.

Beide erwarten, dass die zu durchsuchende Liste nach der als Schlüssel bezeichneten Spalte sortiert wird . Dies ist sehr wichtig.

Die binäre Suche funktioniert für Zeichenfolgen oder Zahlen, sofern diese in sortierter Reihenfolge gespeichert sind. Die primäre Idee hinter der binären Suche ist, dass sie auf der Untersuchung des mittleren Elements basiert. Die Interpolationssuche ist eine Variante. Anstatt das exakte mittlere Element zu verwenden, wird erraten, wo sich das nächste Element befindet, das mit dem übergebenen Wert verglichen werden soll. Weitere Informationen zur Berechnung des nächsten Schlüsselwerts durch den Interpolationssuchalgorithmus finden Sie in der Referenz von JB King oder in der Antwort weiter unten in dieser Antwort.

"Die Interpolationssuche funktioniert nur für numerische Elemente, die in einer sortierten Array-Reihenfolge mit gleichmäßiger Verteilung angeordnet sind (dh der Abstand zwischen beliebigen bis aufeinanderfolgenden Elementen ist ungefähr konstant)." ).

Google Books - Klassische Datenstrukturen 2. Aufl.