Gibt es einen schnelleren Stringvergleich als if S1 = S2

[DeddyH]

Und bei AnsiCompareStr? AFAIK wird dort die API-Funktion CompareString mit den Spracheinstellungen des aktuellen Users aufgerufen, welche mit PChars arbeitet. Das dürfte schneller sein, kommt zumindest auf einen Versuch an.

[BUG]

Zitat von DeddyH:

Das dürfte schneller sein,

Warum

[Bjoerk]

Zitat von DeddyH:

Und bei AnsiCompareStr? AFAIK wird dort die API-Funktion CompareString mit den Spracheinstellungen des aktuellen Users aufgerufen, welche mit PChars arbeitet. Das dürfte schneller sein, kommt zumindest auf einen Versuch an.

Leider nein.

Das ist (bis jetzt) am schnellsten:

Delphi-Quellcode:

function StrCompare(const S1, S2: string): boolean;
begin
  if Length(S1) <> Length(S2) then
    Result:= false
  else
    Result:= S1 = S2;
end;

[sx2008]

Es ist ein Unterschied ob man nur wissen muss ob 2 Strings gleich sind oder wie z.B. bei AnsiCompareStr ob ein String kleiner, grösser oder gleich ist.
Daher ist if AnsiCompareStr(s1,s2)=0 then langsamer als if s1 = s2 then .

Hier sollte man sprachlich besonders präzise sein; will man vergleichen oder auf Gleichheit prüfen?

Delphi-Quellcode:

function StrEquals(const s1,s2:string):Boolean; // prüft ob zwei strings gleich sind
function StrCompare(const s1,s2:string):Integer; // 0=beide gleich, 1=s1 ist grösser, -1=s1 ist kleiner

Wenn man sich anschaut, wie ein AnsiString im Speicher liegt
http://www.codexterity.com/images/ansistring_layout.gif
dann muss man Folgendes tun:
1.) sind die beiden Zeiger s1 und s2 gleich? Falls ja: return(true)
2.) ist einer der beiden Zeiger = nil Falls ja: return(false)
3.) Längen der strings holen
4.) sind die Längen ungleich? Falls ja: return(false)
5.) Zeichen für Zeichen auf Gleichheit prüfen. Bei Abweichung return(false)
6.) return(true)

Wenn man die Punkte 1. bis 6. in Assembler ausprogrammiert erhält man die max. mögliche Geschwindigkeit.
Besonders bei 5. kann man z.B. durch schnellere CPU-Befehle SIMD, SSE,... noch einiges an Zeit rausholen.

[Popov]

Weil es mich auch interessiert hat, habe ich Furtbichlers Vorschlag getestet. Letztendlich dauert der Vergleich dann sogar länger, aber nur paar Millisekunden.

Hier das Beispiel zum überprüfen:

Delphi-Quellcode:

uses
  DateUtils;

procedure TForm1.Button1Click(Sender: TObject);
var
  i, k, m, c, x: Integer;
  t1, t2: TTime;
  s, s1, s2: String;
begin
  Screen.Cursor := crHourGlass;

  c := 0;
  Caption := '';

  t1 := Now;
  x := 10000000; // 10 Mio. Durchläufe
  for i := 1 to x do
  begin
    k := Random(MaxInt);
    m := Random(MaxInt);

    s1 := IntToStr(k); //die Hälfte der Strings sind gleich
    if Odd(i) then s2 := IntToStr(k) else s2 := IntToStr(m);

    //Direkt - Beispiel 1
    //if s1 = s2 then Inc(c);

    //Indirekt - Beispiel 2
    if Length(s1) = Length(s2) then
      if s1[1] = s2[1] then
        if s1[Length(s1)] = s2[Length(s2)] then
          if s1 = s2 then Inc(c);
  end;
  t2 := Now;

  Caption := Format('Gleich: %d von %d; Millisek.: %d', [c, x, MilliSecondsBetween(t1, t2)]);

  Screen.Cursor := crDefault;
end;

[Aphton]

Ne Frage nebenbei (jz nicht nur dies hier betreffend, sondern auch etwas allgemeiner):

Delphi-Quellcode:

    if Length(s1) = Length(s2) then
      if s1[1] = s2[1] then
        if s1[Length(s1)] = s2[Length(s2)] then
          if s1 = s2 then Inc(c);

Ist folgende Variante nicht schneller? Oder optimiert das Delphi allgemein genauso?

Delphi-Quellcode:

    len := Length(s1);
    if len = Length(s2) then
      if s1[1] = s2[1] then
        if s1[len] = s2[len] then  // hier!
          if s1 = s2 then Inc(c);

Sry hab kB Delphi zu starten und zu disassemblieren. Vlt weiß es ja einer auf Anhieb.

[Popov]

