Robert Sedgewick: Algorithmen

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


13. Externes Sortieren



Replacement Selection

Es zeigt sich, daß die Einzelheiten der Implementation in eleganter und effizienter Weise entwickelt werden können, wenn man Prioritätswarteschlangen benutzt. Zunächst überzeugen wir uns davon, daß Prioritätswarteschlangen eine natürliche Möglichkeit bieten, um ein Mehrweg-Mischen zu implementieren. Was noch wichtiger ist, es erweist sich, daß wir Prioritätswarteschlangen für den ersten Sortierdurchlauf dergestalt benutzen können, daß sie sortierte Blöcke erzeugen können, die viel länger sind, als daß sie im internen Speicher Platz finden würden.

Die grundlegende Operation, die benötigt wird, um das P-Weg-Mischen auszuführen, besteht darin, wiederholt das kleinste unter den kleinsten noch nicht ausgegebenen Elementen von jedem der P zu mischenden Blöcke auszugeben. Dieses kleinste Element muß dann durch das nächste Element aus dem Block, aus dem es stammte, ersetzt werden. Die replace- (Ersetzen) Operation in einer Prioritätswarteschlange der Größe P ist genau das, was benötigt wird. (In Wirklichkeit sind die »indirekten« Varianten der Routinen für Prioritätswarteschlangen, die in Kapitel 11 beschrieben wurden, für diese Anwendung besser geeignet.) Um ein P-Weg-Mischen vorzunehmen, füllen wir zuerst eine Prioritätswarteschlange der Größe P mit dem kleinsten Element jeder der P Eingaben unter Verwendung der Prozedur pqinsert aus Kapitel 11 (entsprechend modifiziert, so daß sich anstelle des größten das kleinste Element an der Spitze des Heap befindet). Danach geben wir unter Verwendung der Prozedur pqreplace aus Kapitel 11 (in der gleichen Weise modifiziert) das kleinste Element aus und ersetzen es in der Prioritätswarteschlange durch das nächste Element aus seinem Block.

Der Prozeß des Mischens von A O S mit I R T und A G N (die erste Mischoperation aus unserem obigen Beispiel) unter Verwendung eines Heaps der Größe drei im Mischprozeß ist in Abbildung 13.3 dargestellt. Die »Schlüssel« in diesen Heaps sind die kleinsten (ersten) Schlüssel in jedem Knoten. Um der Klarheit willen stellen wir ganze Blöcke in den Knoten des Heaps dar; natürlich würde eine richtige Implementation ein indirekter Heap aus Zeigern sein, die auf die Blöcke weisen. Zuerst wird A ausgegeben, so daß O (der nächste Schlüssel in seinem Block) zum »Schlüssel« der Wurzel wird. Dadurch wird die Heap-Bedingung verletzt, so daß der Knoten mit dem Knoten ausgetauscht wird, der A, G und N enthält. Danach wird jenes A ausgegeben und durch den nächsten Schlüssel in seinem Block - G - ersetzt. Dadurch wird die Heap-Bedingung nicht verletzt, so daß kein weiterer Austausch erforderlich ist. Indem wir in dieser Weise fortfahren, erzeugen wir die sortierte Datei (man lese jeweils den kleinsten Schlüssel im Wurzelknoten der Bäume in Abbildung 13.3, um die Schlüssel in der Reihenfolge zu sehen, in der sie auf der ersten Position des Heaps erscheinen und ausgegeben werden). Wenn ein Block erschöpft ist, wird eine Marke auf dem Heap gesetzt und als größer als alle anderen Schlüssel betrachtet. Wenn der Heap nur noch aus Marken besteht, ist das Mischen abgeschlossen. Diese Art der Verwendung von Prioritätswarteschlangen wird manchmal Replacement Selection (Auswählen mit Ersetzen) genannt.

Abbildung 13.3
Abbildung 13.3 Replacement Selection für das Mischen bei einem Heap der Größe 3.

Um ein P-Weg-Mischen zu realisieren, können wir somit Replacement Selection auf eine Prioritätswarteschlange der Größe P anwenden, um jedes auszugebende Element in log P Schritten zu bestimmen. Dieser Unterschied in der Leistungsfähigkeit hat keine besondere praktische Bedeutung, da eine »gewaltsame« Implementation jedes auszugebende Element in P Schritten finden kann und P normalerweise so klein ist, daß diese Kosten gegenüber den Kosten der tatsächlichen Ausgabe des Elements nicht ins Gewicht fallen. Die eigentliche Bedeutung von Replacement Selection besteht in der Art und Weise, wie es im ersten Teil des Misch-Sortier-Prozesses benutzt werden kann: um die am Anfang benötigten sortierten Blöcke zu bilden, die die Basis für die Misch-Durchläufe darstellen.

