String in TStringList finden verschnellern?

[himitsu]

Das Tempo ist da logarithmisch und nicht linear.

* jeden Eintrag durchsuchen, also im Durchschnitt 50% aller Einträge, bis man was findet.
* die binäre Suche ist für Sortiertes optimiert, da man beim Vergleich sofort weiß, ob man was getroffen hat und wenn nicht, ob es vor oder hinter dem Eintrag zu finden ist

bei 1000 Einträgem
* linear = durchschnittlich 500 Vergleiche
* binär = maximal 10 Vergleiche


Zusätzlich noch CaseSensitive=True.
Dateinamen sind zwar CaseSensitive=False, aber wenn du außerhalb AnsiUpperCase/FileNameUpperCase machst, dann muß das die Liste nicht mehr bei jedem Eintrag machen.
Beim Dictionary gibt es auch welche, die CaseInsensitiv den Hash berechnen und das dann ebenfalls nicht mehr bei jedem Eintrag machen müssen, während der Suche.

[a.def]

Zitat:

Man fängt in der Mitte an und schaut, ob der Suchwert größer oder kleiner ist.

Das erinnert mich an ein kleines Spiel, welches ich zu Schulzeiten in Java geschrieben habe. Dabei ging es um das Erraten einer Zahl.

Nun habe ich es verstanden.

[himitsu]

Darum auch Binär (Zwei), weil man dort immer alles halbiert.

Die maximal nötigen Vergleiche, bis man einen Eintrag gefunden hat, sind auch "zufällig" immer Zweiterpotenzen.

...
65 bis 128 = maximal 7 Vergleiche
129 bis 256 Werte = maximal 8 Vergleiche
257 bis 512 Werte = maximal 9 Vergleiche
513 bis 1024 Werte = maximal 10 Vergleiche
...

[mjustin]

Wäre eine Lösung mit TDictionary (Generics.Collections) nicht wesentlich schneller, wenn die Anzahl wie angegeben in die Hunderttausende geht?

[himitsu]

Wurde schon erwähnt.

TDictionary ist eine sortierte Hash-Liste mit binärer Suche.

[p80286]

Zitat von nahpets:

In 'ner sortierten Liste wird allerdings mit Find gesucht.

Gleicher Aufruf, unterschiedliches Verhalten, das liebe ich.

Gruß
K-H

[a.def]

Was haltet ihr denn davon. Ist das eine Lösung?
Speeding Up Delphi's TStringList.IndexOf

Ich nutze nun

Delphi-Quellcode:

function IndexOfListObjects(const sTmp: string; List: TStringListEx): Integer;
begin
 // for Result := 0 to List.Count - 1 do
 // if sTmp = PFileListEntry(List.Objects[Result])^.sFileName then

 if not List.Find(sTmp, Result) then
  Result := -1;
end;

[himitsu]

Zitat:

Delphi-Quellcode:

function TStringList.IndexOf(const S: string): Integer;
begin
  if not Sorted then Result := inherited IndexOf(S) else
    if not Find(S, Result) then Result := -1;
end;

Wenn deine Liste also Sortiert ist, ergibt es das.

Delphi-Quellcode:

function TStringList.IndexOf(const S: string): Integer;
begin
  if not Find(S, Result) then 
    Result := -1;
end;

[a.def]

Einziger Unterschied den ich gerade erkennen konnte ist, dass die offizielle Fassung von Find () CompareStrings aufruft, die inoffizielle CompareStr().
Sonst ist alles gleich. Hätte ich mal vorher gucken sollen.

[haentschman]

Moin...

Was ich nicht verstehe, das du dich gegen das angesprochene TDictionary, jedenfalls habe ich es nicht gesehen, wehrst... Das ist genau das für den Einsatzzweck gut ist... als das rumgeeiere mit der Stringlist...