String in TStringList finden verschnellern?

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