Sortieren einer 20GB-Datei mit einem String pro Zeile

Question

In Frage 11.5 von Gayle Laakman Buch Cracking the Technical Interview,

„Stellen Sie eine 20GB-Datei pro Zeile mit einem String haben. Erklären Sie, wie Sie die Datei sortieren würde“

Meine erste Reaktion war genau die Lösung, die sie vorschlug - die Datei in kleinere Stücke (Megabyte) aufteilen, indem XMb Daten eingelesen, sortiert und dann auf Platte geschrieben wurde. Und am Ende, füge die Dateien zusammen.

Ich habe mich dazu entschieden, diesen Ansatz nicht weiter zu verfolgen, da die endgültige Zusammenführung alle Daten im Hauptspeicher beinhalten würde - und wir gehen davon aus, dass dies nicht möglich ist. Wenn das der Fall ist, wie genau hält diese Lösung?

Mein anderer Ansatz basiert auf der Annahme, dass wir fast unbegrenzten Speicherplatz haben, oder zumindest genug, um die 2X der Daten, die wir bereits haben, zu halten. Wir können Daten von X mb einlesen und dann Hash-Schlüssel für sie generieren - jeder Schlüssel entspricht einer Zeile in einer Datei. Wir machen das so lange weiter, bis alle Werte geheilt sind. Dann müssen wir nur die Werte dieser Datei in die Originaldatei schreiben.

Lassen Sie mich wissen, was Sie denken.

Answer 1

http://en.wikipedia.org/wiki/External_sorting gibt eine detailliertere Erklärung, wie externe Sortierung funktioniert. Es befasst sich mit Ihrer Sorge, dass Sie eventuell die gesamten 20 gB in den Speicher bringen müssen, indem Sie erklären, wie Sie die letzten sortierten Stücke zusammenstellen, indem Sie Stücke der sortierten Stücke einlesen, anstatt alle sortierten Stücke gleichzeitig zu lesen.