Diskussion:Interpolationssuche

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)

Das Beispiel hinkt, denn um die Interpolationssuche auf Strings anzuwenden, müsste die Operation „String − String“ erstmal definiert werden, und es müsste eine Ganzzahl ergeben. Du hast aber recht, dass man beim Implementieren der Interpolationssuche auf Rundungsfehler aufpassen muss. --RolandIllig (Diskussion) 23:56, 17. Nov. 2023 (CET)

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)

Das klingt unglaubwürdig. Vom Schema her müsste die Interpolationssuche mit nur einem Schritt die richtige Position finden, da du gesagt hast, dass die Elemente gleichverteilt aufsteigend sortiert sind. --RolandIllig (Diskussion) 23:32, 17. Nov. 2023 (CET)

Da muss ich Dir zustimmen. Ich habe den Test mit einem Excel-Makro selbst durchgeführt und die betreffenden Zahlen wurden jedes Mal gleich beim ersten Versuch gefunden.

Dann habe ich den Test mit Zufallszahlen wiederholt. Jede Zahl war um eine Zufallszahl aus 100 größer, als die vorherige. Mindestens eine Zahl wurde trotzdem immer gleich beim ersten Versuch gefunden und maximal waren es meistens 9 Versuche. Einmal waren es nur 8. Ich habe den Test mehrfach wiederholt.

Ich gehe davon aus, dass die IP entweder einen Fehler in der Formel hatte, oder dass sie - wie bei der Binären Suche - den Code hat warten lassen, bis sich der Anfang und das Ende des Suchbereichs, auf der gleich Position befunden haben. Die Ausstiegsbedingung ist aber der gefundene Wert. --Zahlenzauber (Diskussion) 00:34, 16. Mär. 2024 (CET)

Ich muss noch eine Kleinigkeit hinzufügen: Die IP hatte teilweise doch Recht, denn ich habe eben einen weiteren Test durchgeführt, in dem ich die eine Million Zahlen im Bereich von 1 bis 2.000.000.000 in der Form einer Sinuskurve von 270° bis 360° habe ansteigen lassen. Hier benötigte die Interpolationssuche um die Zahlen zu finden, jeweils bis zu 145 Schritte. Für derartige Datenmuster ist die Interpolationssuche daher in der Tat komplett ungeeignet und viel zu langsam. --Zahlenzauber (Diskussion) 23:33, 16. Mär. 2024 (CET)

Der Autor hatte einen Fehler gemacht, weshalb der Beitrag unzutreffende Ergebnisse enthält. Der Beitrag sollte daher archiviert oder gelöscht werden.

Dieser Abschnitt kann archiviert werden. --Zahlenzauber (Diskussion) 17:21, 16. Mär. 2024 (CET)

Wann die Interpolationssuche geeignet ist und wann nicht

Ich habe den Verdacht, dass die Interpolationssuche nur dann gute Ergebnisse liefern kann, wenn die Werte "relativ gleichmäßig" ansteigen. Wenn die Werte jedoch gleich zu Beginn schnell ansteigen und die Kurve dann schnell abzuflachen beginnt, wie bei 0° bis 90° einer Sinuskurve, dann kann es dazu kommen, dass die Interpolationssuche sehr viele Durchläufe benötigt und um ein vielfaches langsamer ist, als zum Beispiel die Binäre Suche. Das gleiche gilt für den Fall, wenn die Werte exponentiell ansteigen, wie bei 270° bis 360° einer Sinuskurve. --Zahlenzauber (Diskussion) 16:37, 18. Mär. 2024 (CET)

Interpolationssuche = Dreisatz-Rechnung

So wie ich die Sache sehe, sollte man im Artikel noch darauf hinweisen, dass die Interpolationssuche im Kern auf einer Dreisatz-Rechnung basiert. Als Beleg dafür habe ich die Formel mal ein wenig umgestellt:

P = L + ( (R - L) / Array(R) - Array(L) ) x (Suchwert - Array(L))

Ihr werdet sehen, dass meine Formel identisch funktioniert. --Zahlenzauber (Diskussion) 13:31, 24. Mär. 2024 (CET)

Es gibt eine weitere Analogie, nämlich die zur Geradengleichung $f(x)=m\cdot x+c$ bzw. in etwas ausführlicherer Schreibweise $f(x)={\frac {f(x2)-f(x1)}{x2-x1}}\cdot x+c$. Bei der Interpolationssuche ist das f(x) bekannt, nämlich der Suchwert, und das x als Position im Array gesucht. Daher stellen wir um: $x={\frac {1}{m}}\cdot (f(x)-c)$ bzw. $x={\frac {x2-x1}{f(x2)-f(x1)}}\cdot (f(x)-c)$. Setzen wir die von Zahlenzauber verwendeten Variablennamen ein, erhalten wir   $P={\frac {R-L}{Array(R)-Array(L)}}\cdot (Suchwert-Array(L))$. Im Vergleich zu oben fehlt lediglich das einleitende "$L~+~$". Im ersten Schleifendurchlauf ist $L=0$. In weiteren Durchläufen wandert L gegebenenfalls nach rechts und beeinflusst daher das zu berechnende P.

Ja, die Darstellung solcher Querverweise halte ich für sinnvoll.

--Kelti (Diskussion) 15:27, 21. Aug. 2024 (CEST)

Formulierungen

Der Artikel verwendet den Begriff "Anzahl verschiedener Elemente". Damit ist aber keineswegs die Anzahl verschiedener bzw. unterschiedlicher Elemente gemeint. Vielmehr geht es um den numerischen Wert der Differenz zwischen dem größten (letzten) und kleinstem (erstem) Element des aktuellen Suchraums. Wie kann man das am besten formulieren? "Differenz zwischen ..." ist wohl zu lang, "Anzahl möglicher Werte" ist eine eher unverständliche Formulierung, ... . Hat jemand einen prägnanten Vorschlag? --Kelti (Diskussion) 15:31, 21. Aug. 2024 (CEST)