Nur etwas Statistik. Man sollte bedenken, dass auch der sonstige Code um die eigentlich Abfrage Zeit verbraucht. So werden 50 Mio. FOR Schleifen, abzüglich der IF Zeile oder Zeilen (je nach Beispiel) in meinem Rechner in 4820 Millisekunden abgewickelt.

Also

50. Mio Schleifen ohne IF Zeilen durchschnittlich in 4820 Millisekunden

50. Mio Schleifen mit einer IF Zeile (Bsp. 1) durchschnittlich in 5035 Millisekunden

50. Mio Schleifen mit vier IF Zeilen (Bsp. 2) durchschnittlich in 5060 Millisekunden

50. Mio Schleifen mit zwei IF Zeilen (Bsp. 3) durchschnittlich in 5020 Millisekunden

Delphi-Quellcode:

    //Bsp. 3
    if Length(s1) = Length(s2) then
      if s1 = s2 then Inc(c);

50. Mio Schleifen mit vier IF Zeilen (Aphtons Beispiel) durchschnittlich in 5035 Millisekunden


Wie man sieht werden etwas 50. Mio Vergleiche in ca. 200 Millisek. durchgeführt. Das macht 4 Nanosekunden pro Vergleich. Ich würde sagen, das die Funktion optimiert ist. Die Unterschiede zwischen den Beispielen sind eher marginal.

[sx2008]

Die Schleife aus Beitrag #8 ist suboptimal zum Testen weil zu viele störende Anweisungen darin enthalten sind.
Man muss schon alle Varianten hintereinander ausführen.
Und der Code sollte "inline" sein - eine Unterfunktion verbietet sich hier, denn sonst misst man hauptsächlich die Zeit für den Funktionsaufruf.

Delphi-Quellcode:

s1 := '';
s2 := '';
for i := x downto 0 do  // leere Strings
begin
{$IfDef DIRECT}
   if s1 = s2 then Inc(c);
{$Else}
    //Indirekt - Beispiel 2
    if Length(s1) = Length(s2) then
      if s1[1] = s2[1] then
        if s1[Length(s1)] = s2[Length(s2)] then
          if s1 = s2 then Inc(c);
{$EndIf}
end;
s1 := 'abcde';
s2 := '123456'
for i := x downto 0 do  // unterschiedliche Länge
  // gleicher Inhalt wie oben
end;
s1 := 'abcdef';
s2 := '123456'
for i := x downto 0 do  // gleiche Länge, komplett unterschl. Inhalt
  // gleicher Inhalt wie oben
end;
s1 := 'abcdef';
s2 := 'abcdef'
for i := x downto 0 do  // gleiche Strings
  // gleicher Inhalt wie oben
end;
s1 := 'abcdef------------------------------1';
s2 := 'abcdef------------------------------2'
for i := x downto 0 do   // letztes Zeichen verschieden
  // gleicher Inhalt wie oben
end;
Assert(c = 2*(x+1));

[Popov]

Zitat von sx2008:

Die Schleife aus Beitrag #8 ist suboptimal zum Testen weil zu viele störende Anweisungen darin enthalten sind.

Finde ich nicht. Eigentlich war die Schleife zuerst nur zum Vergleich von zwei Vergleichen gadacht, d. h. welche von beiden ist schneller. Da stören die zusätzlichen Anweisungen nicht, da sie in beiden Beispielen gleich vorkommen. Wenn ich zwei Leute mit je einem Kasten Bier in die 10. Etage über Treppe schicke, mag der Kasten hinderlich sein, da aber beide einen Kasten schleppen ist es egal. Er behindert beide ja gleich.

Erst bei der späteren Zeitmessung für die Statistik war die Bagage hinderlich.

@ himitsu

Zitat:

aber nicht die kompletten Strings.

Doch, siehe noch mal nach. In beiden Beispielen werden zum Schluß die Strings verglichen.

[himitsu]

Wobei es eher drauf ankommt was wie verglichen werden soll,

denn in den ganzen Beispielen werden nur die Stringlängen und eventuell noch Bruchteile der Strings verglichen, aber nicht die kompletten Strings.

So ist z.B. 'xxx' = 'yyy' (nur Länge verglichen) oder 'xxxxxxx' = 'xyyyyyx' (Länge plus erstes/letzes Zeichen).


Eventuell sind Hashs/Hashmaps eher eine Lösung oder binäre Bäume und Ähnliches.


Im FastStringsProject werden z.B. nicht mehr alle Zeichen einzeln verglichen, sondern die Vergleiche mehrere Chars zusammenfassen, über MMX, SSE und Dergleichen.


Außerdem sind Tests mit fiktiven/standardisierten Werten vollkommen nutzlos, da unterschiedliche Vergleichsverfahen nicht allgemeingültig direkt verglichen werden können.
Letztendlich kann nur ein Test am realen Projekt herangezogen werden, um das durchschnittlich "optimalste" Verfahren für genau dieses Problem zu finden.