Gibt es einen schnelleren Stringvergleich als if S1 = S2

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

[Bjoerk]

Nein ich denke eher nur dann. Beispiel (hier schlägt der Vergleich fehl):

Delphi-Quellcode:

unit Unit2;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  PString = ^TString;
  TString = string[80];

  TTest = class(TList)
  public
    procedure AddItem(const Value: TString);
    procedure DelItem(Index: integer);
    function CompareItems(const Index1, Index2: integer): boolean;
    destructor Destroy; override;
  end;

  TForm2 = class(TForm)
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  end;

var
  Form2: TForm2;

implementation

{$R *.dfm}

procedure TTest.AddItem(const Value: TString);
var
  P: PString;
begin
  New(P);
  P^:= Value;
  Add(P);
end;

procedure TTest.DelItem(Index: integer);
var
  P: PString;
begin
  P:= Items[Index];
  Dispose(P);
  Delete(Index);
end;

destructor TTest.Destroy;
begin
  while Count > 0 do
    DelItem(Count - 1);
  inherited Destroy;
end;

function TTest.CompareItems(const Index1, Index2: integer): boolean;
begin
  Result:= CompareMem(Items[Index1], Items[Index2], SizeOf(TString));
end;

procedure TForm2.Button1Click(Sender: TObject);
var
  Test: TTest;
begin
  Test:= TTest.Create;
  try
    Test.AddItem('TestItem');
    Test.AddItem('TestItem');
    if Test.CompareItems(0, 1) then ShowMessage('CompareItems');
  finally
    Test.Free;
  end;
end;

end.

[himitsu]

Gut, das mit den "identischen" String-Instanzen hab ich mal mit in den Code aufgenommen.

CompareMem wurde auch schon optiiert (hoffe ich), z.B. im FastMM wurden derart optimierte Vergleichs-/Kopiercodes integriert, welche bei kleinen Speicherblöcken optimierte Codes verwenden, die keine Schleifen und dafür teilweise MMX-Register verwenden.

Zitat von Bjoerk:

Nein ich denke eher nur dann. Beispiel (hier schlägt der Vergleich fehl):

Du mußt natürluch auch wissen was du vergleichst.

Meine Funktion war die Vorgehensweise bei LongStrings (AnsiString, wideString, UnicodeString).

Doch ein ShortString verfügt über ein anderes Speichermanagent.
Die Delphiimplementation dieses Vergleichs beachtet deswegen die Größenangabe ersten Byte (Index 0) und vergleicht NUR die reinen Stringdaten, denn hinter dem String sind die Daten zufällig/unbestimmt.

'abc' = 'abc' im Delphicode und mit einem String[6] sieht eventuell so aus #3'abc'#x#x#x = #3'abc'#x#y#z (Llngenbyte + Text + KEINE #0 + Sonstewas).