Schnelles Ersetzen von String

[monta]

Ich such nach einer möglichst performanten Möglichkeit, bestimmte Zeichen innerhalb von Dateien zu ersetzen. Konkrett geht es um zwei Probleme:

1. Alle Tabulatoren durch ein anderes Char austauschen
2. Alle Hochkommas entfernen

Das Problem liegt hauptsächlich an der größe der Dateien. Es handelt sich um CSV-artige Textdateien von mehreren MB. Somit ist ein einfaches StringReplace schon erschreckend langsam.

Gibt es eine Möglichkeit, das ganze schneller als mit StringReplace durchzuführen?

[Christian]

Beim Stringreplace musst du ja die ganze datei erstmal in den Hauptspeicher laden und dann ersetzen und zurückspeichern. Ich könnte mir vorstellen das das Zeilenweise mit den alten Dateiverarbeitungsroutinen eine Ecke schneller werden könnte.

[slai]

Hy monta

In dem fall, wenn du nur ein char ersetzen möchtest, musst du brute-force durchs file gehen ansonsten wenn du ein text hast und ein pattern suchst gibts 2 schöne möglichkeiten (Pattern Matching)

1. The Boyer-Moore Algorithm
2. The Knuth-Morris-Pratt Algorithm

aber eben in deinem fall mit 1nem zeichen wirst du O(n) Laufzeit haben. Und wie Christian schon erwähnt hat, die datei zeilenweise auslesen.

gruss
slai

[pluto]

schau doch mal hier vorbei:
http://www.delphipraxis.net/topic77274_ ... ingreplace" onclick="window.open(this.href);return false;
http://www.delphipraxis.net/topic6960_e ... ingreplace" onclick="window.open(this.href);return false;
http://www.delphipraxis.net/topic58764_ ... ingreplace" onclick="window.open(this.href);return false;

Aber den Thread den ich eigentlich gesucht habe, habe ich noch nicht wieder gefunden, die haben dort eine angeblich sehr schnelle Procedure entwickelt. Die alles in den Schatten Stellt. Evlt. finde ich sie noch.

einer der Links ist auch für CVS. Was du auch angesprochen hast.
(Ich möchte keine Werbung machen, aber sehr viel von den was sie dort haben läuft mit etwas glück auch unter Lazarus mit einigen oder wenigen Anpassungen)

[piper62]

Hallo,

mach doch mal den Versuch eine betreffende Datei auf einer RAM Disk abzulegen (kein Nadelöhr wegen des Plattenzugriffs). Dann kannst Du dort zeilenweise durchgehen und damit den Rechenaufwand für die Replacefunktion beschränken. Hätte auch den Vorteil, dass es sich einfach umsetzen liesse.
Ich benutze StringReplace viel beim Bearbeiten von OpenOffice Dateien und lade sie üblicherweise komplett in ein TMemo, dort ersetze ich dann alles auf einen Schlag.
Ehrlichgesagt kann ich mir kaum vorstellen, dass es wesentlich schneller geht. Stringvergleich mit Ersetzen ist halt aufwändig...
Aber ein Versuch über eine Datei auf einer RAM Disk wäre es wert.

Gruss,
Tibor

[pluto]

Es gibt sehr schnelle StringReplace Varianten.

[Christian]

Also das mit der Ramdisk ist jawohl das umständlichste was es gin dann kannst sie auch gleich komplett in ne Stringlist laden wie dus sicher gemacht hast kommt aufs selbe raus.

[af0815]

Ev. bist du da mit (Unix)Shellbefehlen schneller. Wenn du das ganze in einen entsprechenden Ausdruck bringen kannst.

[pluto]

Also eine TStringlist währe für mich zu langsam, Wenn es sich um Text Daten handelt würde ich das direkte Laden vorziehen, bei einer TSTringlist müsste ja erst die Komplette Datei in den Speicher geladen werden.

Geht das mit der Ramdisk wirklich schneller ? Kann ich mir gar nicht vorstellen. Aber wenn die CVS Datei sehr groß(so über 10 GB ?) ist warum nicht ?

[Christian]

Was soll denn an einer Stringlist zu langsam sein ?
Und über 10GB Arbeitspeicher ist auch heutzutage noch recht selten.

Auch was an unix schellbefehlen schneller sein soll erschliesst sich mir nicht.
Ein Toolkit für reguläre Ausdrücke ist beim fpc dabei.

[monta]

Danke für eure Ideen.

