Robert Sedgewick: Algorithmen

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


13. Externes Sortieren



Ausgeglichenes Mehrweg-Mischen

Zuerst wollen wir die verschiedenen Schritte der einfachsten Misch-Sortier-Prozedur für ein kleines Beispiel nachvollziehen. Nehmen wir an, daß wir Datensätze mit den Schlüsseln A S O R T I N G A N D M E R G I N G E X A M P L E auf einem Eingabeband haben; diese sollen sortiert und auf einem Ausgabeband gespeichert werden. Die Benutzung eines »Bandes« besagt einfach, daß wir darauf beschränkt sind, die Datensätze sequentiell zu lesen: Der zweite Datensatz kann nicht vor dem ersten gelesen werden usw. Wir nehmen weiterhin an, daß wir im Speicher unseres Computers Platz für drei Datensätze haben, daß uns jedoch beliebig viele Bänder zur Verfügung stehen.

Der erste Schritt besteht darin, jeweils drei Datensätze der Datei einzulesen und diese zu sortieren, so daß Blöcke aus drei Datensätzen entstehen, und die sortierten Blöcke auszugeben. Folglich lesen wir zuerst A S O ein und geben den Block A O S aus, lesen danach R T I ein und geben den Block I R T aus usw. Um nun diese Blöcke zusammenzumischen, müssen sie sich auf verschiedenen Bändern befinden. Wenn wir ein Dreiweg-Mischen vornehmen wollen, würden wir drei Bänder verwenden, wobei wir nach dem Sortierdurchlauf zu der in Abbildung 13.1 dargestellten Konfiguration gelangen würden.

Abbildung 13.1
Abbildung 13.1 Ausgeglichenes Dreiweg-Mischen: Ergebnis des ersten Durchlaufs.

Nun können wir die sortierten Dreier-Blöcke mischen. Wir lesen den ersten Datensatz jedes Eingabebands ein (hierfür ist im Speicher gerade genug Platz) und geben denjenigen mit dem kleinsten Schlüssel aus. Danach wird der nächste Datensatz von demjenigen Band eingelesen, von dem der gerade ausgegebene Datensatz stammt, und es wird wiederum der Datensatz im Speicher mit dem kleinsten Schlüssel ausgegeben. Wenn das Ende eines aus drei Wörtern bestehenden Blocks bei der Eingabe erreicht ist, wird das betreffende Band ignoriert, bis die Blöcke der anderen beiden Bänder verarbeitet worden sind und neun Datensätze ausgegeben sind. Danach wird der Prozeß wiederholt, um die jeweils zweiten aus drei Wörtern bestehenden Blöcke auf jedem Band zu einem Block aus neun Wörtern zusammenzumischen (welcher auf ein anderes Band ausgegeben wird, als Vorbereitung für die folgende Mischoperation). Indem wir in dieser Weise fortfahren, erhalten wir die in Abbildung 13.2 dargestellten drei langen Blöcke.

Abbildung 13.2
Abbildung 13.2 Ausgeglichenes Dreiweg-Mischen: Ergebnis des zweiten Durchlaufs.

Nun kann das Sortieren durch ein weiteres Dreiweg-Mischen vollendet werden. Wenn wir eine wesentlich längere Datei mit vielen Blöcken der Größe 9 auf jedem Band hätten, würden wir den zweiten Durchlauf mit Blöcken der Größe 27 auf den Bändern 1, 2 und 3 beenden, danach würde ein dritter Durchlauf Blöcke der Größe 81 auf den Bändern 4, 5 und 6 erzeugen usw. Wir benötigen sechs Bänder, um eine beliebig große Datei zu sortieren: drei für die Eingabe und drei für die Ausgabe bei jedem Dreiweg-Mischen. (In Wirklichkeit könnten wir mit nur vier Bändern auskommen: Die Ausgabe könnte auf ein einziges Band erfolgen, und dann könnten die Blöcke von diesem Band zwischen den Mischdurchläufen auf die drei Eingabebänder verteilt werden.)

Diese Methode wird Ausgeglichenes Mehrweg-Mischen (balanced multiway merge) genannt. Sie stellt einen sinnvollen Algorithmus für das externe Sortieren und einen guten Ausgangspunkt für die Implementation eines externen Sortierverfahrens dar. Die weiter unten betrachteten komplizierteren Algorithmen können den Ablauf des Sortierens etwas beschleunigen, jedoch nicht sehr. (Allerdings kann, wenn die Ausführungszeiten in Stunden gemessen werden, was bei externem Sortieren nicht ungewöhnlich ist, auch eine Verkürzung der Laufzeit um wenige Prozent sehr viel ausmachen.)

Nehmen wir an, daß N Wörter zu sortieren sind und der interne Speicher die Größe M hat. Dann erzeugt der »Sortier«-Durchlauf ungefähr N/M sortierte Blöcke. (Bei dieser Schätzung werden aus einem Wort bestehende Datensätze vorausgesetzt. Für umfangreichere Datensätze läßt sich die Anzahl der sortierten Blöcke berechnen, indem außerdem noch mit der Größe der Datensätze multipliziert wird.) Wenn wir bei jedem der aufeinanderfolgenden Durchläufe P-Weg-Mischoperationen ausführen, beträgt die Anzahl der aufeinanderfolgenden Durchläufe ungefähr logp(N/M), da jeder Durchlauf die Anzahl der sortierten Blöcke um den Faktor P verringert.

Auch wenn kleine Beispiele helfen können, die Einzelheiten des Algorithmus zu verstehen, ist es bei der Arbeit mit externen Sortierverfahren am besten, an sehr umfangreiche Dateien zu denken. Zum Beispiel besagt die obige Formel, daß die Anwendung eines Vierweg-Mischens zum Sortieren einer aus 200 Millionen Wörtern bestehenden Datei auf einem Computer mit Speicherplatz für eine Million Wörter insgesamt ungefähr fünf Durchläufe erfordern dürfte. Eine sehr grobe Schätzung für die Laufzeit läßt sich erhalten, indem man die Laufzeit für die oben vorgeschlagene Implementation der Herstellung der Kopie einer Datei in umgekehrter Reihenfolge mit fünf multipliziert.


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