Datei-basierten merge-sort auf große Datenmengen in Java

Java bietet eine Allzweck-Sortier-routine, die verwendet werden können, als Teil der größeren Lösung für Ihr problem. Ein gemeinsamer Ansatz, um Daten zu Sortieren, das ist zu groß, um alles in den Speicher passt, ist diese:

1) Lesen, wie viel Daten passen in Hauptspeicher, sagen wir, es ist 1 Gb

2) Quicksort 1 Gb (hier ist, wo Sie verwenden würden, der Java-built-in-Art aus den Sammlungen framework)

3) Schreiben, die sortiert 1 Gb auf der Festplatte als "chunk-1"

4) Wiederholen Sie die Schritte 1-3, bis Sie gegangen durch alle Daten, speichern jedes Daten-chunk in einer separaten Datei. Also, wenn Sie Ihre original-Daten wurde mit 9 Gb, die Sie haben jetzt 9 sortiert Datenblöcke mit der Aufschrift "Brocken-1" thru "chunk-9"

5) nun müssen nur eine Letzte merge-sort merge-9 sortiert Stücke in eine vollständig sortierte Daten festgelegt. Der merge-sort funktioniert sehr effizient gegen diese vorsortiert zu präsentieren. Es wird im wesentlichen open 9-Datei-Leser (eine für jeden Block), plus einer Datei writer (für die Ausgabe). Es vergleicht dann die erste data-element in jeder Datei Lesen, und wählt den kleinsten Wert, der in die Ausgabedatei geschrieben. Die Leser aus, die den ausgewählten Wert kam, Vorschüsse auf seine nächste Datenelement aus, und die 9-Wege-Vergleich-Prozess zu finden, der kleinste Wert wird wiederholt, wieder das schreiben der Antwort an die Ausgabe-Datei. Dieser Vorgang wird wiederholt, bis alle Daten gelesen wurden, von allen chunk-Dateien.

6) Nachdem Schritt 5 beendet ist, Lesen alle Daten, die Sie fertig sind -- output-Datei enthält nun eine vollständig sortierte Datensatz

Mit diesem Ansatz könnte man einfach schreiben Sie eine generische "megasort" Nützlichkeit des eigenen, nimmt Sie einen Dateinamen und maxMemory parameter und effizient sortiert die Datei durch die Verwendung von temp-Dateien. Ich würde Wetten, Sie finden konnte, zumindest ein paar Implementierungen gibt für diese, aber wenn nicht, können Sie nur Rollen Sie Ihre eigenen, wie oben beschrieben.