Schnelles Ersetzen von String
-
- 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
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?
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
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
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
-
- 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)
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)
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
Michael Springwald
-
- 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
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
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
- 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:
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).
-
- 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)
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 ?
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
Michael Springwald
-
- 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
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:
Daraus sind die Folgenden 5 Varianten entstanden:
Stringreplace über TStringlist.Text und Lazarus-Stringreplace sowie Fastcode-Stringreplace:
Stringreplace zeilenweise über TStringlist und Lazarus-Stringreplace sowie Fastcode-Stringreplace:
Über Dateioperationen mit der Funktion aus der Dp in einer Unit verpackt.
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)
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 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;
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;
Code: Alles auswählen
FileReplaceStrings(FileNameEdit1.FileName, #9, ',');
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) 127-mal heruntergeladen
-
- fastcodeansistringreplace.pas
- FastCode-Unit für StringReplace
- (37.31 KiB) 121-mal heruntergeladen
Johannes
-
- 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)
@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 !)
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
Michael Springwald
- 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:
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).
-
- 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:
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.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.
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
-
- 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:
Bei ner Ramdisk werden die Daten auch erst in den Ram kopiert also kein Unterschied.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.
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/