String in TStringList finden verschnellern?

[a.def]

Zur Beantwortung deiner Fragen:

- die Liste war nicht sortiert. Ich habe nun nach dem Create der Liste ein Sorted := True; angehangen.

- das Benutzen von IndexOf(sTmp) war deutlich langsamer als das Suchen in den Objekten.

Zitat:

Wenn als Beispiel in PFileListEntry(List.Objects[0])^.sFileName C:\1\2\3\4.txt stehen würde, was stände dann in List[0] ?

In List[0] wäre dann im besten Fall genau derselbe String.

[p80286]

Zitat von a.def:

Zur Beantwortung deiner Fragen:

- die Liste war nicht sortiert. Ich habe nun nach dem Create der Liste ein Sorted := True; angehangen.

in unsortierten Listen (Arrays etc.) suchen, ist grundsätzlich nicht empfehlenswert.

Zitat von a.def:

- das Benutzen von IndexOf(sTmp) war deutlich langsamer als das Suchen in den Objekten.

Das sollte aber der pure Zufall gewesen sein.

Statt Indexof könntest Du auch Find nutzen, oder aber wie Stefan schon vorgeschlagen hat, bau Dir eine Binäre Suche, die könntest Du dann für Deine speziellen Zwecke anpassen.

Gruß
K-H

[himitsu]

IndexOf und Find sollte doch gleich schnell sein?
Und ja, sortieren hilft (Sorted=True), denn dann wird eine andere Suchmethode verwendet.
> TArray.BinarySearch

Alternativ eine HashList.
TDictionary?

[nahpets]

Ok, mit Sorted := True ist der Inhalt also aufsteigend sortiert und damit kannst Du dann binär suchen.

Grober Überblick: https://de.wikipedia.org/wiki/Bin%C3%A4re_Suche

Hier im Forum mal suchen: http://www.delphipraxis.net/dp_searc...ch_matchmode=0

@p80286
IndexOf ist nicht wirklich schnell, da es in unsortierten Listen letztlich auch in 'ner While-Schleife alle Einträge abfragt, bis was gefunden wurde.
Entspricht daher vom Zeitaufwand vermutlich in etwa der For-Schleife.

In 'ner sortierten Liste wird allerdings mit Find gesucht.

@a.def
Durch das Sorted := True könnte sich damit die Laufzeit für IndexOf verändert haben.

[a.def]

Mich würde mal interessieren, warum eine sortierte Liste schneller durchsucht werden kann als eine unsortierte?
Ob da jetzt 1 Millionen sortierte oder unsortierte Einträge sind... es sind 1 Millionen.

[DeddyH]

Weil man in einer sortierten Liste eben nicht mehr alle Einträge sequentiell durchsuchen muss. Schau Dir doch einfach einmal an, wie eine binäre Suche funktioniert ("Pieksen" in die Mitte, vergleichen und eine Hälfte ignorieren, das so lange, bis der gesuchte Eintrag gefunden wurde oder es keine "Mitte" mehr gibt -> kein Treffer).

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

[stahli]

Man fängt in der Mitte an und schaut, ob der Suchwert größer oder kleiner ist.
Je geht man zur Mitte der kleineren oder größeren Hälfte und dann weiter bis zum Treffer.
Dann erhält man nach einigen Zyklen das Ergebnis oder die Position, an der der neue Eintrag eingefügt werden müsste.

Das ist die binäre 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
...