| | |
| Titel: | Sortieralgorithmen | |
| Startseite english | ||
| ||
| |<< Anfang < Zurück Index Weiter > Ende >>| | |  |
Fallstricke und Fußangeln
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
- 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ß.
- 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.
- usw.
Zurück zu Themenseiten:
StudyPaper.com/Startseite/Computer/Informatik
StudyPaper.com/Startseite/Wissenschaft/Wirtschaftswissenschaften
StudyPaper.com/Startseite
Das Setzen von Verweisen (Links) auf diese Seite ist gestattet und bedarf keine vorherige Absprache.
