Performanteste Möglichkeit zur Prüfung ob zwei StringListen den gleichen Inhalt haben

[nahpets]

Streng genommen sind sie also nicht wirklich gleich, sondern die Inhalte werden, sofern sie nur bestimmte Abweichungen enthalten, als gleich betrachtet?

Mir fiele da nur sowas in der Art ein:

Delphi-Quellcode:

function TesteListen(sl1, sl2 : TStringList) : Boolean;
var
         i : Integer;
begin
  Result := sl1.Count = sl2.Count;
  if not Result then exit;
  i := 0;
  repeat
    Result := TestString(sl1[i]) = TestString(sl2[i]);
    inc(i);
  until not Result or (i >= sl1.Count);
end;

TestString sei hierbei eine Funktion, die die Delimiter u. ä. Zeichen eleminiert oder vereinheitlicht, entsprechend den Anforderungen. Könnte also z. B. sowas sein:

Delphi-Quellcode:

function TestString(s : String) : String;
begin
  // " und ; ersatzlos "streichen".
  Result := AnsiReplaceText(AnsiReplaceText(s,'"',''),';',',');
  // Oder: Delimiter ";" wird zu ','
  Result := AnsiReplaceText(s,'";"','','');
end;

Eventuell könnte man diese Änderungen aber auch bereits auf sl1.Text bzw. sl2.Text machen und dann nur noch TesteListen aufrufen, ohne dass dort noch Funktionen aufgerufen werden müssen.

Kannst Du im StringList.Text bereits alle Delimiter ... vereinheitlichen, könnte nachfolgen ein MD5-Checksummenvergleich eventuell schneller werden.

Oder wenn Du die Delimiter vereinheitlichen kannst, dürfte anschließend ein if Stringliste1.Text = Stringliste2.Text then ... für den Vergleich ausreichen.

[CodeX]

Zitat von nahpets:

Streng genommen sind sie also nicht wirklich gleich, sondern die Inhalte werden, sofern sie nur bestimmte Abweichungen enthalten, als gleich betrachtet?

Hm, wahrscheinlich habe ich mich nicht eindeutig ausgedrückt...
Ich wollte nur darauf hinaus, dass es mir ausschließlich um die Strings in der Liste geht und nicht um sonstige Eigenschaften. Wenn ich also eine StringListe kopiere und in der Kopie die Eigenschaft Delimiter oder QuoteChar ändere, dann hat sich am Inhalt ja nichts geändert und die beiden Listen wären immer noch als gleich zu betrachten. Ich wollte damit nur anmerken, dass eine Lösung mit Speichervergleich wie CompareMem o.ä. vielleicht nicht die korrekteste Lösung wäre.

Also dann besser durch alle Elemente durchgehen und diese einzeln vergleichen als alles per Strings.Text zusammenzusetzen und nur einen Vergleich durchzuführen?

[nahpets]

Also dann würd' ich es so versuchen:

Delphi-Quellcode:

function TesteListen(sl1, sl2 : TStringList) : Boolean;
var
         i : Integer;
begin
  Result := sl1.Count = sl2.Count;
  if not Result then exit;
  i := 0;
  repeat
    Result := sl1[i] = sl2[i];
    inc(i);
  until not Result or (i >= sl1.Count);
end;

[freimatz]

Ich bin auch der Meinung dass ein durchgehen durch die Liste wesentlich schneller ist als Text oder ähnliches zu verwenden. Statt eine repeat würde ich eher einer for Schleife nehmen. Das dann zum Beispiel so (ungetetet)

Delphi-Quellcode:

function TesteListen(sl1, sl2 : TStringList) : Boolean;
var
  i : Integer;
begin
  Result := False;
  if sl1.Count <> sl2.Count 
  then Exit;
  for i := sl1.Count - 1 do 
  begin
    if sl1[i] <> sl2[i] 
    then Exit
  end;
  Result := True;
end;

Falls so ein Vergleich öfters vorkommt und sich die Daten nicht ständig ändern könnte man auch noch über Hashes nachdenken.

[CodeX]

Oder eine While-Schleife

Delphi-Quellcode:

var
  i: Integer;
begin
  Result := sl1.Count = sl2.Count;
  i := 0;
  while Result and (i < sl1.Count) do
  begin
    Result := sl1[i] = sl2[i];
    Inc(i);
  end;
end;

Solange niemand einen performanteren Gegenvorschlag zu einer Schleife hat, mache ich das gerne so.

[freimatz]

Ja genau. Die Möglichkeit ist die schnellste.

Zitat von CodeX:

...
Solange niemand einen performanteren Gegenvorschlag zu einer Schleife hat, ...

Dazu müsstest du erst mehr Hintergrundinformationen liefern.

[jfheins]

Du solltest vielleicht mal ausrechnen, wie schnell du aktuell bist.
Also du musst ja beide Listen komplett aud dem RAM in die CPU schaufeln, das heißt irgendwann kommst du da an das Limit von der Geschwindigkeit des RAM.
Wenn die Lösung aus #9 da in die Nähe kommt, ist da eigentlich nicht viel zu verbessern.

Falls sie es nicht tut, und es noch schneller gehe soll, müsstest du wohl auf assembler gehen und mit SSE-Anweisungen mehrere Bytes auf einmal vergleichen.

Alternativ könntest du probieren, ein paar Durchläufe der Schleife zusammenzufassen. In etwa so:

Delphi-Quellcode:

var
  i: Integer;
  maxi: Integer;
begin
  Result := sl1.Count = sl2.Count;
  i := 0;
  maxi = (sl1.Count div 4) * 4;

  while Result and (i < maxi) do
  begin
    Result := Result or (sl1[i+0] = sl2[i+0]);
    Result := Result or (sl1[i+1] = sl2[i+1]);
    Result := Result or (sl1[i+2] = sl2[i+2]);
    Result := Result or (sl1[i+3] = sl2[i+3]);
    Inc(i, 4);
  end;
  
  while Result and (i < sl1.Count) do
  begin
    Result := sl1[i] = sl2[i];
    Inc(i);
  end;
end;

Keine Ahnung, ob der Compiler soetwas inzwischen automatisch macht, aber das könnte noch ein paar Prozent Unterschied bringen.