Wir wollen es ja mal nicht ganz übertreiben...wenn die Datei 10 GB groß wäre, müsste ich mir erstmal nen anderen Rechner zulegen . Das ist dann doch schon etwas extrem. Momentan sind die Dateien so 10 bis 15 MB. Und ich denk mal, bis 50 oder 100MB könnten es werden, aber 10 GB wohl (glücklicher Weise) nicht.

Das mit der Ramdisk werd ich aus Spass mal ausprobieren, hab ich bisher noch nie gemacht. Aber es sollte wohl keinen großen Unterschied machen, da ich die datei ohnehin schon in eine Stringliste lade, und aus dieser heraus verarbeite. Abgesehen davon ist es nur bedingt komfortabel, immer erst eine Rammdisk einrichten zu müssen.

Der Haken liegt wirklich am Lazarus-eigenen Stringreplace, welches bei großen Datenmengen eine wirklich schlechte Figur macht. Dagegen ist der unterschied zwischen dem Zeilenweisen durchgehen und dem direkten Zugriff auf Stringlist.Text gar nicht so bedeutend.

Ich hab mal 5 Szenarien gebastelt, alle unter der Bedingung, das man es in Pascal ausführen will und somit Shellbefehle u.ä. erstmal raus fallen.

Neben dem Lazaruseigenen Stringreplace hab ich auch noch das Stringreplace des Fastcodeprojektes gefunden und mal getestet.
http://fastcode.sourceforge.net/Fastcod ... eplace.pas" onclick="window.open(this.href);return false;
(Auch im Anhang)

Dieses läuft mit zwei kleinen Änderungen problemlos und wesentlich schneller.
Die Änderungen:
1. {$mode delphi}
2. Auskommentieren der Funktion PosEx ab Zeile 815
(Aufruf über AnsiStringReplaceFastcodePascal(...) )

Außerdem, als Test für die Dateioperationen hab ich folgenden Code, original aus der DP probiert:

Code: Alles auswählen

//******************************************************************************
// Originalcode von:
// http://www.delphipraxis.net/topic86868_suchen+und+ersetzen+in+dateien.html" onclick="window.open(this.href);return false;
//******************************************************************************
 
unit PatchFile;
 
{$mode objfpc}{$H+}
 
interface
 
//uses
  //SysUtils;
 
  procedure FileReplaceStrings(const SrcPath, OldPattern, NewPattern: string);
 
implementation
 
procedure FileReplaceStrings(const SrcPath, OldPattern, NewPattern: string);
var r, i, j: integer;
    f: file of byte;
    offset: array of integer;
    buf: array [0..1023] of byte;
    workBuf: array of byte;
begin
  //OldPattern -> workbuf
  SetLength(workBuf, Length(OldPattern));
  for i := 0 to Length(workBuf) - 1 do
    workBuf[i]:=Ord(OldPattern[i + 1]);
 
  //Durchsuchen
  assignfile(f, SrcPath);
  reset(f);
 
  repeat
    if filepos(f) > Length(workBuf) then
      seek(f, filepos(f)-Length(workBuf));
 
    blockread(f, buf, Length(buf), r);
    //buf nach workBuf durchsuchen
    for i := 0 to Length(buf) - 1 do  //buf durchgehen
    begin
      if i >= r then break; //Ausserhalb des Buffers abbrechen
 
      for j := 0 to Length(workBuf) - 1 do  //Suchstring bei i durchgehen
      begin
        if buf[i + j] = workBuf[j] then //Anfang gefunden!
        begin
          if j = Length(workBuf) - 1 then //Komplett gefunden!
          begin
            SetLength(offset,Length(offset) + 1);
            offset[Length(offset) - 1] := filepos(f) - r + i;
            //offset[n] gibt die Position des workBuf[0] wieder
          end;
        end
        else  //Nicht komplett gefunden!
        begin
          break;
        end;
      end;// for
    end;
  until r < Length(Buf);
 
  //Alles was gefunden wurde steht in offset...
  //Gefundenes ersetzen:
 
  //replaceWith -> als Byte -> workBuf
  SetLength(workBuf,Length(NewPattern){ + 1});  //???
  for i := 0 to Length(workBuf) - 1 do
    workBuf[i] := Ord(NewPattern[i + 1]);
 
  //An jedem Offset ersetzen:
  for i := 0 to Length(offset) - 1 do
  begin
    Seek(f, offset[i]);
    BlockWrite(f, workBuf[0], Length(workBuf), r);
  end;
 
  closefile(f);
