Robert Sedgewick: Algorithmen

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


13. Externes Sortieren



Viele wichtige Sortier-Anwendungen erfordern die Verarbeitung von sehr umfangreichen Dateien, die viel zu groß sind, um in den Hauptspeicher eines Computers zu passen. Methoden, die für derartige Anwendungen geeignet sind, werden externe Methoden genannt, da sie eine große Anzahl an Operationen außerhalb der Zentraleinheit erfordern (im Gegensatz zu den internen Methoden, die wir bisher untersuchten).

Es gibt zwei Hauptfaktoren, welche bewirken, daß externe Algorithmen sich sehr von den bisher betrachteten unterscheiden. Zum einen liegen die Kosten des Zugriffs auf ein Element um Größenordnungen höher als irgendwelche Verwaltungs- oder Berechnungskosten. Zweitens sind zusätzlich zu diesen höheren Kosten starke Einschränkungen des Zugriffs vorhanden, die von dem verwendeten externen Speichermedium abhängig sind: Zum Beispiel kann auf Elemente auf einem Magnetband nur sequentiell zugegriffen werden.

Die große Vielfalt hinsichtlich der Typen und Kosten bei externen Speichereinheiten bewirkt, daß die Entwicklung externer Sortiermethoden sehr stark von der vorhandenen Ausstattung abhängt. Diese Methoden können kompliziert sein, und viele Parameter beeinflussen ihre Leistungsfähigkeit; beim externen Sortieren ist es durchaus möglich, daß eine raffinierte Methode infolge einer einfachen Veränderung in der technischen Ausstattung unzweckmäßig oder unbrauchbar wird. Aus diesem Grunde konzentrieren wir uns in diesem Kapitel weniger auf die Entwicklung spezifischer Implementationen als vielmehr auf allgemeine Methoden.

Kurz gesagt, ist für das externe Sortieren der »systembezogene« Aspekt des Problems sicher ebenso wichtig wie der »algorithmische« Aspekt. Beide Seiten müssen sorgfältig betrachtet werden, wenn eine effiziente externe Sortiermethode entwickelt werden soll. Die primären Kosten beim externen Sortieren entstehen bei der Ein- und Ausgabe. Eine gute Übung für jemanden, der ein effizientes Programm zum Sortieren einer sehr umfangreichen Datei zu implementieren beabsichtigt, besteht darin, zuerst ein effizientes Programm zum Kopieren einer umfangreichen Datei zu implementieren und dann (falls das zu einfach war) ein effizientes Programm zur Umkehrung der Reihenfolge der Elemente in einer umfangreichen Datei zu implementieren. Die systembezogenen Probleme, die auftreten, wenn man versucht, diese Probleme effizient zu lösen, sind den Problemen ähnlich, die bei externen Sortierverfahren auftreten. Das Permutieren einer großen externen Datei auf irgendeine nichttriviale Weise ist etwa genauso kompliziert wie das Sortieren der Datei, auch wenn keine Vergleiche von Schlüsseln usw. erforderlich sind. Beim externen Sortieren beschäftigen wir uns in der Hauptsache damit, die Anzahl der Übertragungen von Datenelementen zwischen externem und internem Speicher zu minimieren und dafür zu sorgen, daß diese Übertragungen mit der der zur Verfügung stehenden Hardware möglichen maximalen Effizienz ausgeführt werden.

Es wurden externe Sortiermethoden entwickelt, die für die Lochkarten und Lochstreifen der Vergangenheit geeignet sind, andere für die Magnetbänder und Magnetplatten der Gegenwart und wieder andere für die Technologien der Zukunft, wie Blasenspeicher und optische Platten. Die Hauptunterschiede zwischen den verschiedenen Geräten sind die jeweilige Größe und Geschwindigkeit des verfügbaren Speichers und die Arten der Einschränkungen des Zugriffs auf die Daten. Wir konzentrieren uns auf grundlegende Methoden für das Sortieren auf Magnetband und Magnetplatte, weil diese Einheiten weiterhin weit verbreitet bleiben dürften und die beiden grundsätzlich verschiedenen Arten des Zugriffs illustrieren, die für viele externe Speichersysteme charakteristisch sind. Oft besitzen moderne Computersysteme eine »Speicherhierarchie« aus verschiedenen Speichern, von denen jeder langsamer, billiger und größer ist als die vorangehenden. Viele der Algorithmen, die wir betrachten werden, können so angepaßt werden, daß sie in einer solchen Umgebung gut laufen. Wir werden uns jedoch ausschließlich mit »Zwei-Ebenen«-Speicherhierarchien beschäftigen, die aus dem Hauptspeicher und einer Platte oder einem Band bestehen.


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