Tutorien für Algorithmen und Datenstrukturen 2

Aufgabe 8-2

(Übungsblatt 8)

Die folgenden Teilaufgaben beziehen sich allgemein auf die in der Vorlesung behandelten Verfahren zum Suchen und Finden von Daten; es können beliebige Bedingungen an die Speicherung der Daten gestellt werden (etwa, dass sie sortiert sein müssen). Begründen Sie jeweils Ihre Antwort, z. B. durch Nennung des Namens eines geeigneten Verfahrens.

1. Gibt es ein Suchverfahren, das regelmäßig (also im average case) mit konstantem Zeitaufwand O(1) zum Ergebnis führt?
2. Gibt es ein Suchverfahren, das im average case einen höheren als linearen Zeitaufwand O(n) hat?
3. Gibt es ein Suchverfahren, das im worst case einen geringeren als linearen Zeitaufwand O(n) hat?
4. Welche(s) Verfahren sollten Sie selbst bevorzugt einsetzen? Weshalb?

Lösungsvorschlag

zu den Teilaufgaben:

1. Ja: Der Zugriff auf eine gute Hash-Tabelle liefert in der deutlichen Mehrzahl der Fälle das gewünschte Element beim ersten Zugriff zurück.

   Eine Hash-Table ist eine Datenstruktur, in der Elemente möglichst an vorausberechneten Positionen abgelegt sind. Diese Positionen lassen sich beim Zugriff sehr schnell aus dem Schlüssel erneut berechnen und sollen so den direkten Zugriff ermöglichen. Nur dann, wenn für mehrere Elemente dieselbe Position berechnet wird, kommt es zu etwas längeren Laufzeiten. Siehe Kapitel 6 „Hash-Verfahren“ der Vorlesung „Algorithmen und Datenstrukturen 1.“

   Der Zugriff auf eine Hash-Table hat im best case O(1), im average case ebenfalls O(1) und im worst case O(n). Dieses traumhafte Laufzeitverhalten erkauft man sich mit einem vergleichsweise hohen Speicherbedarf.

   In Java implementieren mehrere Klassen im Package java.util Hash-Tabellen, beispielsweise LinkedHashMap.

2. Nein: Bei n Elementen kann ich natürlich immer das gesuchte finden, indem ich jedes Element genau einmal anschaue. Dies entspricht aber gerade der sequentiellen Suche, so dass man besser die nehmen könnte.

   (Praktisch gesehen kann man natürlich jeden lahmen Schrott programmieren, und einige Entwickler tun das auch regelmäßig. Die Frage bezog sich aber selbstverständlich auf sinnvolle Suchverfahren.)

3. Ja: Die binäre Suche hat sowohl im average case als auch im worst case O(log n).

4. Der Hauptsatz der Software-Entwicklung lautet: Gar kein Code ist der beste Code.

   Demzufolge sollte von allen existierenden Algorithmen immer derjenige gewählt werden, der so einfach wie möglich und so schnell wie nötig ist. Dies ergibt sich auch aus der Überlegung, dass es bei den heutigen schnellen Computern wenig bringt, für nur ein paar Dutzend Elemente optimale Suchalgorithmen zu implementieren, aber im Gegensatz dazu die Wartbarkeit von Software immer mehr zum Problem wird.

   • In Java bietet die Klasse java.util.Arrays eine Methode binarySearch zur binären Suche an. Zum Suchen in sortierten Arrays sollte immer diese Methode benutzt werden.

   • Zum Suchen in linearen Listen (z. B. Instanzen von LinkedList) und anderen Klassen aus java.util sollte eine sequentielle Suche bevorzugt werden. Das geht am besten mit einem Iterator über die Methode iterator().

   • Ergebnisse einer SQL-Abfrage über JDBC können mit Hilfe der Methode next() sequentiell durchsucht oder durchlaufen werden.

   • Andere Datenstrukturen erfordern meist eine eigene Implementierung. Im Zweifel sollten Sie zunächst mit einer sequentiellen Suche beginnen.

   Nach Fertigstellung der Implementierung sollte die Geschwindigkeit ausgiebeig getestet werden. Nur, wenn sie dann nicht ausreicht, sollte über trickreiche Optimierungen wie Interpolations- oder Fibonaccisuche nachgedacht werden.