Effiziente Out-Of-Core-Sortierung

Question

Ich versuche herauszufinden, wie man einen riesigen Datensatz, der nicht in den Speicher passt, effizient sortiert. Die naheliegende Antwort auf einer hohen Ebene besteht darin, eine ganze Reihe von Chunks zu sortieren, die mit einem Standardalgorithmus in den Speicher passen, diese auf die Festplatte zu schreiben und sie dann zusammenzuführen. Zusammenführen ist das Problem.

Angenommen, die Daten werden in C-Chunks aufgeteilt, sodass ich C-Dateien zusammenführen muss. Wenn ich einen C-Weg-Merge in einem Durchgang mache, dann habe ich technisch einen O (N^2) -Algorithmus, obwohl dieser nur O (N) -Schreibvorgänge auf dem Datenträger ausführen muss. Wenn ich sie iterativ in C/2-Dateien, dann C/4-Dateien usw. zusammenführe, dann habe ich einen O (N log N) -Algorithmus, aber einen, der O (N log N) schreibt, schreibt auf Platte und hat daher ein riesiger konstanter Begriff.

Was ist die typische Lösung für dieses Rätsel? Gibt es einen guten?

Answer 1

Die einfache Antwort ist, dass es keine einfache Antwort auf diese Frage gibt. Es gibt viele Antworten, von denen die meisten ziemlich komplex sind - Knuth Volume 3 (für ein Beispiel) widmet ihm viel Raum.

Eine Sache, die offensichtlich wird, wenn sie durch suchen, was getan worden ist, dass man wirklich die Anzahl der Dateien minimieren möchten, dass Sie während Ihrer ersten Sortierung erstellen, und die Länge jeder zu maximieren. Um dies zu tun, möchten Sie im Allgemeinen so viele Daten einlesen, wie Sie in den Speicher einpassen können, aber anstatt sie nur zu sortieren und auszugeben, möchten Sie sie in einen Haufen zusammenfassen. Wenn Sie dann jeden Datensatz ausschreiben, lesen Sie IN einen anderen Datensatz und legen ihn in Ihren Heap. Während Sie jeden nachfolgenden Datensatz vom Heap in die Datei schreiben, prüfen Sie, ob er größer ist als die vorhandenen Datensätze. Wenn nicht, entfernen Sie es aus dem Heap und fügen es in einen anderen Heap ein. Fahren Sie dann mit dem nächstkleineren Datensatz im ersten Heap fort. Sie hören auf, Datensätze in die aktuelle Datei zu stellen, wenn der erste Heap vollständig leer ist und Ihr zweiter Heap Ihren gesamten Speicher belegt. An diesem Punkt fangen Sie an, Datensätze in eine neue Datei zu schreiben und "vertauschen" Sie die Verwendung der beiden Haufen.

Dadurch werden in der Anfangsphase wesentlich längere Zwischendateien erzeugt, so dass die Zusammenführung wesentlich weniger Arbeit erfordert.

Edit: Ich habe das sicherlich nicht erfunden - ich habe wahrscheinlich zuerst darüber in Knuth gelesen, aber vielleicht in Algorithmen + Datenstrukturen = Programme (Niklaus Wirth) - beide diskutieren es. Knuth schreibt die erste Veröffentlichung der Methode "H. Seward" in seiner Masterarbeit am MIT 1954 zu. Wenn Sie die zweite Ausgabe von Knuth haben, finden Sie sie auf Seite 254 von Band 3. Ich habe nie eine Kopie bekommen der dritten Ausgabe, also habe ich keine Seitennummer dafür.

Answer 2

Warum nicht das Problem aus einer anderen Perspektive betrachten. Wenn Sie zum Beispiel Namen sortieren, machen Sie einen Durchgang, sortieren Sie alles, was mit A-F beginnt, einen zweiten Durchlauf, der Strings sortiert, die mit G-M usw. beginnen. Dann können die Ergebnisse einfach der Reihe nach angefügt werden. Der Nachteil ist, dass die Daten gelesen von CD-C-Zeiten sein müssen.

