Gibt es einen schnelleren Stringvergleich als if S1 = S2

[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));

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

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

Ups, dann hatte ich falsch geguckt.

Na gut, aber dann wäre es wohl besser, wenn man die ganze Vergleichsroutine ersetzt, denn so wird es ja im schlimmsten Fall nur langsamer, da zum eigentlichen Vergleich (s1 = s2) noch weitere Vergleiche dazukommen.
Aber wie gesagt, ohne zu wissen was und wo verglichen werden soll, kann man eigentlich nicht viel machen, außer die Vergleichroutine selber zu optimieren. (praktisch wie beim FastCodeProject)
Und ob es nicht bessere Wege gäbe (Hash und Co.), kann man auch nicht sagen.

[Medium]

Hashes müssen auch erst gebildet werden, die Zeit dafür wäre also eigentlich den Vergleichen zuzurechnen. Da kommt es auf den konkreten Fall an, ob es in dem Programm die Hashes vorab zu bilden einen echten Vorteil erzeugt (sprich die Strings weit vorher erzeugt sind, und es dort nicht so auf Speed ankommt). Und man sollte genügend lange Hashes haben, sonst kommt man bei zu großer String-Anzahl ggf. zu oft in den Worst-Case, dass man zu gleichen Hashes dann doch zur Sicherheit den ganzen String testen muss. Ungleichheit sollte damit aber - wenn man die Vorab-Kosten raus nehmen darf - mit dem Vergleich schon des ersten Bytes vom Hash in der überwiegenden Zahl der Fälle feststellbar sein. (Es sei denn, man konstruiert gerade solche Strings, die möglichst ähnliche Hashes ergeben. Aber wer macht das in der Praxis schon )
Hier ist wirklich der Knackpunkt die Erzeugung der Hashes, bzw. ob man sich die Geschwindigkeit ohne merkliche Einbußen im Vorab erkaufen kann.

[Popov]

Wie du schon sagst, es wird mehr. Trotzdem, nur die Länge und dann Vergleich scheint schneller zu sein als nur Vergleich.

Was ich aber hier festgestellt habe ist, dass zumindest bei kurzen Strings das so schnell geht, dass man sich jegliche weitere Optimierung sparen kann. Letztendlich stellt sich aber die Frage wie lang die im konkretem Fall sind.

Auf der anderen Seite kann ich mich noch aus meiner C64 Zeit erinnern, da hatte ich den ganzen Basic als Assemblercode im Kopf, dass es nichts simpleres gibt als zwei Zeichenketten zu vergleichen. Das ist kein komplizierter Code, da kann man nichts falsch machen, das ist schnell. Alles andere ist mehr Aufwand. Und wenn Windows da nichts anders macht, dann ist es auch hier simpel und schnell.

[himitsu]

Ja, das müssen sie, aber darum muß man ja auch wissen was wie wo verglichen werden soll,

denn wenn man z.B. etwas in einer Liste suchen will, dann kann man die meisten Hashs schon vorberechnen (von allem in der Liste) und die Hashliste sogar noch sortieren.
Nun muß man nur noch den einen String hashen und kann dann ganz schnell in der Liste suchen, oder eben BTrees und Co., wo der String dann nicht erstmal komplett gehasht werden muß, sondern man nur stückchenweise in den Listen sucht, vorzeitig abbrechen kann.

Auch der Stringvergleich vom Delphi vergleicht zuerst die Länge.
Schematisch gesehn macht s1 = s2 auch nichts Anderes:

Delphi-Quellcode:

if Pointer(s1) = Pointer(s2) then Exit(True);  // ich weiß nicht, ob das in der Delphi-Implementation mit drin ist, aber ist zur Erkennung auf "identische" String-Instanzen
if Pointer(s1) = nil then l1 := 0 else l1 := (PInteger(s1) - SizeOf(Integer))^;
if Pointer(s2) = nil then l2 := 0 else l2 := (PInteger(s2) - SizeOf(Integer))^;
Result := (l1 = l2) and ((l1 = 0) or CompareMem(Pointer(s1), Pointer(s2), l1 * SizeOf(s1[1])));

// und um noch ein paar Sprünge einzusparen + s1='' wird eh in einen Nil-Vergleich optimiert:
if Pointer(s1) = Pointer(s2) then Exit(True);
l1 := 0;  if s1 <> '' then l1 := (PInteger(s1) - SizeOf(Integer))^;  // oder einfach nur l1 := Length(s1); ... wird Length eigentlich inline compiliert?
l2 := 0;  if s2 <> '' then l2 := (PInteger(s2) - SizeOf(Integer))^;
//Result := (l1 = l2) and ((l1 = 0) or CompareMem(Pointer(s1), Pointer(s2), l1 * SizeOf(s1[1]))); 
Result := (l1 = l2) and ((l1 = 0) or ((PLongWord(s1)^ = PLongWord(s2)^) and CompareMem(Pointer(s1), Pointer(s2), l1 * 2))); // WideChar + vergleicht extra nochmal die ersten 1-2 Chars, ohne zu CompareMem zu springen
Result := (l1 = l2) and ((l1 = 0) or ((PWord(s1)^ = PWord(s2)^) and CompareMem(Pointer(s1), Pointer(s2), l1 * SizeOf(s1[1]))));  // AnsiChar oder WideChar

[Furtbichler]

Da der Vergleich von zwei Bytes so mit die schnellste Operation ist, wird der Knackpunkt die Schleife über alle Zeichen sein.

Bei kurzen Strings kann es eigentlich nichts schnelleres geben, aber bei sehr langen Strings kann man eben die Schleife optimieren.

Wenn ich sehr lange Strings zum testen nehme, die zudem noch unterschiedlich lang sind, dann kann ich mit dem Trick auf testen der Länge und 1.Zeichen 8% einsparen, obwohl ich in der Testroutine anstatt 10.000.000 Vergleiche nur 100 durchführen muss. Die Strings haben eine Länge von 1000+Random(1000) Zeichen..

Wenn ich also meinen Algorithmus, der auf Stringvergleich basiert, optimieren will, muss ich die Anzahl der Stringvergleiche verkleinern. Wenn es um das Suchen in Listen geht, würde ich eine Hashmap nehmen, da hat man i.A. nur einen Stringvergleich.

[Bjoerk]

CompareMem und Strings? Ich wurde mal darüber aufgeklärt, daß Strings den selben Pointer haben können, aber nicht müssen?

[Furtbichler]

Ja und? Funktioniert CompareMem nicht, wenn die Zeiger identisch sind?