Schnelles Ersetzen von String

Für Fragen zur Programmiersprache auf welcher Lazarus aufbaut
monta
Lazarusforum e. V.
Beiträge: 2809
Registriert: Sa 9. Sep 2006, 18:05
OS, Lazarus, FPC: Linux (L trunk FPC trunk)
CPU-Target: 64Bit
Wohnort: Dresden
Kontaktdaten:

Schnelles Ersetzen von String

Beitrag von 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?
Johannes

Christian
Beiträge: 6079
Registriert: Do 21. Sep 2006, 07:51
OS, Lazarus, FPC: iWinux (L 1.x.xy FPC 2.y.z)
CPU-Target: AVR,ARM,x86(-64)
Wohnort: Dessau
Kontaktdaten:

Beitrag von 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.
W.m.k.A.h.e.m.F.h. -> http://www.gidf.de/

slai
Beiträge: 211
Registriert: Fr 27. Apr 2007, 17:36
Wohnort: Zürich
Kontaktdaten:

Beitrag von 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
Windows 7, Lazarus 0.9.28.2 fpc 2.2.4, Firebird 2.1, Zeoslib 6.6.6-stable

pluto
Lazarusforum e. V.
Beiträge: 7192
Registriert: So 19. Nov 2006, 12:06
OS, Lazarus, FPC: Linux Mint 19.3
CPU-Target: AMD
Wohnort: Oldenburg(Oldenburg)

Beitrag von 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)
MFG
Michael Springwald

piper62
Beiträge: 131
Registriert: Sa 5. Apr 2008, 17:57
OS, Lazarus, FPC: Linux (Debian, Xubuntu), MacOS X, MS Win, Android, Web
CPU-Target: 32Bit/64Bit
Wohnort: Ulm

Beitrag von 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
Lazarusforum e. V.
Beiträge: 7192
Registriert: So 19. Nov 2006, 12:06
OS, Lazarus, FPC: Linux Mint 19.3
CPU-Target: AMD
Wohnort: Oldenburg(Oldenburg)

Beitrag von pluto »

Es gibt sehr schnelle StringReplace Varianten.
MFG
Michael Springwald

Christian
Beiträge: 6079
Registriert: Do 21. Sep 2006, 07:51
OS, Lazarus, FPC: iWinux (L 1.x.xy FPC 2.y.z)
CPU-Target: AVR,ARM,x86(-64)
Wohnort: Dessau
Kontaktdaten:

Beitrag von 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.
W.m.k.A.h.e.m.F.h. -> http://www.gidf.de/

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 6857
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Burgenland
Kontaktdaten:

Beitrag von af0815 »

Ev. bist du da mit (Unix)Shellbefehlen schneller. Wenn du das ganze in einen entsprechenden Ausdruck bringen kannst.
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

pluto
Lazarusforum e. V.
Beiträge: 7192
Registriert: So 19. Nov 2006, 12:06
OS, Lazarus, FPC: Linux Mint 19.3
CPU-Target: AMD
Wohnort: Oldenburg(Oldenburg)

Beitrag von 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 ?
MFG
Michael Springwald

Christian
Beiträge: 6079
Registriert: Do 21. Sep 2006, 07:51
OS, Lazarus, FPC: iWinux (L 1.x.xy FPC 2.y.z)
CPU-Target: AVR,ARM,x86(-64)
Wohnort: Dessau
Kontaktdaten:

Beitrag von 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.
W.m.k.A.h.e.m.F.h. -> http://www.gidf.de/

monta
Lazarusforum e. V.
Beiträge: 2809
Registriert: Sa 9. Sep 2006, 18:05
OS, Lazarus, FPC: Linux (L trunk FPC trunk)
CPU-Target: 64Bit
Wohnort: Dresden
Kontaktdaten:

FastCode heißt die Lösung

Beitrag von 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)
Dateianhänge
Stringreplace_Vergleich.pdf
Ergebnisse
(36.11 KiB) 126-mal heruntergeladen
fastcodeansistringreplace.pas
FastCode-Unit für StringReplace
(37.31 KiB) 120-mal heruntergeladen
Johannes

pluto
Lazarusforum e. V.
Beiträge: 7192
Registriert: So 19. Nov 2006, 12:06
OS, Lazarus, FPC: Linux Mint 19.3
CPU-Target: AMD
Wohnort: Oldenburg(Oldenburg)

Beitrag von 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 !)
MFG
Michael Springwald

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 6857
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Burgenland
Kontaktdaten:

Beitrag von 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.
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

monta
Lazarusforum e. V.
Beiträge: 2809
Registriert: Sa 9. Sep 2006, 18:05
OS, Lazarus, FPC: Linux (L trunk FPC trunk)
CPU-Target: 64Bit
Wohnort: Dresden
Kontaktdaten:

Beitrag von monta »

af0815 hat geschrieben: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.
Johannes

Christian
Beiträge: 6079
Registriert: Do 21. Sep 2006, 07:51
OS, Lazarus, FPC: iWinux (L 1.x.xy FPC 2.y.z)
CPU-Target: AVR,ARM,x86(-64)
Wohnort: Dessau
Kontaktdaten:

Beitrag von 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.
W.m.k.A.h.e.m.F.h. -> http://www.gidf.de/

Antworten