String in TStringList finden verschnellern?

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

[EmWieMichael]

Zitat von himitsu:

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

Täusche ich mich, oder werden bei dieser Rechnung die Vergleiche mit '=' vergessen? Ich muss doch nach jeder Halbierung zwei Vergleiche anstellen: '=' und ('<' oder '>').
Oder ist es mit 8 Uhr noch zu früh für mich...?

[himitsu]

Zitat von EmWieMichael:

Täusche ich mich, oder werden bei dieser Rechnung die Vergleiche mit '=' vergessen? Ich muss doch nach jeder Halbierung zwei Vergleiche anstellen: '=' und ('<' oder '>').

Rein "logisch" nur eine mathematische Rechnung.
V = A - B (gleich 0, kleiner 0, größer 0)
CompareValue
Dann weiß man sofort ob größer, kleiner oder gleich.

Aber aus diesem Grund sind Hash-Listen schneller, da dort je Wert nur ein "Vergleich" nötig ist, während bei Strings ja jedes einzelne Char verglichen werden muß.

Die genaue Anzahl der physischen Vergleiche, im Bytecode (Assembler) oder gar in der CPU, will man besser nicht wissen.
Für einen Vergleich zweier Suchalgorithmen reicht es, wenn man die ungefähre Anzahl der logischen Vergleichsoperationen kennt.

[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

[p80286]

Zitat von himitsu:

Aber aus diesem Grund sind Hash-Listen schneller, da dort je Wert nur ein "Vergleich" nötig ist, während bei Strings ja jedes einzelne Char verglichen werden muß.

Naja nicht unbedingt, "damals" haben wir die Strings in 16-Bit Werte zerhackt, und diese dann verglichen, da konnte man gegenüber den 8-Bit Vergleichen knappe 50% herausholen. Mit 32-Bit oder gar 64-Bit kann man da gut Gas geben. Und die hash-Berechnung fällt nicht an.

Gruß
K-H