String in TStringList finden verschnellern?

[a.def]

Bei einem ganz einfachen Test war bei mir die normale StringList schneller

Delphi-Quellcode:

procedure TForm1.Button2Click(Sender: TObject);
var
 sl: THashedStringList;
 i, X: Integer;
 Watch: TStopwatch;
begin
 sl := THashedStringList.Create;

 sl.Sorted := True;
 for i := 0 to 49999 do
  sl.Add(TStringUtils.RandomString(60));

 sl.Add('ABCABCABC');

 for i := 0 to 49999 do
  sl.Add(TStringUtils.RandomString(60));

 Watch := TStopwatch.Create;
 Watch.Start;

 for i := 0 to sl.Count - 1 do
  begin
   sl.Find('ABCABCABC', X); // Absichtlich kein Break, damit alles verglichen wird
  end;

 Watch.Stop;
 ShowMessage(IntToStr(Watch.ElapsedMilliseconds) + 'ms');
 sl.Free;
end;

// StringList: ~180ms
// HashedList: ~200ms

[himitsu]

Das liegt daran, dass du ausgerechnet die grausamste und sinnloseste Implementation einer Hashlist erwischt hast.

Delphi-Quellcode:

//Unit IniFiles

function THashedStringList.IndexOf(const S: string): Integer;
begin
  UpdateValueHash;
  if not CaseSensitive then
    Result := FValueHash.ValueOf(AnsiUpperCase(S))
  else
    Result := FValueHash.ValueOf(S);
end;

Vor jeder einzelnen Suchanfrage werden ALLE Hashs neu berechnet.
Das muß zwangsläufig langsamer sein.

[a.def]

Zitat von himitsu:

Vor jeder einzelnen Suchanfrage werden ALLE Hashs neu berechnet.

Wenn die HashedStringList mit diesem groben, sagen wir mal, "Fehler" diese geschwindigkeit erzielt (nur 20ms langsamer als die normale in meinem Beispiel), dann muss die ja super schnell sein, wenn dieser "Fehler" nicht ist.

Ich habe das jetzt mal mit IndexOf statt Find gemacht und da ist die HashedStringList schneller als die normale (trotz Neuberechnung der Hashes)

[haentschman]

Zitat:

Ist das in etwas so?

Nöö...

Schau mal hier: http://docwiki.embarcadero.com/Libra...ns.TDictionary

eine der Varianten...TryGetValue: http://docwiki.embarcadero.com/Libra...ry.TryGetValue
... gibt den Value zurück wenn Key gefunden wird.

[nahpets]

Wenn man in IndexOf und Find reinschaut, sieht man, dass da noch ziemlich vieles gemacht wird, um zum Vergleichsergebnis zu kommen.

Hier wird aber doch "nur" ein einfacher Vergleich auf Übereinstimmung von Zeichenfolgen in 'ner sortierten Stringliste benötigt.

Wie wäre es denn, hier einfach mal 'ne eigene Suchroutine zu schreiben, der die Stringliste übergeben wird und die als Rückgabewert den Index des gesuchten Eintrages der Stringliste liefert.

Ungetestet und nur hingedaddelt, daher ohne jegliche Garantie für irgendwas, sondern nur als Idee für's eigene Ausprobieren:

Delphi-Quellcode:

function BinSearch(Suche : String; Start : Integer; Ende : Integer; sl : TStringList) : Integer;
var
        Mitte : Integer;
begin
  Mitte := Start + ((Ende - Start) div 2);
  if Suche <= sl[Mitte] then Result := BinSearch(Suche, Start, Mitte, sl)
  else Result := BinSearch(Suche, Mitte, Ende, sl);
end;

Hier fehlt zum Beispiel noch die Prüfung, ob der Suchbegriff überhaupt in der Stringliste vorkommt, also ist

