12.3 Sprungsuche

Ergänzung für Studierende

Zeitverhalten der Sprungsuche

Das Grundprinzip der Sprungsuche wurde bereits in den vorhergehenden Abschnitten dieser Seite beschrieben. Der Abschnitt richtet sich jetzt an Studierende der Informatik in den ersten Semestern. Zunächst behandeln wir die Zeitkomplexität der Sprungsuche.

1. Zeitkomplexität der klassischen Sprungsuche

Die optimale Sprungweite k entspricht bei der klassischen Sprungsuche ungefähr der Quadratwurzel aus der Anzahl n der Arrayelemente. Da die Sprungweite eine ganze Zahl sein muss, wird entsprechend gerundet oder es wird eine ganzzahlige Division durchgeführt.

k = √n

Für ein Array mit 10.000 Elementen ergibt sich beispielsweise eine optimale Sprungweite von 100.

1.1 Worst case

Im ungünstigsten Fall sind bei einem Array mit 10.000 Elementen ungefähr 100 Sprünge notwendig, um den Block zu finden, in dem die Suchzahl vermutet wird. Da der Block 100 Elemente umfasst, sind im worst case noch einmal 100 weitere Vergleiche innerhalb dieses Blocks notwendig. Man käme also auf ca. 200 Vergleiche. Mit einer binären Suche hätte man die Suchzahl in log₂(10.000) = 13,28. Mit maximal 14 Vergleichen hätte man bei einer binären Suche also jede Zahl gefunden - auch im worst case.

Das Zeitverhalten für den worst case lässt sich mit O(√n) beschreiben.

1.2 Best Case

Im günstigsten Fall befindet sich die Suchzahl direkt am Anfang des Arrays (oder im ersten Block an der ersten Position). In diesem Fall ist bereits beim allerersten Vergleich (beim ersten Sprung) klar, dass das Element gefunden wurde. Man benötigt im best case also gerade einmal einen Vergleich.

Im Vergleich dazu benötigt eine binäre Suche im Bestfall (wenn das gesuchte Element zufällig genau in der Mitte des Arrays liegt) ebenfalls 1 Vergleich.

Das Zeitverhalten für den best case lässt sich mit O(1) beschreiben.

1.3 Average Case

Im durchschnittlichen Fall (bei einer gleichmäßigen Verteilung der Suchzahlen über das gesamte Array) muss man im Mittel die Hälfte der Blöcke durchspringen, also ca. 50 Sprünge. Innerhalb des gefundenen Blocks (der 100 Elemente umfasst) muss im Durchschnitt ebenfalls die Hälfte der Elemente linear durchsucht werden, also ca. 50 weitere Vergleiche. Man käme im Schnitt also auf ca. 100 Vergleiche

Mit einer binären Suche hätte man die Suchzahl mit 12 bis 13 Vergleichen deutlich schneller gefunden.

Das Zeitverhalten lässt sich ähnlich wie für den worst case mit O(√n) charakterisieren.

2. Vergleich mit anderen Suchverfahren

Die folgende Tabelle zeigt die ungefähre maximale Anzahl der Suchschritte für verschiedene Arraygrößen. Dabei wird vorausgesetzt, dass die Arrays bereits sortiert sind. Bei der Sprungsuche wird die optimale Sprungweite √n verwendet.

Die Tabelle zeigt sehr schön, dass die Sprungsuche wesentlich effizienter ist als die sequenzielle Suche. Gegenüber der binären Suche fällt sie bei sehr großen Arrays allerdings deutlich zurück. Die binäre Suche besitzt eine logarithmische Zeitkomplexität von O(log n), während die klassische Sprungsuche lediglich O(√n) erreicht.

3. Optimierung: Binäre Suche innerhalb des gefundenen Blocks

Eine naheliegende Verbesserung besteht darin, den gefundenen Block nicht sequenziell, sondern mit einer binären Suche zu durchsuchen.

3.1 Berechnung der maximalen Anzahl von Vergleichen bei dieser Optimierung.

Die Zahl der Sprünge unterscheidet sich nicht von der klassischen Sprungsuche (sequentielle Suche innerhalb der Blöcke). Die Zahl der Vergleiche berechnet sich hier für den worst case mit

V(n,k) = n/k

Die binäre Suche innerhalb des Zielblocks hat ein Zeitverhalten, dass mit

V(k) = log₂(k)

beschrieben werden kann. Insgesamt ergibt sich dann für die Zahl der Vergleiche:

T(n, k) = n/k + log₂(k)

Bei einem Array mit 10.000 Elementen und einer Sprungweite von 100 ergibt sich:

T(10.000, 100) = 100 + log₂(100) = 107

Gegenüber den ungefähr 200 Vergleichen der klassischen Sprungsuche bedeutet dies eine deutliche Verbesserung.

3.2 Eine weitere Optimierung

