Robert Sedgewick: Algorithmen

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


13. Externes Sortieren



Mehrphasen-Mischen

Ein Problem beim ausgeglichenen Mehrweg-Mischen für das Sortieren mit Hilfe von Bändern besteht darin, daß es entweder eine übermäßig große Anzahl von Bandeinheiten oder ein übermäßig häufiges Kopieren erfordert. Für das P-Weg-Mischen müssen wir entweder 2P Bänder verwenden (P für die Eingabe und P für die Ausgabe), oder wir müssen zwischen den Mischdurchläufen fast die gesamte Datei von einem einzigen Ausgabeband auf P Eingabebänder kopieren, wodurch sich die Anzahl der Durchläufe praktisch verdoppelt, so daß sie dann ungefähr 2 logP(N/2M) beträgt. Es wurden verschiedene zweckmäßige Bandsortieralgorithmen entwickelt, die praktisch dieses gesamte Kopieren überflüssig machen, indem sie die Art und Weise ändern, in der die kleinen sortierten Blöcke zusammengemischt werden. Die bekannteste dieser Methoden wird Mehrphasen-Mischen (polyphase merging) genannt.

Die dem Mehrphasen-Mischen zugrundeliegende Idee besteht darin, die durch Replacement Selection erzeugten sortierten Blöcke in gewisser Weise ungleichmäßig auf die verfügbaren Bandeinheiten zu verteilen (wobei eine leer bleibt) und dann eine Strategie der Art »Mischen, bis ein Band leer ist« anzuwenden, wonach eines der Ausgabebänder und das Eingabeband die Rollen tauschen.

Nehmen wir zum Beispiel an, daß wir nur drei Bänder haben, und daß wir mit der Anfangskonfiguration von sortierten Blöcken auf den Bändern beginnen, die die ersten Zeilen Abbildung 13.5 zeigen. (Diese ergibt sich bei Anwendung von Replacement Selection auf unsere Beispieldatei bei einem internen Speicher, in dem nur zwei Datensätze abgelegt werden können.) Band 3 ist ursprünglich leer, es ist das Ausgabeband für die ersten Mischoperationen. Nun wird nach drei Zweiweg-Mischoperationen von den Bändern 1 und 2 auf Band 3 das zweite Band leer, wie in der Mitte von Abbildung 13.5 zu sehen ist. Danach wird nach zwei Zweiweg-Mischoperationen von den Bändern 1 und 3 auf Band 2 das erste Band leer, wie im unteren Teil der Abbildung 13.5 dargestellt ist. Das Sortieren wird in zwei weiteren Schritten vollendet. Zuerst verbleibt nach einem Zweiweg-Mischen von den Bändern 2 und 3 auf Band 1 eine Datei auf Band 2 und eine Datei auf Band 1. Danach befindet sich nach einem Zweiweg-Mischen von den Bändern 1 und 2 auf Band 3 die gesamte sortierte Datei auf Band 3.

Abbildung 13.5
Abbildung 13.5 Anfangsetappen des Mehrphasen-Mischens mit drei Bändern.

Diese Strategie »Mischen, bis ein Band leer ist« läßt sich auf eine beliebige Zahl von Bändern übertragen. Abbildung 13.6 zeigt, wie sechs Bänder verwendet werden können, um 497 Anfangssequenzen zu sortieren. Wenn wir, wie in der ersten Spalte von Abbildung 13.6 angegeben, mit Band 2 als Ausgabeband, Band 1 mit 61 Anfangssequenzen, Band 3 mit 120 Anfangssequenzen usw. beginnen, ist nach der Durchführung eines Fünfweg-»Mischens, bis ein Band leer ist« Band 1 leer, auf Band 2 befinden sich 61 (lange) Sequenzen, auf Band 3 59 Sequenzen usw., wie es die zweite Spalte von Abbildung 13.6 zeigt. Zu diesem Zeitpunkt können wir Band 2 zurückspulen und es zu einem Eingabeband machen, und wir können Band 1 zurückspulen und es zum Ausgabeband machen. Indem wir in dieser Weise fortfahren, bekommen wir schließlich die gesamte sortierte Datei auf das Band 1. Das Mischen wird in viele Phasen zerlegt, welche nicht alle Daten einbeziehen, doch es ist kein direktes Kopieren erforderlich.

Abbildung 13.6
Abbildung 13.6 Verteilung der Sequencen für das Mehrphasen-Mischen mit sechs Bändern.

Die Hauptschwierigkeit beim Implementieren eines Mehrphasen-Mischens besteht darin zu bestimmen, wie die am Anfang vorliegenden Sequenzen zu verteilen sind. Es ist nicht schwer zu sehen, wie die obige Tabelle erhalten werden kann, wenn man rückwärts vorgeht: Man wähle die größte Zahl in jeder Spalte, mache sie zu Null und addiere sie zu jeder der anderen Zahlen, dann ergibt sich die vorangehende Spalte. Dies entspricht der Definition des Mischens der höchsten Ordnung für die vorangehende Spalte, welches die aktuelle Spalte ergeben kann. Diese Methode ist für jede beliebige Anzahl von Bändern (mindestens drei) anwendbar; die auftretenden Zahlen sind »verallgemeinerte Fibonacci-Zahlen«, die viele interessante Eigenschaften haben. Natürlich kann es sein, daß die Anzahl der am Anfang vorliegenden Sequenzen nicht im voraus bekannt ist, und wahrscheinlich wird es nicht exakt eine verallgemeinerte Fibonacci-Zahl sein. Daher muß eine Anzahl von »Pseudosequenzen« hinzugefügt werden, damit die Zahl der Anfangssequenzen genau den gemäß der Tabelle benötigten Wert hat.

Die Analyse des Mehrphasen-Mischens ist kompliziert und interessant, und sie liefert überraschende Ergebnisse. Zum Beispiel erweist es sich, daß die beste Methode des Verteilens von Pseudosequenzen auf die Bänder die Benutzung von zusätzlichen Phasen und von mehr Pseudosequenzen, als notwendig zu sein scheinen, erfordert. Der Grund dafür ist, daß einige Sequenzen viel öfter bei Mischoperationen verwendet werden als andere.

Wenn man eine möglichst effiziente Sortiermethode für Bänder implementieren will, muß man viele weitere Faktoren berücksichtigen. Ein wesentlicher Faktor, den wir überhaupt nicht in Betracht gezogen haben, ist die Zeit, die für das Zurückspulen eines Bandes benötigt wird. Diese Frage ist gründlich untersucht worden, und viele interessante Methoden wurden angegeben. Wie jedoch bereits erwähnt wurde, sind die gegenüber dem einfachen ausgeglichenen Mehrweg-Mischen erreichbaren Einsparungen recht begrenzt. Sogar das Mehrphasen-Mischen ist nur für kleine P besser als ausgeglichenes Mischen, und auch dann nur unwesentlich. Für P > 8 läuft ausgeglichenes Mischen im allgemeinen schneller ab als Mehrphasen-Mischen, und für kleinere P beruht der Effekt beim Mehrphasen-Mischen hauptsächlich auf der Einsparung von zwei Bändern (ein ausgeglichenes Mischen mit zwei zusätzlichen Bändern würde schneller ablaufen).


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