sl[BinSearch('ASDF',0,sl.Count - 1,sl) = 'ASDF';

Könnte daraus eventuell dann sowas werden?

Delphi-Quellcode:

function IndexOfListObjects(const sTmp: string; List: TStringList): Integer;
begin
 Result := BinSearch(sTmp,0,List.Count - 1,List);
 if List[Result] <> sTmp then Result := -1;
end;

[Uwe Raabe]

Zitat von nahpets:

Wenn man in IndexOf und Find reinschaut, sieht man, dass da noch ziemlich vieles gemacht wird, um zum Vergleichsergebnis zu kommen.

Insbesondere sieht man, daß Find eine binäre Suche durchführt und IndexOf direkt Find aufruft, wenn Sorted gesetzt ist.

Daraus folgt a) daß Find nur dann funktionieren kann, wenn Sorted gesetzt wurde, und b) IndexOf immer funktioniert c) IndexOf im Falle von Sorted wegen der binären Suche in Find schon recht schnell sein sollte.

Bleiben noch die Optimierungsmöglichkeiten in CompareStrings , das sowohl von Find als auch von IndexOf im Falle von Sorted = false aufgerufen wird. Da CompareStrings virtuell ist müssen wir hier die Implementierung in TStringList heranziehen. Darin wird je nach Kombination der Properties UseLocale und CaseSensitive CompareStr oder CompareText bzw. der Ansi-Pendants aufgerufen. Letztere bemühen jeweils eine Funktion aus der Windows-API und sind somit potentiell langsamer als ihre nativen Vettern. Diese beiden (CompareStr und CompareText) sind aus dem Fastcode-Projekt übernommen worden und somit potentiell auch nicht die langsamsten. Da die Text-Variante noch die Groß/Klein-Schreibung berücksichtigt (in dem sie sie ignoriert), ist diese potentiell noch etwas langsamer als CompareStr, daß einen direkten Vergleich durchführt.

Folglich sollte das beste Ergebnis erzielt werden, wenn die Stringlist mit folgenden Einstellungen betrieben wird:

Delphi-Quellcode:

Sorted := true;
CaseSensitive := true;
UseLocale := false;

Trotzdem kann das stumpfe Iterieren durch alle Strings mit einem direkten Vergleich durchaus deutlich schneller sein, als das Find. Im Gegensatz zu CompareString, daß einen Ordnungsvergleich (kleiner, gleich, größer) durchführt, wird bei einem direkten Vergleich eben nur auf Gleichheit getestet. Da Strings aber referenzgezählte Objekte sind, kann bei diesem Vergleich als erstes geprüft werden, ob es sich um dasselbe Objekt handelt und nicht nur um einen String mit demselben Inhalt.

Selbst bei mehreren Millionen Einträgen kann der Brute-Force Ansatz immer noch schneller sein. Man sollte das also mit realen Daten testen, bevor man blind eine bestimmte Methode einsetzt.

[a.def]

Das gibt einem zu denken. Danke für die ausführliche Erklärung!

Eine Frage habe ich noch. Wenn man sorted auf True setzt, ist das hinzufügen zur Liste deutlich langsamer und Einträge die schon vorhanden sind werden ignoriert.
Spielt es eine Rolle, ob ich Sorted vor oder nach dem Hinzufügen all meiner Einträge auf True setze?

[Fritzew]

Also:

Delphi-Quellcode:

sl := Tstringlist.create;
sl.Duplicates = dupAccept; // Damit Duplicate erlaubt sind
// Alles einfügen

// dann
sl.sorted := true;  // Sortiert die Liste

so sollte es gehen

[nahpets]

Wenn Sorted = true muss beim Einfügen geschaut werden, wo der neue Eintrag hin muss, damit er dort eingefügt werden kann.

Statt Sorted = true könntest Du mal probieren, ob der Aufruf von Sort vor der Stelle, ab der Du suchen willst, etwas bringt. Du muss dann aber an der Stelle mit etwas Wartezeit rechnen.

Man kann für den Fall dann auch eine eigene Sortierroutine zuweisen, die eventuell auch das Laufzeitverhalten ändern könnte.