TStringlist: Performance & sort/sorted Frage

[alzaimar]

Übrigens geht es noch viel schneller: Es gibt eine Datenstruktur ('Skiplist'), die sehr schnell eine sortierte Liste aufbaut. Anstatt also die Strings in eine Stringlist einzufügen und dann zu sortieren, füge ich sie in die Skiplist ein und lese die Liste anschließend aus.
Ergebnis: Viel viel schneller als Quicksort (QS ist vom Aufwand O(n log n), Die Skiplist-Version ist O(n)...
(1000ms vs. 70ms bei 100000 Strings)

Hier der Code:

Delphi-Quellcode:

Var
  sKey : String;
  sSkipList : TcsSkipList; // <-- The magic Listenstruktur
  slData : TStringList;
  i : Integer;

Begin
  slData := TStringlist.Create;
  sSkipList := TcsStringSkipList.Create(16);
  Try
    for i:=0 to 100000 do 
      sSkipList.Insert(intToStr (100000 - i),nil);
    sSkipList.First;
    While not sSkipList.EndOfList do begin
      sSkipList.CurrentData(sKey,nil);
      slData.Add(sKey);
      sSkipList.Next;
    End;
  Finally
    sSkipList.Free;
  End;
...
End;