String kopieren, was ist schneller?

[SearchBot]

Hallo,

ich suche eine Optimierung.
Folgendes Projekt habe ich da: 150MB String, genaugenommen rund 10000 Zeilen mit je ca. 18kB Zeilenlänge, von denen ich aber nur rund 1800 Zeichen brauche, und von denen auch nur 30 Zeichen pro Zeile :stupid:

Mit den optimierten (und leicht umgebauten) Fastcode-Challenge-Routinen von StringReplace :thumb: setze ich mir in wenigen Sekunden rund 30000 Marker im String, nach diesen Markern steht die Info, die ich brauche.

Delphi-Quellcode:

var TeilString, Riesenstring: AnsiString; p:integer;
//Marker ist ein einzelnes Char, zB #9
p:=PosEx(Marker,RiesenString);
repeat
 Teilstring:=copy(Riesenstring,p,1800);
 RiesenString[p]:=#32; //löschen des Markers
 p:=PosEx(Marker,RiesenString);
 //..Mache was mit dem Teilstring.. (3x weitere copy mit anderen Markern)
until p=0;

Das Copy braucht ne Weile und 150MB extra (offenbar für eine Arbeitskopie des Strings).
Gibt es was schnelleres als Copy? CopyBlock vielleicht?
Gerne auch ohne, daß nochmal 150MB im Speicher benötigt werden, weshalb ich auch auf gleiche Stringtypen achte, damit hoffentlich keine zeitaufwändige Konvertierung im Hintergrund nötig ist.

Derzeit benötigt meine Routine rund 50s für 100 Zeilen... :pale:

Danke schonmal fürs mitdenken :wink:

[Uwe Raabe]

Ich habe jetzt gerade kein XE verfügbar, aber unter XE2 entspricht das Copy im Wesentlichen einem Move-Befehl. Eine Kopie des RiesenString kann ich im erzeugten Code auch nicht finden.

Du verwendest doch hoffentlich das PosEx aus AnsiStrings und nicht das aus StrUtils?

Warum nutzt du eigentlich nicht den dritten Parameter von PosEx für die Startposition der Suche? Wie es jetzt ist, beginnt die Suche immer am Anfang des RiesenString. Deshalb musst du auch den Marker ausblenden. Abgesehen davon ist das von der Performance her eher ungünstig. So wäre es deutlich geschickter:

Delphi-Quellcode:

p:=PosEx(Marker,RiesenString, 1);
repeat
 Teilstring:=copy(Riesenstring,p,1800);
  // Annahme: der nächste Marker kann erst nach dem Teilstring kommen
 p:=PosEx(Marker,RiesenString, p + 1800);
 //..Mache was mit dem Teilstring.. (3x weitere copy mit anderen Markern)
until p=0;

[Blup]

Warum werden überhaupt die Marker im String gesetzt?
Wenn die Position einmal ermittelt wurde, kann der Teilstring doch sofort verarbeitet werden.
Warum wird zur Weiterverarbeitung eine Kopie gemacht?
Benötigt wird doch nur ein Pointer(PAnsiChar) auf das erste Zeichen und die Anzahl der zu verarbeitenden Zeichen.

Bei solch großen Dateien bietet es sich an mit Memory Mapped Files (MMF) zu arbeiten.

[Dejan Vu]

Den Teilstring muss man auch nicht kopieren. Wenn ich weiß, wo der anfängt, und wie lang er ist (1800 Zeichen), kann ich alle weiteren Operationen mit dieser Information machen. Und zuerst Marker zu verteilen, die man hinterher eh wieder rauslöscht, ist vielleicht auch nicht das Gelbe vom Ei.

Anhand welcher Kriterien werden die Marker denn gesetzt?

[Sir Rufo]

Eventuell muss man auch mal etwas anders denken.

Warum willst du die Datenquelle überhaupt ändern (Marker setzen)? Das sind Meta-Informationen, die du zur Verarbeitung benötigst und die haben in der Datenquelle nichts zu suchen.

Es reicht doch vollkommen die Position im Text zu kennen und die Länge, dann kann man mit diesen Informationen sehr hübsch sich den Teilstring aus der Datenquelle holen.