Answer 3

Warum verwenden Sie die Algorithmen nicht in http://www.amazon.com/Art-Computer-Programming-Sorting-Searching/dp/0201896850?

Sie sind ziemlich gut und sorgfältig erklärt.

Answer 4

Eine gute Lösung ist external sorting. Überprüfen Sie speziell den externen Mergesort Algorithmus.

Externe Sortierung ist ein Begriff für eine Klasse von Sortieralgorithmen, die große Datenmengen verarbeiten kann. Externe Sortierung erforderlich ist, wenn die Daten passen nicht einer Computervorrichtung in den Hauptspeicher sortiert werden (in der Regel RAM) und stattdessen müssen sie in den langsameren externen Speicher (in der Regel ein Festplatte) befinden. Der typische externe Sortieralgorithmus verwendet eine Sortierzusammenführungs-Strategie , die mit der Sortierung kleiner Unterdateien beginnt. Der Basisalgorithmus besteht aus zwei Phasen: der Sortierung Phase und der Zusammenführungsphase. In der Sortierphase können die Teildateien in passen die verfügbare Pufferraum in den Hauptspeicher gelesen werden, sortiert ein internen Sortieralgorithmus verwendet, und zurück auf die Platte geschrieben als temporäre Subdateien sortiert. In der Zusammenführungsphase werden die sortierten Subdateien während ein oder mehrere Durchgänge zusammengeführt.

Answer 5

Nick hat Recht, externe Sortierung verwenden. Ihre C-way-Zusammenführung impliziert übrigens nicht O (N^2). Verwenden Sie eine Prioritätswarteschlange für die Zusammenführung und es ist immer noch O (N lg N).

Sie können sich auch cache oblivious algorithms zum Sortieren ansehen.

Answer 6

Es ist lustig, als ich diese gleiche Frage vor einem Monat hörte ... und die Antwort, die unser lokaler Guru auch gab.

„Verwenden Sie die Unix Art Befehl“

Obwohl wir admitedly dachte, dass es ein Witz auf Kosten der Fragesteller war ... es stellt sich heraus, dass es nicht. Die Argumentation ist, dass diese schlauen Jungs bereits viel darüber nachgedacht haben, wie man das Problem sehr großer Dateien lösen kann, und eine sehr beeindruckende Implementierung gefunden haben, die die verfügbaren Ressourcen gut ausnutzt.

Deshalb, es sei denn, Sie planen, das Rad neu zu erfinden: dh Sie haben Zeit und das ist geschäftskritisch, dann ist die einfache Verwendung der unix sort wahrscheinlich eine ausgezeichnete Idee.

Der einzige Nachteil ist seine arkane Syntax. This page ist dem Befehl und verschiedenen Erklärungen gewidmet.

Mein persönlicher Tipp: Nehmen Sie eine kleine Probe der Daten zum Testen, dass der Befehl effektiv genau das tut, was Sie wollen.

Answer 7

Sortieren Sie, oder erstellen Sie eine neue Kopie? Wenn Sie an Ort und Stelle sortieren, ist eine Speicher-Mapping-IO in der Regel eine gute Option. Ordnen Sie einfach Ihre gesamte Datei zu und führen Sie eine Zusammenführung durch. Das Betriebssystem speichert so viele Dateien wie möglich im Speicher und minimiert je nach Datensatz den IO-Wert.

Wenn Sie Ihren eigenen Sortieralgorithmus schreiben, besteht ein Trick darin, Ihre Richtung nach jedem Durchlauf umzukehren. Also, wenn du deinen ersten Passierst, beginnst du von Anfang bis Ende, dann gehst du von Ende zu Anfang auf deinem zweiten Pass. Wenn Sie Ihre Dateien in die Teile A, B, C und D aufteilen, sollten Sie nach dem Sortieren von C und D C und D zusammenführen und nicht zu A und B zurückkehren. Der Grund dafür ist natürlich, dass Ihr Betriebssystem Teile der Dateien in den Speicher, und Sie möchten den Cache so viel wie möglich verwenden.