Wenn wir jetzt eine binäre Suche für das Finden der Suchzahl innerhalb der Blöcke verwenden, kann die Blockgröße durchaus größer sein. Die Zahl der Vergleiche ändert sich dadurch nur wenig. Wenn die Blockgröße doppelt so groß ist wie bisher (200 statt 100), ist nur ein Vergleich mehr notwendig, aber die Zahl der Sprünge wird halbiert. Bei einer Blockgröße von 400 sind zwei Vergleiche mehr notwendig als bei einer Blockgröße von 100, aber die Zahl der Sprünge beträgt nur noch ein Viertel der ursprünglichen Zahl.

Nehmen wir wieder unser Array aus 10.000 int-Zahlen und wählen eine Blockgröße von 400. Innerhalb der Blöcke wird binär gesucht.

Die Zahl der Vergleiche berechnet sich dann für den average case folgendermaßen:

Es muss durchschnittlich die Hälfte der Blöcke angesprungen werden, bei 25 Blöcken (1000 / 40) sind das ca. 12,5 Sprünge.

Innerhalb eines solchen Blocks beträgt die Zahl der Vergleiche bei der binären Suche im average case bei 8 bis 9.

Insgesamt ergibt sich dann ein Wert von ca. 21 Vergleichen - gegenüber den 100 Vergleichen bei der klassischen Sprungsuche (average case).

3.3 Vergleichender Überblick

4. Ist die Kombination aus Sprungsuche und binärer Suche sinnvoll?

4.1 Einwand

Man könnte nun kritisch einwenden: Wählen wir doch einfach eine Blockgröße von 10.000. Dann hätte man 0 Sprünge und maximal 14 Vergleiche, im average case sogar nur 13 Vergleiche. Das das Ganze wäre eine reine binäre Suche.

Für die praktische Anwendung der Sprungsuche auf gewöhnliche int-Arrays ergibt sich im Grunde kaum ein Vorteil. Wenn das gesamte Array bereits sortiert ist und auf jedes Element direkt über seinen Index zugegriffen werden kann, ist es in der Regel sinnvoller, sofort eine binäre Suche über das gesamte Array durchzuführen.

4.2 Dynamische Listen

Eine Sprungsuche könnte aber dann Sinn machen, wenn beispielsweise nicht direkt auf das mittlere Element einer Datenstruktur zugegriffen werden kann. Das ist beispielsweise bei einfach verketteten dynamischen Listen der Fall, die nicht auf einer Arraystruktur mit Direktzugriff basieren.

Angenommen, wir haben eine sortierte dynamische Liste mit 10.000 Elementen. Wir können dann nicht direkt das Element 5.000 anspringen, um eine binäre Suche durchzuführen.

Was man aber machen kann, ist der Einsatz eines Arrays von Referenzen, die auf jedes hundertste Element zeigen. Bei einer Suche vergleichen wir zunächst den Suchwert mit den Elementen, auf die diese Referenzen zeigen. Sobald wir ein Element gefunden haben, dessen Wert größer als der Suchwert ist, wissen wir, dass sich das gesuchte Element im vorhergehenden Block befinden muss.

Nun folgen wir der gespeicherten Referenz auf den Anfang dieses Blocks und durchsuchen die maximal 100 Elemente sequenziell. Da wir den Anfang des Blocks direkt über eine Referenz erreichen können, müssen wir nicht erneut vom Anfang der gesamten Liste aus suchen.

Dann springt man einen Block zurück und führt dann eine sequentielle Suche innerhalb dieses Blocks durch. Eine binäre Suche innerhalb des Blocks ist nicht möglich, da kein Direktzugriff auf die Elemente erfolgen kann.

Allerdings ist dieses Verfahren mit einem Nachteil verbunden: Sobald man Elemente in die dynamische Liste einfügt oder Element aus der Liste löscht, muss man die Referenzen neu setzen.

4.3 Externe Speicher

Ein weiteres mögliches Einsatzgebiet der Sprungsuche sind Daten, die nicht vollständig im Arbeitsspeicher liegen, sondern von einem externen Speichermedium gelesen werden müssen.

Bei der binären Suche wird der Suchbereich immer wieder halbiert. Dabei kann es notwendig sein, abwechselnd auf weit voneinander entfernte Speicherbereiche zuzugreifen. Bei einem gewöhnlichen Array im Arbeitsspeicher ist dies kein Problem, bei manchen externen Speichermedien können solche Zugriffe jedoch aufwendig sein, zum Beispiel bei Magnetbändern, die - man wundert sich - immer noch häufig eingesetzt werden, um Daten langfristig zu speichern.

Auch bei einem Netzwerk-Stream können die Daten häufig nur in einer Richtung gelesen werden. Ein beliebiger Rücksprung zu einer früheren Position ist dann nicht möglich.

In solchen Situationen kann eine Sprungsuche vorteilhaft sein. Die Daten werden nacheinander in größeren Blöcken in den Arbeitsspeicher eingelesen. Anhand des letzten Elements eines Blocks lässt sich feststellen, ob der gesuchte Wert innerhalb dieses Blocks liegen könnte.

Wenn das der Fall ist, wird der bereits eingelesene Block im Arbeitsspeicher durchsucht. Das kann jetzt durchaus mit einer binären Suche erfolgen.