Strings vergleichen optimieren?

FloFri · Beiträge: 97

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:

markieren

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. · Beiträge: 1672

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 · Beiträge: 1173 Erhaltene Danke: 14 RAD Studio XE2

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:

markieren

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.

markieren

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 (english) vorbeischauen.

_________________
Ist Zeit wirklich Geld?

FloFri · Beiträge: 97

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 · Beiträge: 1173 Erhaltene Danke: 14 RAD Studio XE2

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

Hier ein noch schnellerer Code:

markieren

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;

_________________
Ist Zeit wirklich Geld?

FloFri · Beiträge: 97

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 · Beiträge: 1173 Erhaltene Danke: 14 RAD Studio XE2

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.

_________________
Ist Zeit wirklich Geld?

Moritz M. · Beiträge: 1672

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 · Beiträge: 97

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:

markieren

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 · Beiträge: 1173 Erhaltene Danke: 14 RAD Studio XE2

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

_________________
Ist Zeit wirklich Geld?

FloFri · Beiträge: 97

äh, jo

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 · Verfasst: 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 · Beiträge: 1173 Erhaltene Danke: 14 RAD Studio XE2

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

markieren

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;

_________________
Ist Zeit wirklich Geld?

FloFri · Beiträge: 97

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 · Beiträge: 1173 Erhaltene Danke: 14 RAD Studio XE2

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.

_________________
Ist Zeit wirklich Geld?

FloFri · Beiträge: 97

Die Fragen kann ich mit JA beantworten.

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

MSCH · Verfasst: 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 · Beiträge: 97

gute idee, dadurch wird die zumindest etwas kleiner

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme