Entwickler-Ecke :: Thema anzeigen - Strings vergleichen optimieren?

FloFri - Mo 28.04.03 15:42
Titel: Strings vergleichen optimieren?

Hi!
Ich habe ein Problem mit dem vergleichen zweier Strings. Ich habe einen orginal-String und einen veränderten. Jetzt möchte ich genau wissen, bei dem wievielten zeichen welche änderung gemacht wurde. Ich hoffe, ihr versteht, was ich meine. Ich benutze dazu folgenden Code:

Quelltext

1:
2:
3:
4:

for i := 0 to leng do
  begin
        if orgfile[i] <> newfile[i] then changes := changes + (inttostr(i) + '|§' + newfile[i] + '!$');
  end;

in leng steht die länge von newfile. Die '|$' und '!$' benutze ich nur als Trennzeichen.

So weit, so gut, die funktion funktioniert auch perfekt. Jetzt habe ich nur folgendes Problem: Das ist extrem lahm! Bei kleinen strings ist das kein Problem, aber die grossen haben teilweise mehrere Millionen zeichen. Und da dauert das vergleichen selbst bei meinem Athlon 1800+ mehrere Stunden.

Könnte mir da wer eine schnellere möglichkeit geben? Eventuel sogar in Assembler? Bin für jede hilfe dankbar!

MfG
FloFri

Moritz M. - Mo 28.04.03 17:45

Da gibt es eigentlich keine schnellere Möglichkeit, da du bereits die schnellste benutzt. Wie kommst du auf einen string mit Millionen von Zeichen?
Und falls ich die Frage stellen darf:
Was soll das für ein Programm werden.

Zur Not musst du halt einen Balken einbauen, der den User warten lässt.

AndyB - Mo 28.04.03 19:27
Titel: Re: Strings vergleichen optimieren?

FloFri hat folgendes geschrieben:

Eventuel sogar in Assembler?

Soweit muss man gar nicht gehen. Und wenn du den obigen Quellcode nur in Assembler umschreibst, wirst du keinen Geschwindigkeitsgewinn bekommen.

Zitat:

Das ist extrem lahm! Bei kleinen strings ist das kein Problem, aber die grossen haben teilweise mehrere Millionen zeichen. Und da dauert das vergleichen selbst bei meinem Athlon 1800+ mehrere Stunden.

Geschwindigkeitsanalyse:
- Der Vergleich geht rechts schnell von statten.
- changes aufzubauen geht anfangs recht schnell. Bei zunehmender Zeichenzahl verbraucht es jedoch unmengen an Rechenpower.

Zu den Gründen:
Mit changes := changes + ... traktierst du den Speichermanager aufs Brutale.

Ein vereinfachtes Beispiel:

Quelltext

1:	s := s + '12';

Hieraus mach der Compiler folgendes

Zuerst wird ein neuer String erzeugt, der alle Zeichen von s plus den Zeichen von '12' aufnehmen kann.
Nun wird der String s in den neuen String kopiert. Das '12' wird nun an diesen angehängt.
Der alte String wird freigegeben und s zeigt nun auf den neuen String.

Wenn man das nun genauer betrachtet, so muss man feststellen, dass für jede String-"Addition" ein neuer, größerer Speicherbereich reserviert wird und die alten Daten hineinkopiert werden. Beides benötigt bei kleinen Datenmengen wenig Zeit. Aber bei 1Mio Zeichen werden unmengen an Daten kopiert. Zudem wird der Speicher immer stärker fragmentiert, da immer größere Speicherblöcke reserviert werden, die nicht in die alten hineinpassen.

Um das ganze zu umgehen sollte man von vornherein die maximale Größe des zu erzeugenden Strings ermitteln, auch wenn das heißen würde, dass man die komplette Schleife 2x durchlaufen muss.

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

// max. changes Länge ermitteln
changesLen := 0;
for i := 0 to leng do 
  if orgfile[i] <> newfile[i] then Inc(ChangesLen, Length(inttostr(i)) + 2 + 1 + 2);

