n-Weg-Mischen

Das Zusammenfügen von Läufen ist jetzt eher eine prozessorintensive als eine harddiskintensive Operation. Die Einträge der temporären Datei müssen jetzt nämlich nachdem sie von Platte gelesen wurden dekomprimiert, bzw. bevor man sie wieder auf Platte schreibt komprimiert werden. Deshalb könnte man als weitere Verbesserung eine Technik anwenden, genannt multiway merging oder n-Weg-Mischen, die eine weitere Reduzierung der Laufzeit ermöglicht. Angenommen 4-Weg-Mischen wird verwendet, um die sortierten Läufe zusammenzufügen. Dadurch werden nur noch $\lceil \log_4 40\rceil = 3$ Durchgänge für die hypotetische Sammlung benötigt, die Laufzeit reduziert sich dadurch erheblich. Diese Herangehensweise kann weiter verfolgt weden: angenommen alle $L$ sortierten Läufe wurden in die temporäre Datei geschrieben. Nun könnte man mittels eines einzigen $L$-Weg-Mischens die gesamte Datei sortieren. Man muß dazu aus jedem der $L$ einzeln sortierten Läufe eine gleiche Anzahl von Einträgen in den Speicher laden, um diese dann zusamenzufügen. Dazu muß immer der Eintrag mit dem kleinsten Schlüssel gesucht und anschließend gespeichert werden.

Eine effiziente Datenstruktur für das Finden des Elements mit dem kleinsten Schlüssel aus einer teilweise sortierten Menge ist die Prioritätswarteschlange⁸. Das Einfügen eines Elements, bzw. das Entfernen des kleinsten Elements aus einer Prioritätswarteschlange der Größe $L$ kann jeweils mit einer Zeitkomplexität von $\mathcal{O}(\log L)$ durchgeführt werden. Auf diese Weise läßt sich die Laufzeit der sortierbasierten Inversion auf weniger als die Hälfte reduzieren.

Wir erhalten also einen sortierbasierten Inversionsalgorithmus, der durch die Verwendung komprimierter temporärer Dateien und durch $n$-Weg-Mischen in etwa drei Stunden und mit nur etwa 600 Mbytes an zusätzlichem Plattenplatz eine Dokumentensammlung von 5 Gbytes indexieren kann. Es gibt zwar noch eine Reihe weiterer Verbesserungsmöglichkeiten, die aber nur in Hinblick auf die Größe der zusätzlich verwendeten Plattenplatzes Vorteile mit sich bringen, sie haben also einen leicht schlechteren Laufzeitverhalten, als der hier vorgestellte. Auf die Analyse weiterer verbesserter Algorithmen wird an dieser Stelle verzichtet, dem interessierten Leser sei hier [3] empfohlen.