Sortieralgorithmus: Große Textdatei mit Zeilen variabler Länge (durch Komma getrennte Werte)

Question

Was ist ein guter Algorithmus zum Sortieren von Textdateien, die größer als verfügbarer Speicher (viele 10 GByte) sind und Datensätze mit variabler Länge enthalten? Alle Algorithmen, die ich gesehen habe, gehen davon aus, dass 1) Daten in den Speicher passen oder 2) Datensätze fester Länge sind. Aber stellen Sie sich eine große CSV-Datei, die ich durch das „Geburtsdatum“ -Feld (das vierte Feld) sortieren wollte:

Id,UserId,Name,BirthDate 
1,psmith,"Peter Smith","1984/01/01" 
2,dmehta,"Divya Mehta","1985/11/23" 
3,scohen,"Saul Cohen","1984/08/19" 
... 
99999999,swright,"Shaun Wright","1986/04/12" 
100000000,amarkov,"Anya Markov","1984/10/31" 

Ich weiß, dass:

1. Dies liefe auf einer Maschine (nicht verteilt).
2. Die Maschine, auf der ich das ausführen würde, hätte mehrere Prozessoren.
3. Die Dateien, die ich sortieren würde, könnten größer sein als der physische Speicher der Maschine.
4. Eine Datei enthält Zeilen variabler Länge. Jede Zeile würde aus einer festen Anzahl von Spalten bestehen (durch Trennzeichen getrennte Werte). Eine Datei würde nach einem bestimmten Feld sortiert (dh nach dem vierten Feld in der Datei).
5. Eine ideale Lösung wäre wahrscheinlich "verwenden Sie diese vorhandene Sortier-Dienstprogramm", aber ich bin auf der Suche nach dem besten Algorithmus.
6. Ich erwarte keine vollständig codierte, funktionierende Antwort; etwas mehr in Richtung "check this out, hier ist so, wie es funktioniert, oder hier ist, warum es gut für dieses Problem funktioniert." Ich weiß einfach nicht, wo ich suchen soll ...
7. Das sind keine Hausaufgaben!

Vielen Dank! ♥

Answer 1

Diese Klasse von Algorithmen wird externe Sortierung genannt. Ich würde damit beginnen, die Wikipedia entry zu überprüfen. Es enthält einige Diskussionen und Hinweise.

Answer 2

Eine standardmäßige Zusammenführungssortierung funktioniert. Das gemeinsame Schema ist

1. Split die Datei in N Teile von ungefähr gleicher Größe
2. Sortieren jedes Teil (im Speicher, wenn es klein genug, sonst rekursiv den gleichen Algorithmus anwenden)
3. die sortierten Teile Merge

Answer 3

Schlagen Sie die folgenden Ressourcen:

Merge Sortieren: http://en.wikipedia.org/wiki/Merge_sort

Seminumerical Algorithmen, Vol. 2 der Kunst der Computerprogrammierung: Knuth: Addison Wesley: ISBN 0-201-03822-6 (v.2)

Answer 4

Keine Notwendigkeit zu sortieren. Lesen Sie die Datei ALL.CSV und hängen Sie jede gelesene Zeile an eine Datei pro Tag an, z. B. 19841231.CSV. Lesen Sie für jeden vorhandenen Tag mit Daten in numerischer Reihenfolge diese CSV-Datei und hängen Sie diese Zeilen an eine neue Datei an. Optimierungen sind beispielsweise möglich, indem Sie die Originaldatei mehr als einmal bearbeiten oder Tage erfassen, die tatsächlich in der Datei ALL.CSV vorkommen.

Also eine Zeile mit "1985/02/28" sollte der Datei 19850228.CSV hinzugefügt werden. Die Datei 19850228.CSV sollte an NEW.CSV angehängt werden, nachdem die Datei 19850227.CSV an NEW.CSV angehängt wurde.Die numerische Reihenfolge vermeidet die Verwendung aller Sortieralgorithmen, obwohl sie das Dateisystem foltern könnte.

In der Realität könnte die Datei ALL.CSV in einer Datei pro Jahr aufgeteilt werden. 1984. CSV, 1985. CSV, und so weiter.