TStringlist: Performance & sort/sorted Frage

[kurtm1]

Habe mal eine generelle Frage zur Performance bzw. Verwendung der TStringlist.

Ziel ist es möglichst performant nach der Reihe eine Vielzahl an Elementen einzufügen und am Ende eine sortierte Liste zu erhalten. Generell gibts es zwei mögliche Ansätze:
1. Alle Elemente mit ".Add" einfügen und danach alle mittels ".Sort" sortieren
2. Die Stringlist auf ."Sorted:=true" setzen, womit die Stringlist zu jedem Zeitpunkt / Add Vorgang immer korrekt sortiert ist

Gehe ich richtig in der Annahme, dass Möglichkeit 1 schneller ist, da nicht nach "jedem" Add sortiert wird (oder ist es die 2. Option, da dort laut Delphi Hilfe immer an der alphabetisch korrekten Stelle eingefügt wird)?

[hazard999]

Guck dir einfach die O-Notation für den Avarage-Case an.

1. N + N * LD N
2. Summe von 1 BIS N für X von LD X

[jaenicke]

Bei dieser Frage eindeutig die zweite, denn es wird natürlich nicht jedesmal neu sortiert.

Allerdings ist eine TStringList sicher nicht die performanteste Lösung, die ist nur die einfachste Lösung, wenn man selbst sich nicht zu viele Gedanken drüber machen will.

[hoika]

Hallo,

also ich sage, die 1. ist einfacher.

Es ist einfacher, zuerst alle Einträge per Add hinzuzufügen
und zum Schluss zu sortieren.

Im zweiten Fall wird ja der Einfüge-Index gesucht.


Heiko

[hazard999]

@hoika:

Bitte begründen, in wie fern einfacher?

[hoika]

Hallo,

einfacher von der Performance her,
also schneller.


Heiko

[kurtm1]

hmm also (noch) keine eindeutige Antwort..

[hoika]

Hallo,

probier es einfach aus.
10.000 Einträge und testen.


Heiko

[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;