[BUG]

Frei nach Wheeler: Jedes Problem in der Informatik kann durch eine weitere Indirektionsstufe gelöst werden :mrgreen:

Die Zeiger&Länge Lösung erscheint mir sinnvoll, besonders wenn du wiederholt auf die Teilstrings zugreifen musst. Damit baust du dir praktisch einen Index auf dem Hauptstring.

Wenn du nur einmal darauf zugreifen musst, kannst du den Teilstring auch wirklich gleich verarbeiten (#3).

[SearchBot]

Hallo und danke für Euer Interesse :-D

Für alle: Riesenstring ist eine XML-Datei, genaugenommen eine Tabelle mit rund 10000 Zeilen und 572 Spalten - aus der ich nur 3 Spalten benötige...

Wahrscheinlich schieße ich mir sowieso von hinten durch die Brust ins Auge, oder so. :roll:
Aktuell ist aber dies die schnellste Lösung für mein Projekt und ich habe die letzte 4 Wochen schon allerlei probiert...

Ich habe es auch schon mit XML-Nodes und so versucht, aber verworfen, weil es zu lange Verarbeitungszeiten gibt. Wahrscheinlich habe ich auch was falsch gemacht - ist aber jetzt nicht das Thema :wink:
Daher ist mir der String-Überflieger lieber.

Zitat:

Zitat von Uwe Raabe (Beitrag 1285862)

Eine Kopie des RiesenString kann ich im erzeugten Code auch nicht finden.

Du verwendest doch hoffentlich das PosEx aus AnsiStrings und nicht das aus StrUtils?

Warum nutzt du eigentlich nicht den dritten Parameter von PosEx für die Startposition der Suche?

Die Kopie wird offenbar vom Copy-Befehl erzeugt. Ich beobachte dazu den freien Speicher vor und nach dem Befehl, um das festzustellen :wink:

Genaugenommen verwende ich das PosEx aus der optimierten FastCode-Unit. Dieser ist in Assembler geschrieben und verwendet AnsiStrings(..wobei mir jetzt gerade auffällt, daß ich die Unit AnsiStrings noch garnicht kenne?!).

Den dritten Parameter hatte ich vergessen, als ich meinen Post fern von meinem Delphi an einem anderen PC eingetippt habe. Den versuche ich auch gerade zu verwenden, um mich portionsweise durch den Riesenstring zu schieben, klappt aber grad noch nicht so wie gewünscht (ein müdes Hirn macht mehr Denkfehler :oops: )...

Zitat:

Zitat von Blup (Beitrag 1285865)

1) Warum werden überhaupt die Marker im String gesetzt?
Wenn die Position einmal ermittelt wurde, kann der Teilstring doch sofort verarbeitet werden.
2) Warum wird zur Weiterverarbeitung eine Kopie gemacht?
3) Benötigt wird doch nur ein Pointer(PAnsiChar) auf das erste Zeichen und die Anzahl der zu verarbeitenden Zeichen.

4) Bei solch großen Dateien bietet es sich an mit Memory Mapped Files (MMF) zu arbeiten.

1) Weil das am schnellsten geht und zeitgleich den Riesenstring etwas verkleint (StringReplace). Im kurzen Teilstring kann ich sie dann meine 3 Zielfelder direkt finden und rauskopieren. Dachte mir, daß das schnellergeht, als wenn ich immer den Riesenstring durchs Copy laufen lasse. Zumal ich nach dem ersten Durchlauf noch 10000 weitere Zeilen vor mir habe...

2) Eine Kopie macht offenbar der Befehl copy, wenn ich mit dem Taskmanager den "Verwendungsverlauf des physikalischen Speichers" beobachte. Daher suche ich ja eine Alternative zu Copy, wenn es geht.

3) Aah, mit Pointern hab ichs nicht so... Die Positionen bekomme ich ja leicht raus, aber es geht ja um das zeitaufwändige rauskopieren...

4) Ursprünglich bekomme ich die Datei als MemoryStream. Dann schiebe ich das geschwind in einen StringStream, dessen DataString ich dann in meinen Riesenstring (der schlicht s heißt, aber des Verständnisses wegen ich so ausführlich benenne) setze, um die Bearbeitungen durchzuführen.
MMF ist für mich jetzt ein neues Stichwort, danke schön :idea:

Zitat:

Zitat von Dejan Vu (Beitrag 1285868)

Den Teilstring muss man auch nicht kopieren. Wenn ich weiß, wo der anfängt, und wie lang er ist (1800 Zeichen), kann ich alle weiteren Operationen mit dieser Information machen. Und zuerst Marker zu verteilen, die man hinterher eh wieder rauslöscht, ist vielleicht auch nicht das Gelbe vom Ei.

Anhand welcher Kriterien werden die Marker denn gesetzt?

Im Grunde weiß ich nicht genau, ob er immer so lang ist. Daher setze ich die Marker, um für meinen dritten Wert die Endposition in der aktuellen Zeile zu finden.
Wie am Anfang beschrieben suche ich bestimmte Spalten. Jede Zielspalte bekommt einen anderen Marker, um diese Werte dann schnell wieder zu finden.
Eigentlich lösche ich nur den "Zeilen-Ende"-Marker, weil das mit dem PosEx-Offset noch nicht so klappt. Daran will ich nachher weiter basteln :wink:
Mit der Fastcode-StringReplace-Funktion, die ich zu diesem Zweck etwas umgebaut habe, werden die 150MB in gefühlten 2 Sekunden an den 10000 Stellen markiert, was ich 3x mache (also rund 6 Sekunden Vorbereitungszeit - das ist ok, finde ich).

Zitat:

Zitat von Sir Rufo (Beitrag 1285872)

1) Warum willst du die Datenquelle überhaupt ändern (Marker setzen)?
2) Es reicht doch vollkommen die Position im Text zu kennen und die Länge, dann kann man mit diesen Informationen sehr hübsch sich den Teilstring aus der Datenquelle holen.

1) Die Datenquelle wird nicht verändert, ich arbeite ja mit einer Kopie. Und die zerschnibble ich, was ich eben daraus brauche :lol:

2) genau. Und das Rausholen des Teilstrings möchte ich beschleunigen, schneller als der Befehl Copy, wenn das geht - und das geht bestimmt irgendwie...

Zitat:

Zitat von BUG (Beitrag 1285880)

Die Zeiger&Länge Lösung erscheint mir sinnvoll, besonders wenn du wiederholt auf die Teilstrings zugreifen musst. Damit baust du dir praktisch einen Index auf dem Hauptstring.

Wenn du nur einmal darauf zugreifen musst, kannst du den Teilstring auch wirklich gleich verarbeiten (#3).

Ja, sobald er schnellst möglich aus dem Riesenstring separiert ist.

Vielleicht möchtet ihr die umgebaute FastCode-StringReplace noch sehen?
Original: AnsiStringReplaceJOHIA32Unit3.pas
Ich habe sie dahingegend erweitert, daß nach jedem Fund und Replace ein anderer String gesucht wird - in diesem Fall mittels eine Zahl; also sozusagen ein StringReplace mit Counter. Passend, weil jedes Tabellenfeld zB A99, A100, A101... heißt. Das macht die ursprüngliche Routine etwas langsamer, aber ist im Vergleich immernoch superschnell :stupid:

[Sir Rufo]

Zitat:

Zitat von SearchBot (Beitrag 1285942)

Zitat:

Zitat von Sir Rufo (Beitrag 1285872)

1) Warum willst du die Datenquelle überhaupt ändern (Marker setzen)?
2) Es reicht doch vollkommen die Position im Text zu kennen und die Länge, dann kann man mit diesen Informationen sehr hübsch sich den Teilstring aus der Datenquelle holen.

1) Die Datenquelle wird nicht verändert, ich arbeite ja mit einer Kopie. Und die zerschnibble ich, was ich eben daraus brauche :lol:

2) genau. Und das Rausholen des Teilstrings möchte ich beschleunigen, schneller als der Befehl Copy, wenn das geht - und das geht bestimmt irgendwie...

Du schreibst etwas (Merker) dort hinein, wo sich deine Daten befinden. Ob das die 200.000 Kopie der Original-Daten ist spielt keine Geige. Es ist die Datenquelle, wo du deine Daten gleich herausziehen möchtest.

