Ich habe mal den
Algorithmus im Wiki nachgebaut. Der Vorteil ist, das man den Speicherbedarf festlegen hat. Das Verfahren degeneriert also nicht und funktioniert auch bei beliebig großen Dateien,
ist dafür aber langsamer. [Edit]: Nö, sogar schneller.
Im Prinzip passiert Folgendes:
1. Eingabedatei wird in einzelne Abschnitte a <MaxSize> Bytes unterteilt:
1.1 Es werden solange Zeilen eingelesen, bis die Gesamtgröße <MaxSize> erreicht.
1.2 Diese Stringliste wird in-memory sortiert (TStringlist.Sort)
1.3 Abschließend wird diese Liste in einer temporären Datei gespeichert.
2. Ein K-Merge Algorthmus vermischt die K-temporaren Dateien (jeweils sortiert)
Dabei ist (1.2) der eigentliche Bottleneck, obwohl Quicksort zu den schnellsten Sortieralgorithmen gehört.
Kann man das optimieren?
Antwort: Ja.
Der Trick: Wir verwenden eine spezielle (String)Listenstruktur, die Strings beim Einfügen gleich sortiert ablegt und speichern dann den Inhalt in einer Datei ab. Normalerweise würde man das mit einem Array machen, per Binärsuche die Einfügeposition suchen und dort einfügen. Man könnte auch einen Binärbaum verwenden. Das ist aber unter dem Strich nicht schneller als Quicksort, da beide Verfahren vom Aufwand O(log n) sind. Was also tun?
Glücklicherweise existiert eine Listenstruktur, die wesentlich schneller ist: SkipLists. Der Aufwand zum Einfügen eines Objektes ist annähernd O(1), ggü O(log n) bei Binärsuche. Beim Einfügen von n Elementen werde ich also mit einer Skipliste in O(n) fertig sein, ggü O(n log n) bei einer Binärsuche bzw. Quicksort.
Herkömlicher Code:
Delphi-Quellcode:
While not Eof (Inputfile) do begin
ReadLn (Inputfile, sText);
sStringList.Add (sText);
End;
sStringList.Sort;
sStringList.SaveToFile (OutputFilename);
optimierter Code;
Delphi-Quellcode:
While not Eof (Inputfile) do begin
ReadLn (Inputfile, sText);
sSkipList.Add (sText);
End;
Assignfile (OutputFile, OutputFilename);
Rewrite (OutputFile);
sSkipList.First; // Iterator auf 1.Element setzen
While Not sSkipList.EndOfLine Do Begin // Solange noch Elemente in der Liste sind
Writeln (OutputFile, sSkipList.CurrentKey); // Aktuellen Iterator-Wert speichern
sSkiplist.Next; // Zum nächsten Wert gehen
End;
CloseFile (OutputFile);
Anstatt also eine Stringliste zu füllen und anschließend zu sortieren, fülle ich eine Skiplist und speichere den Inhalt ab, indem ich die Liste sequentiell von vorne nach hinten durchlaufe. Der Inhalt ist damit automatisch sortiert
Mit dieser Optimierung sortiert die vorgestellte Klasse eine 6MB-Textdatei in 1.6 anstatt 6.3 Sekunden (bei 1MB Puffer).
150MB werden in 60 Sekunden sortiert, ggü. 160 Sekunden mit herkömmlichem Sort (bei 10MB Puffer).
Auch wenn die hier vorgestellte Klasse langsamer sein sollte, als Satty67's Version (wovon ich mal ausgehe), könnte man das Skiplist-Verfahren auf seine Klasse anwenden, um sie noch weiter zu optimieren.