6.5 Vergleich der nicht-linearen Suchverfahren

Wir haben nun die

• binäre Suche
• die Sprungsuche
• die Indexsuche und
• die Interpolationssuche

als nicht-lineare Suchverfahren kennengelernt. Alle vier Verfahren funktionieren nur, wenn die zu durchsuchende Sammlung von Elementen aufsteigend oder absteigend sortiert ist, wobei natürlich das Sortierkriterium mit dem Suchkriterium übereinstimmen muss. Die Suche nach einem Interpreten in einer nach Kaufdatum sortierten CD-Sammlung kann natürlich nur linear (sequentiell) erfolgen.

Auf dieser Seite wollen wir nun das Zeitverhalten der vier nicht-linearen Suchalgorithmen experimentell erforschen.

6.5.1 Die Klasse VergleicheSuchverfahren

Auf den oben genannten Seiten finden Sie kurze Quelltexte zu den einzelnen Suchverfahren, die aber noch nicht lauffähig sind. Sie müssen jeweils noch in eine Java-Klasse eingebettet werden. Diese Aufgabe sollte für Sie aber kein Problem darstellen.

Ich habe dann die KI ChatGPT gebeten, aus den vier von mir implementierten Java-Methoden eine große Klasse VergleicheSuchverfahren zu erstellen, mit der die vier Suchverfahren verglichen werden können.

Meine Vorgaben dabei waren:

• Es sollen aufsteigend sortierte int-Arrays mit 64, 128, 256, 512, 1024 und 2048 Elementen untersucht werden.
• Der Wertebereich der Arrayelemente soll zwischen 1 und 5000 liegen.
• Bei den vier Algorithmen soll nur die Zahl der erforderlichen Vergleiche mitgezählt werden. Eine Methode wie sprungsuche() liefert also nicht den Index der gefundenen Zahl (oder -1) zurück, sondern die Anzahl der erforderlichen Vergleiche.

Den kompletten und sehr langen Quelltext dieser von ChatGPT erstellten Klasse können Sie hier als Java-Datei herunterladen:

Die Klasse VergleicheSuchverfahren

Die Klasse wurde unter BlueJ und IntelliJ getestet, sie funktioniert dort einwandfrei.

6.5.2 Ergebnisse der Vergleiche

Wir wollen uns nun die Ergebnisse dieser Untersuchung anschauen und betrachten dazu die Konsolenausgabe des Programms:

Vergleich von vier Suchverfahren
Suchanfragen: alle Zahlen von 1 bis 5000

       n        Sprungsuche         Indexsuche      Interpolation        Binaersuche
          (gesamt / mittel)  (gesamt / mittel)  (gesamt / mittel)  (gesamt / mittel)
----------------------------------------------------------------------------------------------------
      64      91032 /  18,21      83743 /  16,75      29934 /   5,99      59982 /  12,00
     128     114770 /  22,95     115771 /  23,15      29870 /   5,97      69712 /  13,94
     256     151441 /  30,29     179692 /  35,94      29742 /   5,95      79290 /  15,86
     512     199152 /  39,83     307549 /  61,51      29486 /   5,90      88504 /  17,70
    1024     271109 /  54,22     562964 / 112,59      28972 /   5,79      96960 /  19,39
    2048     367891 /  73,58    1073763 / 214,75      27950 /   5,59     103886 /  20,78

Links sieht man jeweils die Gesamtzahl der Vergleiche für alle 5000 Suchzahlen, rechts daneben jeweils den Mittelwert für das Suchen nach einer Zahl.

Es stellt sich heraus, dass - wie bereits vermutet - die Interpolationssuche das schnellste Verfahren ist, gefolgt von der Binärsuche. Die Sprungsuche ist auf Platz 3, und am langsamsten ist die Indexsuche.

Auffällig ist insbesondere das Verhalten der Interpolationssuche bei wachsender Arraygröße n. Während bei den anderen Verfahren die Zahl der Vergleiche mit zunehmendem n mehr oder weniger deutlich ansteigt, bleibt sie bei der Interpolationssuche nahezu konstant. Das ist mathematisch gut erklärbar: Bei gleichmäßig verteilten Werten kann die Position der Suchzahl sehr genau abgeschätzt werden, sodass häufig schon der erste berechnete Zugriff direkt zum Ziel führt oder nur noch sehr wenige Nachvergleiche nötig sind.

Die Binärsuche zeigt ebenfalls ein recht günstiges Verhalten. Ihre Zahl der Vergleiche wächst nur logarithmisch mit n, also ungefähr proportional zu log₂(n). Selbst bei einer Verdopplung der Arraygröße steigt der Aufwand daher nur um etwa einen zusätzlichen Vergleich.

Die Sprungsuche ist deutlich langsamer als die Binärsuche, aber immer noch schneller als die Indexsuche.

Bei der Indexsuche kann ein Hilfsarray den Einstieg in die Suche verbessern, doch entsteht ein zusätzlicher Aufwand durch das Suchen im Index und durch die anschließende Suche im betreffenden Intervall.