Gibt es einen schnelleren Stringvergleich als if S1 = S2

[Bjoerk]

Sitz‘ grad mal wieder über einem meiner 88000 Parser. Dabei ist mal wieder bei mir die Frage aufgetaucht, ob es einen schnelleren Stringvergleich als if S1 = S2 gibt? Vermutlich nein, sonst wäre er in Delphi implementiert. Richtig?

[Furtbichler]

Zitat:

Zitat von Bjoerk (Beitrag 1183050)

Richtig?

Mittlerweile vielleicht. Es gibt ja die FastCode Challenge Site, wo sich Delphi z.T. bedient hat.

Der Vergleich zweier Strings kann eventuell durch folgende Heuristik schneller werden.
Vergleiche die Längen, dann das jeweils erste Zeichen und dann das jeweils letzte Zeichen. Nur wenn alle drei Vergleiche TRUE ergeben, vergleiche den Rest des Strings.

Ich denke aber, die Compare-Routinen sind schon optimiert

[Bjoerk]

Genau so macht es Delphi, Zeichen für Zeichen.

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

Zitat von DeddyH (Beitrag 1183072)

Das dürfte schneller sein,

Warum :gruebel:

[Bjoerk]

Zitat:

Zitat von DeddyH (Beitrag 1183072)

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

Delphi-Quellcode:

AnsiCompareStr(s1,s2)=0 then

langsamer als

Delphi-Quellcode:

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.