end;
 
end.

---

Daraus sind die Folgenden 5 Varianten entstanden:

Stringreplace über TStringlist.Text und Lazarus-Stringreplace sowie Fastcode-Stringreplace:

Code: Alles auswählen

Datei := TStringList.Create;
  Datei.LoadFromFile(FileNameEdit1.FileName);
  Datei.Text := StringReplace(Datei.Text, #9, ',', [rfReplaceAll]);
//  bzw. mit:
//  Datei.Text := AnsiStringReplaceFastcodePascal(Datei.Text, #9, ',', [rfReplaceAll]);
  Datei.SaveToFile(FileNameEdit2.FileName);
  Datei.Free;

Stringreplace zeilenweise über TStringlist und Lazarus-Stringreplace sowie Fastcode-Stringreplace:

Code: Alles auswählen

Datei := TStringList.Create;
  Datei.LoadFromFile(FileNameEdit1.FileName);
  for i := 0 to Datei.Count - 1 do
    Datei.Strings[i] := StringReplace(Datei.Strings[i], #9, ',', [rfReplaceAll]);
//  bzw. mit:
//  Datei.Strings[i] := AnsiStringReplaceFastcodePascal(Datei.Strings[i], #9, ',', [rfReplaceAll]);
  Datei.SaveToFile(FileNameEdit2.FileName);
  Datei.Free;

Über Dateioperationen mit der Funktion aus der Dp in einer Unit verpackt.

Code: Alles auswählen

FileReplaceStrings(FileNameEdit1.FileName, #9, ',');

Die Ergebnisse find ich doch recht erstaunlich. besonders was die Unterschiede der beiden StringReplace-Implementationen angeht.

Und mit etwas über 100ms für 200000Ersetzungen kann ich erstmal doch ganz gut leben

(Die Werte sind grob gemittelt, eine 8 bedeutet Durchlaufzeiten am Rande der Auflösung von GetTickCount sodass sowohl 0ms als auch 15ms gemessen wurden)

Ergebnis (bzw. im anhang)

[pluto]

@Christian
Natürlich ist die TStringlist langsamer, weil sie erstmal alles in den Speicher Laden muss, Erst dann habe ich Zugriff drauf. Erst wenn LoadFromFile Fertig ist, kann ich die Daten verarbeiten, wobei es in machen fällen sin macht das schon vorher zu tun.

Wie du in Montas ergbnissen sehen kannst hatte ich mit der TStringlist recht *G*
(oder ich verstehe was falsch !)

[af0815]

Bei den Dateioperationen könnte man sicherlich noch was tun, wenn es nicht ganz so allgemein schreibt. Für Einzelzeichenersetzungen kann man den Buffer linear durchgehen und die Ersetzungen direkt im Buffer machen. Ev. auch auf Byte casten und damit die Vergleiche schneller machen.

[monta]

Bei den Dateioperationen könnte man sicherlich noch was tun, wenn es nicht ganz so allgemein schreibt. Für Einzelzeichenersetzungen kann man den Buffer linear durchgehen und die Ersetzungen direkt im Buffer machen. Ev. auch auf Byte casten und damit die Vergleiche schneller machen.

Ja, sicher lässt sich da noch was machen und das ganze auf Einzelzeichen spezialisieren, aber für meine Zwecke wohl überflüssig, weil die Fastcode-Version zu unterbieten wohl ohnehin schwer sein dürfte und wenn, fällt es auch nicht so wirklich ins Gewicht.

Da ich erst Stringreplace von Laz hatte, bin ich so schon mehr als Zufrieden mit der FastCode-Variante. Auf die Dateioperationen kann ich verzichten, die mag ich eh nicht so besonders.

@Pluto also die Ergebnisse belegen nicht wirklich deine Meinung, außer für den fall, das nichts ersetzt wird, aber irgendwie laden muss man es ja immer.

[Christian]

Natürlich ist die TStringlist langsamer, weil sie erstmal alles in den Speicher Laden muss, Erst dann habe ich Zugriff drauf. Erst wenn LoadFromFile Fertig ist, kann ich die Daten verarbeiten, wobei es in machen fällen sin macht das schon vorher zu tun.

Bei ner Ramdisk werden die Daten auch erst in den Ram kopiert also kein Unterschied.

Interesant ist hier das StringReplace mit kurzen zeilen sehr viel schneller ist als mit dem gesamten Text.