Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


13. Externes Sortieren



Ein einfacher Weg

Viele moderne Computersysteme verfügen über eine große virtuelle Speicherkapazität, die man beim Implementieren einer Methode für das Sortieren sehr großer Dateien nicht außer Acht lassen sollte. In einem guten virtuellen Speichersystem kann der Programmierer eine sehr große Menge an Daten adressieren und es der Verantwortung des Systems überlassen, dafür zu sorgen, daß die adressierten Daten bei Bedarf vom externen in den internen Speicher übertragen werden. Diese Strategie beruht auf der folgenden Tatsache, daß viele Programme einen relativ kleinen »Bezugsbereich« haben: Jede Bezugnahme auf den Speicher erfolgt mit hoher Wahrscheinlichkeit auf einen Bereich des Speichers, der relativ nahe bei anderen Bereichen liegt, auf die in letzter Zeit eine Bezugnahme erfolgte. Das hat zur Folge, daß Datenübertragungen vom externen zum internen Speicher häufig nicht erforderlich sind. Eine interne Sortiermethode mit einem kleinen Bezugsbereich kann mit einem virtuellen Speichersystem sehr gut realisierbar sein. (Zum Beispiel hat Quicksort zwei »Bezugsbereiche«: Die meisten Bezugnahmen erfolgen in der Nähe von einem der beiden Zerlegungszeiger.) Bevor man erwarten kann, erhebliche Einsparungen zu erzielen, sollte man jedoch den Systemprogrammierer konsultieren: Eine Methode von der Art des digitalen Sortierens, welche keinerlei Bezugsbereich besitzt, wäre in einem virtuellen Speichersystem katastrophal, und sogar Quicksort könnte Probleme verursachen, je nachdem, wie gut das zur Verfügung stehende virtuelle Speichersystem implementiert ist. Andererseits sollte die Strategie der Anwendung einer einfachen internen Sortiermethode für das Sortieren von auf Platten befindlichen Dateien in einem guten virtuellen Speichersystem ernsthaft in Erwägung gezogen werden.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]