|
Sortieren auf Datenträger
Solange alle Daten im Hauptspeicher Platz haben, stimmen die obigen Aufwandsabschätzungen. In vielen Fällen sind die Datenmengen aber so groß, daß sie nur in großen Dateien auf Datenträgern Platz finden.
Meist wird nach einem Schlüssel (Kundennummer, Namen, ...) sortiert und die übrigen Daten (Adresse, ...) werden mitkopiert. Die Aufgabe vereinfacht sich stark, wenn es möglich wird, den Schlüssel sowie den Verweis auf den dazugehörigen Datensatz (Record-Nummer) im Speicher unterzubringen.
In jedem Fall erfordert der langsame Zugriff auf Dateien ganz andere Lösungsstrategien für Sortierverfahren.
Nutzung des Hauptspeichers
Um auch größere Datenmengen effizient sortieren zu können, muß man den zur Verfügung stehenden Speicher effizient nutzen. Man muß also versuchen, einen möglichst großen Teil des Hauptspeichers für das Programm zu reservieren, um möglichst wenig auf den sehr viel langsameren (Faktor 1000 und mehr) Sekundärspeicher (Festplatte, ...) zurückgreifen zu müssen.
Optimierungen
Bei der Aufwandsabschätzung zählt man die Größenordnung der geleisteten Arbeit. Allerdings kann der Einsatz gezielter Optimierungen (natürlich unter Verwendung von Kenntnissen über die interne Verarbeitung durch den Compiler und Hardware) die Abschätzung völlig auf den Kopf stellen.
Es muß daher immer sorgfältig betrachtet werden, ob nicht weitergehende Annahmen (zum Beispiel in Hinblick auf Struktur und Umfang der zu erwarteten Datenmenge) im Einzelfall gezielte Optimierungen erlauben.
Beispiele
1. MergeSort: Für die Subprocedure Merge wird das Hilfsarray Ziel benötigt. Deklariert man das Hilfsarray als lokale Variable innerhalb von Merge anstatt global zu Merge, benötigt der Algorithmus die zehnfache Zeit, da nun bei jedem Aufruf (also insgesamt n*ld(n)-mal) die Variable Ziel (400 KB!) neu am Stack angelegt und anschließend wieder vernichtet werden muß.
2. QuickSort: Wird statt der globalen Procedure swap das Vertauschen von zwei Variablen schon innerhalb des Sortieralgorithmus implementiert, so verbessert sich die Performance um ca. 30%, da nun die Procedureaufrufe für swap entfallen.
3. usw.
|