SetLength(changes, changesLen);
P := PChar(changes);
for i := 0 to leng do 
begin 
  if orgfile[i] <> newfile[i] then StrCat(P, PChar(inttostr(i) + '|§' + newfile[i] + '!$'));
end;

Wen Optimierung von Delphi Code interessiert, kann mal beiOptimalCode [http://www.optimalcode.com/opguide.htm] (english) vorbeischauen.

FloFri - Mo 28.04.03 20:31

Danke, mal sehen, ob das nun schneller geht.

Auf die Frage, was das werden soll und warum die Strings so gross sind: Das soll ein Patchprogramm werden und die Strings sind einfach die Rohfassungen von beliebigen Dateien. Und bei einem 72 MB-Datei ist das nunmal so gross. (P.s.: Die Strings hab ich mit ExeMod ausgelesen, falls jemandem das was sagt!)

*edit* Dein Code will aber irgendwie auch nicht, bekomme bei der ersten schleife nach einiger zeit eine exception und changeslen steigt nicht mehr an. Mit int64 ist es das gleiche. */edit*

AndyB - Mo 28.04.03 23:36

Jetzt muss ich meinen Code schon selbst Testen. Soweit ist es jetzt schon.

Hier ein noch schnellerer Code:

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:

var
  s: string;
  changesLen: Integer;
  Len, i: Integer;
  P: PChar;
begin
  // max. changes Länge ermitteln
  changesLen := 0;
  for i := 0 to leng do
    if orgfile[i] <> newfile[i] then Inc(ChangesLen, Length(IntToStr(i)) + 2 + 1 + 2);

  if changesLen > 0 then
  begin
    SetLength(changes, changesLen);
    P := PChar(changes);
    for i := 0 to leng do
      if orgfile[i] <> newfile[i] then
      begin
        s := IntToStr(i) + '|§' + newfile[i] + '!$';
        Len := Length(s);
        Move(s[1], P[0], Len);
        Inc(P, Len);
      end;
  end;
end;

FloFri - Di 29.04.03 07:00

Der Code funktioniert bis auf eine Kleinigkeit Perfekt: Es kann sein, dass einer der beiden Strings größer ist als der andere. Wenn newfile > orgfile, dann bekomme ich in beiden Schleifen massig exceptions. Wie kann ich das anfangen. Alles was in diesem "Überhang" steht, soll als Veränderung in den String kommen.

AndyB - Di 29.04.03 09:30

Ich habe nur deinen Code optimiert. Er macht immer noch genau das, was dein Code gemacht hat.

Mitleng := Min(Length(orgfile), Length(newfile));bekommst du die Länge, die du in der Schleife durchlaufen musst.
Wenn dann Len(orgfile) < Len(newfile) musst du eben die restlichen Zeichen von newfile zu changes hinzufügen oder ggf. andersherum.

Moritz M. - Di 29.04.03 13:29

Der Fehler daran ist, dass sich leng immer auf den längeren String beziehen muss. Du musst die Schleife dann abbrechen, wenn der kürzere String zu Ende ist und dann halt noch die Anzahl Zeichen, die der längere String noch hätte, als Nichtübereinstimmung hinzufügen.

FloFri - Di 29.04.03 17:53

danke! ich glaube, das sollte zu schaffen sein :)

*edit* Sorry, aber ich muss noch einmal Stören, denn da ist irgendwo noch der Wurm drinnen. Ich benutze jetzt folgenden Code:

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:

leng := min(Length(orgfile), Length(newfile));
  // max. changes Länge ermitteln 
  changesLen := 0; 
  for i := 0 to leng do
    if orgfile[i] <> newfile[i] then Inc(ChangesLen, Length(IntToStr(i)) + 2 + 1 + 2);
  if Length(newfile) > Length(orgfile) then
    begin
      for i := Length(orgfile) to Length(newfile) do
        Inc(ChangesLen, Length(IntToStr(i)) + 2 + 1 + 2);
    end;

  if changesLen > 0 then 
  begin 
    SetLength(changes, changesLen); 
    P := PChar(changes); 
    for i := 0 to leng do 
      if orgfile[i] <> newfile[i] then 
      begin 
        s := IntToStr(i) + '|§' + newfile[i] + '!$';
        Len := Length(s);
        Move(s[1], P[0], Len);
        Inc(P, Len);
      end;
    if Length(newfile) > Length(orgfile) then
    begin
      for i := Length(orgfile) to Length(newfile) do
        begin
          s := IntToStr(i) + '|§' + newfile[i] + '!$';
          Len := Length(s);
          Move(s[1], P[0], Len);
          Inc(P, Len);
        end;
    end;
  end;

Aber der String hört immer mit |§ auf, was ja eigendlich nicht sein kann. Da muss irgendwo noch ein fehler in der längenberechnung sein, ich weis aber nicht wo!

AndyB - Di 29.04.03 18:50

Mit deinem geänderten Code hört es bei mir mit !$ auf.
Wo gibst du das ganze aus? Etwa in einem TMemo?

FloFri - Di 29.04.03 21:21

äh, jo :roll:
geht das da nicht? muss nicht unbedingt sein, das mit TMemo, aber ich weis nicht, wie ich den string sonst am einfachsten in eine Datei schreiben kann (habe bis jetzt entweder TStringlist oder TMemo dafür benutzt).

MSCH - Di 29.04.03 21:30

hmm, grübel, wenns nen Patchprog werden soll, warum liest du die Datei via mapped files komplett in den Speichel?
vielleicht mal ne andre Lösung?
grez
msch

AndyB - Di 29.04.03 23:03

FloFri hat folgendes geschrieben:

aber ich weis nicht, wie ich den string sonst am einfachsten in eine Datei schreiben kann

Auf keinen Fall über ein Memo. Bei meinen Tests hat die Zeile Memo1.Text := changes 20x so lange gedauert, wie das Aufbauen von changes.

Funktion zum schreiben eines Strings in eine Datei

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

procedure StringToFile(const Filename, Value: string);
var
  Stream: TStream;
begin
  Stream := TFileStream.Create(Filename, fmCreate);
  try
    if Length(Value) > 0 then
      Stream.Write(Value[1], Length(Value));
  finally
    Stream.Free;
  end;
end;

FloFri - Mi 30.04.03 00:01

gut, damit geht das jetzt, aber jetzt habe ich ein neues problem. ich habe mal einen test gemacht und 2 Dateien 8jeweils etwa 12 MB gross), bei denen ein paar sachen verändert wurden, verglichen. Die Datei mit dem String Changes war aber über 30 MB gross.

Wie kann man das System noch verbessern, wie gesagt, ich will ein patchprog schreiben.

AndyB - Mi 30.04.03 10:40

Zwei Fragen, die du dir stellen solltest, was die ganze Patchen erst interessant macht:

Was passiert, wenn ein oder mehrere Zeichen eingefügt wurden? Die restlichen Daten passen nicht mehr und werden alle als verändert erkannt?
Was passiert, wenn ein oder mehrere Zeichen entfernt wurden? Die restlichen Daten passen nicht mehr und werden alle als verändert erkannt?

Für diese beiden Fragen musst du eine Lösung finden.

FloFri - Mi 30.04.03 19:06

Die Fragen kann ich mit JA beantworten.

Aber mit der Lösung könnte kompliziert werden, weis da jemand Rat, zumindest ansatzweise?

MSCH - Do 01.05.03 13:08

Vieleicht so ?
Die Datei du du patchen willst, durchsuchen nach den zu patchenden Strings, Offset merken (dyn Array).
Quelle bis Offset[] kopieren, neuer String, weiter bis nächsten Offset[] u.s.w..

Das ganze mit Streams, oder verry simple mit F: TextFile.

grez
msch

FloFri - Fr 02.05.03 18:49

gute idee, dadurch wird die zumindest etwas kleiner