Also schreibe dort keinen Merkel rein, sondern merke dir die Position und die Länge. Wenn du die Daten dann brauchst, dann einfach ab der Position in der Länge die Daten aus dieser Datenquelle herausnehmen.

[BUG]

Zitat:

Zitat von SearchBot (Beitrag 1285942)

Ich habe es auch schon mit XML-Nodes und so versucht, aber verworfen, weil es zu lange Verarbeitungszeiten gibt. Wahrscheinlich habe ich auch was falsch gemacht - ist aber jetzt nicht das Thema :wink:

Bei so großen XML-Dateien sind SAX-Parser nicht uninteressant ... insbesondere wenn du später doch noch ein paar andere Infos aus der XML-Datei brauchst :stupid:

[Mavarik]

hmm warum "saust" du nicht einfach mit 2 PChars da durch.

Wenn Du an der richtigen Stelle bist von PCharDest := PCharSource bis du aus dem Bereich bist..

sonst immer nur nette inc's des PChars... nix ist schneller...

Oder habe ich da was falsch verstenden?

[Sir Rufo]

Zitat:

Zitat von Mavarik (Beitrag 1285954)

hmm warum "saust" du nicht einfach mit 2 PChars da durch.

Wenn Du an der richtigen Stelle bist von PCharDest := PCharSource bis du aus dem Bereich bist..

sonst immer nur nette inc's des PChars... nix ist schneller...

Oder habe ich da was falsch verstenden?

Das "Sausen" macht er ja schon mit diesen FastCode-Gedöns-Routinen :)

Er saust da nur über das Ziel hinaus. Erst in alle Ecken pinkeln, und dann mit der Nase am Boden die Stellen suchen, die nach Laterne unten riechen, die Stelle wischen und dann endlich dort etwas machen. Hört sich nicht nur umständlich an, ist es auch.

[Dejan Vu]

Zitat:

Zitat von Sir Rufo (Beitrag 1285958)

Hört sich nicht nur umständlich an, ist es auch.

Also :kotz: 'umständlich' ist jetzt nicht ... huälp... das richtige Wort. Bezogen auf deinen bildlichen Vergleich.

[OlafSt]

Der Ansatz ist wirklich durch die Brust ins Auge und dann ins Knie... Du hast ja mehrere Suchvorgänge, wo doch ein einzelner genügt.

- Du hast eine Routine, die den Startmarker setzt
- Du hast eine Routine, die den Endmarker setzt

Statt den String zu modifizieren, läßt du dir die Position im String jeweils zurückgeben. Das Stück kopierst du heraus und verarbeitest es weiter.

Delphi-Quellcode:

...
sp:=GetStartPosition(RiesenString);
ep:=GetEndPosition(RiesenString, sp); //Sucht ab sp nach dem Ende
VielKleinererString:=copy(RiesenString, sp, ep);
//Weiterverarbeiten des VielKleinererString

BTW... Wenn du den MemoryStream in einen StringStream uschaufelst, wird dann nicht noch eine Kopie erzeugt ? ;)

[SearchBot]

Zitat:

OlafSt: BTW... Wenn du den MemoryStream in einen StringStream uschaufelst, wird dann nicht noch eine Kopie erzeugt ?

Ja, aber das macht er nur 1x, danach gebe ich den MemoryStream und StringStream wieder frei. Hab dazu keine andere Lösung gefunden, an den String zu kommen...

Also gut, ok, :oops:

die Positionierung kann ich also noch besser machen - aber wie ist das jetzt mit dem rauskopieren meiner Werte, nachdem ich also die Positionen gefunden habe?

Gibt's da was schnelleres als copy und wie müsste das dann aussehen?

[Sir Rufo]

Ähm, du reist von Bremen über Paris, Rom, Madrid nach Hamburg, aber der Weg zur Kneipe um die Ecke ist dir zu weit?

Stell das um, nimm das Copy und schau dir die Zeiten an. Den größten Teil verbrätst du beim Suchen, Suchen

[QuickAndDirty]

Ist move für Buffer nicht eine Alternative zu copy?