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

[CodeX]

Ich habe viele Threads zu dem Thema gefunden, wie man Unterschiede von StringListen herausfindet. Meine Frage hat aber einen anderen Fokus.

Wie prüfe ich am performantesten, ob zwei StringListen (TStrings) die gleichen Strings in der gleichen Reihenfolge enthalten? Eigenschaften wie Delimiter o.ä. spielen dabei keine Rolle und könnten entsprechend unterschiedlich sein.

Eine Liste kann schon mal bis zu 10.000 Strings enthalten.

Mir fallen mehrere Möglichkeiten ein, wie das ganz einfach geht (z.B. Werte in einer Schleife durchgehen und vergleichen oder DelimitedText vergleichen). Aber wäre die performanteste Methode?

[HolgerX]

Hmm..

Delphi-Quellcode:

  if StringList1.Text <> StringList2.Text then ..// Sie sind unterschiedlich (ungleiche Einträge, Position...)

[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

Delphi-Quellcode:

if Stringliste1.Text = Stringliste2.Text then ...

für den Vergleich ausreichen.

[Der schöne Günther]

Eine TStringList wrapped ein "array of TStringItem" wobei TStringItem ein Record ist.

meineStrings[42] gibt dir das 42+1-te Element aus diesem internen Array. Mit

Delphi-Quellcode:

Count

lässt sich die Anzahl der Elemente abfragen.

Das ist denke ich schneller als z.B. sich den gesamten

Delphi-Quellcode:

Text

zusammenbauen zu lassen


PS: Ich fühle mich unschuldig, ich hatte keinen roten Kasten.

[himitsu]

Der Holger will lieber nicht wissen was TStringList.Text macht. :stupid:
DelimitedText und CommaText machen das Selbe, nur eben mit "Delimiter" statt LineBreak.

TStringList besteht aus vielen Strings, die werden zu einem großen String zusammen gebaut (das ist nicht wirklich "performant")
und das dann zusammen verglichen. (gut, das geht dann schnell, aber die zu vielen Speicheroperationen vorher hebt es bei Weitem nicht auf)

Also Besser ist es da, einfach nacheinander die Strings zu vergleichen und bei einem Unterschied abzubrechen. (wenn die Zeilenanzahl vorher schon nicht stimmt, dann gleich da raus, da es eh nicht gleich sein kann)
[edit] also praktisch das gezeigte TesteListen ... muß man nur noch entscheiden, ob TestString nötig ist, oder ob es nur "anders" verstanden wurde :angle:


Geht es aber um den Vergleich zweier TMemo (TMemoStrings) ... dort ist es intern schon "ein" String, Memo.Lines.Text ist optimiert und gibt direkt Memo.Text zurück, und Memo.Lines[i] muß jedesmal einen Teilstring aus dem Großen rauskopieren.



Muß es "schnell" gehen, dann darf man die Daten nicht verändern/kopieren, sondern muß die Originaldaten direkt vergleichen.

[CodeX]

Zitat:

Zitat von nahpets (Beitrag 1362464)

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

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.

[mjustin]

Delphi-Quellcode:

// Sie sind auch gleich, wenn beide Variablen auf die selbe Adresse zeigen
if StringList1 = StringList2 then ...
// sie sind gleich

[freimatz]

Ja genau. Die Möglichkeit ist die schnellste.

Zitat:

Zitat von CodeX (Beitrag 1362509)

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

Dazu müsstest du erst mehr Hintergrundinformationen liefern.

[MichaelT]

Erst wenn der Count gleich ist, dann den Vergleich machen. Das hilft aber allein unter der Annahme, dass Leerzeilen in beiden Listen gewollt an der selben Stelle auftreten.

Du kannst auch zuerst mal ein Zeichen prüfen und falls die gleich sind den ganzen String und/oder die Länge usw... Wenn du erwartest, dass die Listen gleich sind und der Items.Count ident bringt das wenig.

Zitat:

Zitat von CodeX (Beitrag 1362456)

Ich habe viele Threads zu dem Thema gefunden, wie man Unterschiede von StringListen herausfindet. Meine Frage hat aber einen anderen Fokus.

Wie prüfe ich am performantesten, ob zwei StringListen (TStrings) die gleichen Strings in der gleichen Reihenfolge enthalten? Eigenschaften wie Delimiter o.ä. spielen dabei keine Rolle und könnten entsprechend unterschiedlich sein.

Eine Liste kann schon mal bis zu 10.000 Strings enthalten.

Mir fallen mehrere Möglichkeiten ein, wie das ganz einfach geht (z.B. Werte in einer Schleife durchgehen und vergleichen oder DelimitedText vergleichen). Aber wäre die performanteste Methode?

[Bernhard Geyer]

Wieso nimmt man nicht einfach die Equals-Methode?

Bis auf die Prüfung ob man nicht die gleichen Instanzen vergleicht ist diese schon sehr schnell.

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