Diskussion:Interpolationssuche

Quellen

• englischer Artikel: Interpolation Search
• Robert Sedgewick: Algorithmen in C. Addison-Wesley. 1992. S. 239-241.

Korrektur VB-Quellcode

Es fehlt eine Klammer und zusätzlich wird das deklarierte position durch pos ersetzt.

Zur Klammer:

position = left + Math.Floor((right - left) * (key - array(left) / diffElem)

Muss heißen:

position = left + Math.Floor((right - left) * (key - array(left)) / diffElem)

Begründung (siehe Artikel):

$x=l+{\frac {v-A[l]}{A[r]-A[l]}}\cdot (r-l)$ (nicht signierter Beitrag von 79.248.97.184 (Diskussion) 20:16, 15. Mai 2011 (CEST))

Korrektur Quellcode

Nehmen wir ein Array wie ["Anton", "Claus", "Dieter","Emil"] .

Suchen wir mit den hier gezeigten Formeln nach "Bernd", landen wir in einer Endlosschleife und nie vor dem Anfang oder hinter dem Ende des Arrays. Der größtnötige Schleifendurchlauf muss irgendwo unterhalb 1+Anzahl-Array-Elmenten/2 liegen. Mehr Durchläufe braucht man nicht um sicher sagen zu können, dass "Bernd" nicht in diesem Array vorkommt. Wenn die Sprungweite unter 0.5 gesunken ist, gibt es ebenfalls kein Ergebnis, Bzw. immer den selben erfolglosen Vergleich. Das wäre dann immer noch schneller als eine "Bubble-Suche". Selbstverständlich muss der Fall, dass der Index außerhalb des Arrays liegt, abgefangen werden. Sonst gäbe es eine Fehlermeldung. Aber soweit dürfte es hier gar nicht kommen. -- Kinetics (Diskussion) 14:55, 25. Apr. 2013 (CEST)

Vergleich zwischen der binären Suche und der Interpolationssuche

Hinweis:

Dieser Beitrag soll nicht direkt als Anregung für die Artikel der binäre Suche und der Interpolationssuche dienen, sondern er soll eine zusätzliche Orientierungshilfe für die Autoren bereitstellen.

Ich habe mir mal die Mühe gemacht, die binäre Suche und die Interpolationssuche gegeneinander antreten zu lassen. Ich habe dafür beide Algorithmen jede Zahl in einem Array mit einer Million Werten suchen lassen und in jedem Fall geprüft, wie oft der eine oder andere Algorithmus schneller war.

• Die binäre Suche hat jeweils maximal nur 20 Versuche gebraucht, um eine Zahl zu finden und war in 915.982 Fällen (91,6%) schneller. Insgesamt wurden 18.951.445 Zahlen aus dem Array ausgelesen.
• Die Interpolationssuche hat jeweils bis zu 68 Versuche gebraucht, um eine Zahl zu finden und war nur in 59.507 Fällen (6%) schneller. Insgesamt wurden 27.794.621 Zahlen aus dem Array ausgelesen.
• In 24.511 Fällen (2,4%) waren beide Algorithmen gleich schnell.

Ich komme daher zu dem Schluss, dass die Interpolationssuche - aufgrund ihrer Arbeitsweise - bei derart großen Zahlen- / Datenmengen, für den praktischen Einsatz komplett ungeeignet ist, weil sie bei einer Million Werten, in 94% der Fälle, bis zu 3,4 Mal langsamer ist, als die binäre Suche.

Die Interpolationssuche ist der binären Suche gegenüber aber auch bei kleineren Zahlen- / Datenmengen haushoch unterlegen. Bei 1000 zu durchsuchenden Werten, ist die Interpolationssuche nur in 11,3% der Fälle schneller als die binäre Suche. Bei 100 Werten sind es 17% und bei 10 Werten 20%. Das zeigt, dass die Interpolationssuche für den praktischen Einsatz grundsätzlich ungeeignet ist. --77.21.163.85 15:29, 14. Dez. 2020 (CET)

Wie hast Du die eine Million Werte ermittelt? Danke 194.174.73.80 18:03, 27. Jan. 2021 (CET) Marco PB

@ 194.174.73.80

Hallo! Ich habe das in Excel mit einem Makro (Visual Basic) gemacht. Ich habe hierfür ein Array mit einer Million Werten eingerichtet (Dim lngArray(1000000) as Long) und dann jeder Stelle den Wert ihrer Position gegeben. Also lngArray(1)=1 ... lngArray(1000000)=1000000. Dann habe ich der Reihe nach die Positionen der Zahlen 1 bis 1000000 suchen lassen. Excel eignet sich für solche Experimente besonders gut. --77.21.163.85 15:38, 15. Mai 2021 (CEST)