Ich habe eine Textdatei, die eine sehr lange Liste von Elementen hat. Also möchte ich sie alphabetisch sortieren, aber ich möchte nicht die ganze Datei in den Speicher (RAM) laden.Wie sortiere ich eine Datei mit einer sehr langen Liste von Elementen?
Ich habe versucht, den gesamten Inhalt der Datei in ein Array zu laden und sie so zu sortieren, wie ich es normalerweise tue. Aber das System beschwert sich, dass es nicht viel Speicher gibt !!
Danke, Mohammad
Sie werden auf external sorting nachlesen müssen. Der grundlegende Ansatz besteht darin, eine Art von Divide-and-Conquer-Routine wie merge sort zu verwenden, in der Sie einen Teil der Datei lesen und sortieren, dann einen anderen Teil der Datei lesen und sortieren usw., und wenn Sie am Ende sind, werden Sie zusammengeführt die sortierten Teile zusammen.
Vielleicht hilft die STXXL (Standard Template Library für Extra Large Data Sets).
STXXL bietet external sorting unter anderem.
interessant .... –
Sie müssen nicht die gesamte Datei im Speicher halten. Wenn dies eine Aufgabe ist, die Sie nicht sehr oft ausführen müssen, können Sie eine Anwendung schreiben, die sie sehr langsam sortiert. So etwas (Pseudo):
Das heißt Auswahl Sortierung (fast), nicht die beste Idee. – unbeli
@unbeli: Ich weiß, es ist fast Auswahl Sortierung. Auswahl Sortierung sucht auch nach dem größten Wert. Aber ich schrieb: "Wenn das eine Aufgabe ist, die man nicht oft machen muss, ..." –
Auch wenn man es nicht oft macht, warum sollte sie einen schwachen Algorithmus implementieren, wenn es einen einfacheren gibt? – unbeli
Wenn Sie ein Unix-ähnliches Betriebssystem verwenden, können Sie den Befehl sort verwenden. Es wird sich um den Speicherverbrauch kümmern. Für ein Beispiel wird etwas wie "cat large_file | sort" die Aufgabe erledigen.
Oder Sie können Ihre eigenen schreiben/externe Sortierung aus der Bibliothek verwenden. Sagen Sie uns, welche Sprache Sie verwenden und vielleicht wird Ihnen jemand genau sagen, welche Bibliothek Sie verwenden sollen.
Sie können hier einen schönen Kurs über externe Sortierung anzeigen. http://video.google.com/videoplay?docid=-978892635109400080# –
Unter UNIX verwenden Sie die Befehlszeile: 'sort'. –