Die Idee besteht darin, die (ungeordneten) Eingabedaten eine große Prioritätswarteschlange durchlaufen zu lassen und dabei wie oben immer das kleinste Element in der Prioritätswarteschlange auszugeben und es durch das nächste Element aus den Eingabedaten zu ersetzen. Zusätzlich wird, falls das neue Element kleiner als das letzte ausgegebene Element ist und somit kein Bestandteil des aktuellen sortierten Blocks werden kann, dieses als Bestandteil des nächsten Blocks markiert und als größer als alle Elemente im aktuellen Block behandelt. Wenn ein markiertes Element an die Spitze der Prioritätswarteschlange gelangt, wird der alte Block abgeschlossen und ein neuer Block begonnen. Auch das läßt sich leicht mit pqinsert und pqreplace aus Kapitel 11 implementieren, nachdem geeignete Modifikationen vorgenommen wurden, so daß sich das kleinste Element an der Spitze des Heap befindet, und nachdem pqreplace so abgeändert wurde, daß es markierte Elemente grundsätzlich als größer als unmarkierte Elemente behandelt.

Unsere Beispieldatei veranschaulicht den Wert von Replacement Selection deutlich. Mit einem internen Speicher, der nur in der Lage ist, drei Datensätze zu speichern, können wir sortierte Blöcke der Größe 5, 3, 6, 4, 5 und 2 erzeugen, wie in Abbildung 13.4 dargestellt ist. Wie zuvor entspricht die Reihenfolge, in der die Schlüssel die erste Position im Heap einnehmen, der Reihenfolge, in der sie ausgegeben werden. Die Schattierung verdeutlicht, welche Schlüssel im Heap zu welchen verschiedenen Blöcken gehören: Ein Element, das genauso markiert ist wie das Element an der Wurzel, gehört zum aktuellen sortierten Block, und die anderen gehören zum nächsten sortierten Block. Die Heap-Bedingung (erster Schlüssel kleiner als der zweite und dritte) wird überall eingehalten, wobei die Elemente im nächsten sortierten Block als größer als die Elemente im aktuellen sortierten Block betrachtet werden. Die erste Sequenz endet mit I N G im Heap, da diese Schlüssel alle mit größeren Schlüsseln an der Wurzel eintrafen (so daß sie nicht in die erste Sequenz aufgenommen werden konnten), die zweite Sequenz endet mit A N D im Heap usw.

Abbildung 13.4
Abbildung 13.4 Replacement Selection für die Erzeugung der Anfangssequenzen.

Eigenschaft 13.1 Für zufällige Schlüssel besitzen die Sequenzen, die durch Replacement Selection erzeugt werden, ungefähr die doppelte Größe des verwendeten Heaps.

Der Beweis dieser Eigenschaft erfordert eine sehr komplizierte Analyse, doch die Behauptung läßt sich leicht experimentell überprüfen. w.z.b.w.

Die praktische Bedeutung dieser Eigenschaft besteht darin, daß ein Misch-Durchlauf eingespart wird: Anstatt mit sortierten Sequenzen zu beginnen, die etwa die Größe des internen Speichers haben, und dann einen Misch-Durchlauf vorzunehmen, um Sequenzen zu erzeugen, die etwa die doppelte Größe des internen Speichers haben, können wir sofort mit Sequenzen beginnen, die etwa doppelt so groß sind wie der interne Speicher, indem wir Replacement Selection mit einer Prioritätswarteschlange der Größe M benutzen. Wenn in den Schlüsseln eine gewisse Ordnung vorhanden ist, können die Sequenzen sehr viel länger sein. Wenn sich zum Beispiel bei keinem Schlüssel mehr als M größere Schlüssel vor ihm in der Datei befinden, ist die Datei im Ergebnis des Durchlaufs von Replacement Selection vollständig sortiert, und kein Mischen ist mehr erforderlich! Das ist der wichtigste praktische Grund für die Anwendung dieser Methode.

Insgesamt ergibt sich damit, daß die Technik des Replacement Selection sowohl für den Schritt »Sortieren« als auch für den Schritt »Mischen« bei einem ausgeglichenen Mehrweg-Mischen angewandt werden kann.

Eigenschaft 13.2 Eine Datei aus N Datensätzen kann unter Verwendung eines internen Speichers, in dem M Datensätze gespeichert werden können, und von P + 1 Bändern in ungefähr 1 + logP(N/2M) Durchläufen sortiert werden.

Wie bereits erläutert, benutzen wir zuerst Replacement Selection mit einer Prioritätswarteschlange der Größe M zur Erzeugung von Anfangssequenzen mit einer Länge von ungefähr 2M (in einer zufälligen Situation) oder mehr (falls die Datei teilweise geordnet ist) und benutzen dann Replacement Selection mit einer Prioritätswarteschlange der Größe P für ungefähr logp(N/2M) (oder weniger) Misch-Durchläufe. w.z.b.w.


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