String in TStringList finden verschnellern?

[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

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

[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

[EmWieMichael]

Zitat von himitsu:

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

Wahrscheinlich steh´ ich wirklich auf´m Schlauch : Ich habe jetzt eine Rechnung aufgestellt und das Ergebnis steht in 'V'; ich weiß, dass 'V' kleiner 0, größer 0 oder gleich 0 ist. Um auf dieses Ergebnis zu reagieren, benötige ich doch immer noch zwei Vergleiche:

Code:

...
if (V = 0) then 
 begin
   Gefunden; 
   Break;
 end; 
if (V < 0) then 
 SuchindexNachUnten;
else
 SuchindexNachOben;
...

[Klaus01]

oder so:

Delphi-Quellcode:

case v of
  low(Integer) .. -1: SuchIndexNachUnten;
  0: Gefunden;
  1 .. high(Integer): SuchIndexNachOben;
end;

Grüße
Klaus