Schnellstes Entfernen von Chars aus einem String?

[DeddyH]

Hat denn auch mal jemand getestet, wie lange die erste Schleife braucht, wenn Chars sehr groß ist (1 GB oder mehr)?

[mm1256]

Ich hab alle Tests mit einer knapp 1 GB großen Textdatei gemacht. 3 Chars die ersetzt werden sollen, insgesamt 31805 Ersetzungen. Die Zeitunterschiede der letzten Versionen (einschließlich Zacherl + DeddyH's Versionen) sind marginal, d.h. Unterschiede sind zumindest unter Win8.1/64 nicht messbar. Die paar Ticks Differenz die ich noch messen kann, sind zudem mit normalen Messmethoden via TickCount nicht permanent nachvollziehbar (CPU-Cache usw.)

Ist also schon fast Geschmacksache, was man nimmt: Strings, PChars oder das Bool-Array.

[DeddyH]

Ich glaube, Du hast mich falsch verstanden. Ich meinte den String mit den Ersetzungen, also den 2.Parameter.

[himitsu]

Zitat:

Zitat von DeddyH (Beitrag 1295512)

Hat denn auch mal jemand getestet, wie lange die erste Schleife braucht, wenn Chars sehr groß ist (1 GB oder mehr)?

Dann sollte man sich überlegen das andersrum anzugehn, anstatt massig auszuschließen,
definiert man dort die paar erlauben Zeichen. :zwinker:

[Bjoerk]

"wenn Chars sehr groß ist (1 GB oder mehr)" macht hier nicht so viel Sinn, Chars i.d.R. <= 255 bzw. 65535 Zeichen.

[TRomano]

Wir haben doch auch nur max. 65535 Zeichen in Unicode, da wir doch die Chars einzeln betrachten, oder habe ich da was verpasst ?
Man sollte bei dem Algo wirklich beachten, ab wann (Anzahl der Chars) es sich wirklich noch "lohnt" zu Löschen.

[himitsu]

Unicode (UTF-16) hat zwar 2 Byte pro "Char", aber es sind dennoch die Zeichen 0 bis $10FFFF (1114111+1-2*1024) definiert, aber keiner der Codes hier kommt mit den armen vernachlässigten Surrogates klar.

[TRomano]

Wie auch immer ... man sollte sich wirklich überlegen, dass man, wenn man einsprachige Texte als gegeben ansieht, die Such-Char-Anzahl nicht überdimensioniert. Damit kontakariert man ja die eigentliche Funktion.

[Amateurprofi]

Zitat:

Zitat von Bjoerk (Beitrag 1295506)

Japp. Das dürfte auch der Minimale Zeitunterschied zu Zacherl gewesen sein. Wenn man sprechende Variablenbezeichner einführt, sieht man man auch daß es sich um einen BoyerMoore für Substrings der Länge 1 handelt. Habs in meine Sammlung aufgenommen (hab öfters mal ein BlankReplace und dergleichen). Thanx to Zacherl und Amateurprofi. :)

Delphi-Quellcode:

class function TStrUtils.RemoveChars(const S, Chars: string): string; // Chars CaseSensitive;
var
  I, Index: integer;
  Skip: array[Char] of boolean;
begin
  FillChar(Skip[#0], Length(Skip) * SizeOf(Skip[#0]), 0);
  for I := 1 to Length(Chars) do
    Skip[Chars[I]] := true;
  SetLength(Result, Length(S));
  Index := 0;
  for I := 1 to Length(S) do
    if not Skip[S[I]] then
    begin
      Inc(Index);
      Result[Index] := S[I];
    end;
  SetLength(Result, Index);
end;

Das Array "Skip" als lokale Variable heißt 64Ki Bytes auf dem Stack.
IdR sollte das unproblematisch sein, aber ich vermeide das gern.

[himitsu]

Hier ging es ja um Geschwindigkeit und da ist Stack nunmal schneller.

[Amateurprofi]

Zitat:

Zitat von Dejan Vu (Beitrag 1295467)

PS: Wieso misst Du die Zeit so komisch? Ich würde das so machen:
Führe 'RemoveChars' 1000x aus und miss die Zeit, danach führe 'RemoveCharsFromString' 1000x aus. Teile beide Zeiten durch 1000. Damit hast Du auch die 18ms Ungenauigkeit vom 'TimeStamp' (falls es die gibt) bereinigt.

N mal laufen lassen und dann die Zeit durch N teilen heißt, dass alles, was das System in der Zeit macht, in die Zeitmessung einfließt.
Genau das möchte ich mit den Einzelmessungen ja vermeiden.
Die Annahme ist, dass zumindest bei einem der Durchläufe keine Interrupts stattfinden.

"TimeStamp" braucht minimal so um die 25 CPU-Ticks (nicht ms), aber da kann man auch Überraschungen erleben.
Versuch mal

Delphi-Quellcode:

   MinT1:=High(Int64);
   MaxT1:=0;
   for I:=1 to 1000000 do begin
      T0:=TimeStamp;
      T1:=TimeStamp;
      Dec(T1,T0);
      MinT1:=Min(MinT1,T1);
      MaxT1:=Max(MaxT1,T1);
   end;
   ShowMessage(IntToStr(MinT1)+#13+IntToStr(MaxT1));

[Amateurprofi]

Zitat:

Zitat von DeddyH (Beitrag 1295512)

Hat denn auch mal jemand getestet, wie lange die erste Schleife braucht, wenn Chars sehr groß ist (1 GB oder mehr)?

Lange braucht sie.
Aber hast du auch hinterfragt, wie lange "Pos" braucht, um X Mal ein Zeichen in einem 1GB-String NICHT zu finden?

Hab ich mal gemacht, aber mit "nur" 1 MB.

Delphi-Quellcode:

SetLength(R,1000000);
   for I:=1 to Length(R) do R[I]:=Chr(Random(26)+Ord('A'));

32 Bit Umgebung
Ergebnisse gleich
Min und Max CPU-Ticks für 1 Durchläufe
T1 Min 1529298460 Max 1529298460
T2 Min 6510004 Max 6510004


PS:
R ist hier nicht die in meiner Test-Prozedur deklarierte Konstante sondern eine Variable.

[Amateurprofi]

Zitat:

Zitat von himitsu (Beitrag 1295577)

Hier ging es ja um Geschwindigkeit und da ist Stack nunmal schneller.

Ja, es entfällt AllocMem und FreeMem, aber dafür hast du zusätzlich FillChar.
AllocMem verwendet zum Füllen des Memories mit Nullen eine ähnliche Methode wie FillChar, allerdings ohne den Overhead den FillChar nun einmal hat.
Unterm Strich dürfte das ein Nullsummenspiel sein.
Kannst ja mal testen.
Meine Messungen bei 1 Mio Durchläufen ergaben, das AllocMem+FreeMem geringfügig schneller war, wenn ich die Min-Zeiten ansah, dafür, auch das sei gesagt, deutlich mehr, bei dem Max-Zeiten.

[himitsu]

Ich mach es teils so und teils so.
Aber statt Alloc-Zeugs verwende ich lieber dynamische Arrays, mit automatischer Freigabe.

entweder statisch oder dynamisch und selten manuell

[Harry Stahl]

Das müsste man noch mal wie untenstehend etwas beschleunigen können. Wie viel das schneller ist, hängt davon ab, ob der Text zu ersetzende Zeichen enthält und wenn ja, ab wann.

In der vorherigen Variante erfolgen IMMER Allokationen von Speicherbereich und zuweisende Speicheroperationen, auch wenn der Text gar keine zu ersetzende Zeichen enthält (eben durch das charweise kopieren).

Hier erfolgt das kopieren nur dann, wenn zu ersetzenden Zeichen vorhanden sind und nur ab der Stelle, wo das erste zu ersetzende Zeichen vorliegt. Liegt kein zu ersetzendes Zeichen vor, steigt die Funktion schon bei [1] aus und liefert den unveränderten String als Ergebnis zurück. Wenn man also viele Aufrufe dieser Funktion im Programmablauf hat und oft gar keine Ersetzungen vorgenommen werden müssen, dann sollte die Sache noch mal spürbar beschleunigt werden können.

Delphi-Quellcode:

function RemoveCharsEx(const S, Chars: string): string; // Chars CaseSensitive;
var
   I, Index: integer;
   Skip: array[Char] of boolean;
   StartPos, LastPos: Integer;
begin
   FillChar(Skip[#0], Length(Skip) * SizeOf(Skip[#0]), 0);

   for I := 1 to Length(Chars) do
     Skip[Chars[I]] := true;

   Result := S; // Ergebnis vorbelegen
   StartPos := -1;

   for i := 1 to length (s) do // Prüfen, ob Text zu ersetzende Zeichen enthält
     if skip[S[i]] then begin
       StartPos := i;
       LastPos := i;
       break;
     end;

   if StartPos = -1 then exit; // [1] Text enthielt keine zu ersetzenden Zeichen

   for I := StartPos to Length(S) do
     if not Skip[S[I]] then
     begin
       Result[LastPos] := S[I];
       Inc(LastPos);
     end;

   SetLength(Result, LastPos-1);
end;

Zum Aspekt der Surrogates hat himitsu ja schon einen Hinweis gegeben (seltsamerweise hat es bei einem Test auch mit Surrogates funktioniert, aber das war wohl nur Zufall).

[himitsu]

Ja, wenn man einen Surrogare entfernt und nur der vorkommt, dann klappt es, aber versuch mal von zwei Aufeinanderfolgenden nur Einen zu entfernen, ohne den Anderen zu schrotten. :zwinker:
Bei einer Einzelzeichenbearbeitung (Char) praktisch unmöglich.

[Dejan Vu]

Zitat:

Zitat von Amateurprofi (Beitrag 1295578)

N mal laufen lassen und dann die Zeit durch N teilen heißt, dass alles, was das System in der Zeit macht, in die Zeitmessung einfließt.

Ich sorge dafür, das ein Durchlauf ca. 1 Sekunde braucht. Das Messe ich 10x und dann reicht mir das. Wenn ich das für jeden Kandidaten direkt hintereinander mache, dann bekomme ich -bis auf das Grundrauschen- reproduzierbare Ergebnisse, und zwar auf +/- 5% genau. Das reicht mir vollkommen aus. Genauer kann man das eh nicht hinbekommen.

Daher die Frage. Aber so muss ich das auch mal probieren.

[Harry Stahl]

@himitsu: Ich bin im Prinzip ja Deiner Meinung.

Allerdings stimmt der Praxis-Test damit nicht überein: Aus dem anliegenden Screenshot ist erkennbar, dass im zu ersetzenden Text am Anfang direkt zwei Surrogates-Chars nebeneinander liegen, nach Aufruf der Remove-Funktion wird nur das eine ersetzt, das andere (und der sonstige Text) bleibt (unbeschädigt) erhalten. Warum, ist mir selber momentan ein Rätsel.

Edit: Eigentlich bin ich davon ausgegangen, dass in dem Falle, wo Surrogates beteiligt sind, beim Durchlaufen des zu ersetzenden Strings für jede Stelle (IsSurrogate[i]) aufgerufen werden müsste und dann eben bei Bejahung die Kopieraktion mit zwei UTF-16-Chars zu erfolgen hätte.

[himitsu]

Wenn man die WideChar einzeln behandelt, dann geht in diesem Prozess die Verbindung zwischen High-Surrogate und Low-Surrogate verloren.

Delphi-Quellcode:

1234AB5AC6789

Wenn ich nun AB279 entferne, dann müsste eigentlich

Delphi-Quellcode:

1345AC68

[B] raus kommen,
aber wenn man einzeln A B 2 7 9 entfernt, dann wird auch ein Teil (A) des zweiten Surrogates entfernt.
Und

Delphi-Quellcode:

1345C68

ist nunmal falsch.

Wenn man "Texte" zusammenhängend verarbeitet (z.B. Pos), dann gibt es eigentlich nie ein Problem, da dort die Verbindung bestehen bleibt,
aber bei dieser Art der getrennten Verarbeitung war's das halt.

Das ist auch der Grund, warum man für High- und Low-Surrogate nicht den selben Bereich genutzt hat, auch wenn das vom Speicherverbrauch her schlechter ist, da der Wert doppelt soviel Werte in einem Char blockiert.
Allergings ist so eine implizite Trennung und Erkennung an nur einem einzelnen Char möglich, um was es sich dabei haandelt und ob der zweite Teil davor oder dahinter liegt.

[Namenloser]

Zitat:

Zitat von Amateurprofi (Beitrag 1295462)

Zitat:

Zitat von Namenloser (Beitrag 1295290)

Meine ist also nicht nur einfacher, sondern auch durchweg schneller. (CPU i7 4790K, 64 Bit)
Was sagst du nun?

Dazu sage ich, dass ich das nicht nachvollziehen kann.
Auf meinem Rechner (I7 2600K) sind die Ergebnisse so:

32 Bit Umgebung
Ergebnisse gleich
Min und Max CPU-Ticks für 1000 Durchläufe
T1 Min 141756 Max 358172
T2 Min 18144 Max 137786

64 Bit Umgebung
Ergebnisse gleich
Min und Max CPU-Ticks für 1000 Durchläufe
T1 Min 165112 Max 377076
T2 Min 19936 Max 146812

Min/Max find ich jetzt nicht so glücklich, da kriegst du gerade die größten Schwankungen. Median oder Durchschnitt wären aussagekräftiger.

Wie dem auch sei, ich kann mir den Unterschied nur so erklären, dass entweder Delphis Pos-Routine wesentlich langsamer ist als das Freepascal-Äquivalent oder erhebliche Unterschiede zwischen den CPUs bestehen.

Probier es doch mal mit einer anders definierten Pos-Funktion:

Delphi-Quellcode:

function Pos(const Needle: MyChar; const Haystack: MyString): integer; inline;
var
  i: integer;
begin
  for i := 1 to length(Haystack) do
    if Haystack[i] = Needle then
    begin
      Result := i;
      exit;
    end;
  Result := 0;
end;

Bei mir ändert sich dadurch nicht wirklich was:

Code:

[dev]$ ./test
Ergebnisse gleich
35883
69671
[dev]$ ./test
Ergebnisse gleich
44440
85332
[dev]$ ./test
Ergebnisse gleich
34680
71640

Allerdings interessanterweise nur im WideChar-Fall. Im 8-Bit-Fall ist meine Routine damit nun leicht langsamer als deine. Ich vermute daher, dass Freepascals Pos-Routine im 8-Bit-Fall irgendwelche SSE-Instructions verwendet.

Edit: Okay, letzteres lag wohl nur an der Optimierungsstufe:

AnsiString, ohne eigene Pos-Funktion:
fpc test.pas
Ergebnisse gleich
38464
46625
fpc -O3 test.pas
Ergebnisse gleich
36628
40034

AnsiString, mit eigener Pos-Funktion:
fpc test.pas
Ergebnisse gleich
58889
46354
fpc -O3 test.pas
Ergebnisse gleich
39852
42474

WideString, ohne eigene Pos-Funktion:
fpc test.pas
Ergebnisse gleich
41160
73345
fpc -O3 test.pas
Ergebnisse gleich
39369
67631

WideString, mit eigener Pos-Funktion:
fpc test.pas
Ergebnisse gleich
62403
73024
fpc -O3 test.pas
Ergebnisse gleich
34298
64443


(Sorry, bin zu faul, herauszufinden, wie man hier eine Tabelle formatiert)

[Mavarik]

hmm...

Also ohne es getestet zu haben... Aber wenn ich einen 1GB langen String habe...
Wie sieht das Zeitverhalten aus, wenn ich den String in

Anzahlzeichen/Cores vorher per Pointer auf mehrere Threads aufteile?

Mavarik

[Amateurprofi]

Zitat:

Zitat von Harry Stahl (Beitrag 1295600)

Das müsste man noch mal wie untenstehend etwas beschleunigen können. Wie viel das schneller ist, hängt davon ab, ob der Text zu ersetzende Zeichen enthält und wenn ja, ab wann.

In der vorherigen Variante erfolgen IMMER Allokationen von Speicherbereich und zuweisende Speicheroperationen, auch wenn der Text gar keine zu ersetzende Zeichen enthält (eben durch das charweise kopieren).

Hier erfolgt das kopieren nur dann, wenn zu ersetzenden Zeichen vorhanden sind und nur ab der Stelle, wo das erste zu ersetzende Zeichen vorliegt. Liegt kein zu ersetzendes Zeichen vor, steigt die Funktion schon bei [1] aus und liefert den unveränderten String als Ergebnis zurück. Wenn man also viele Aufrufe dieser Funktion im Programmablauf hat und oft gar keine Ersetzungen vorgenommen werden müssen, dann sollte die Sache noch mal spürbar beschleunigt werden können.

Delphi-Quellcode:

function RemoveCharsEx(const S, Chars: string): string; // Chars CaseSensitive;
var
   I, Index: integer;
   Skip: array[Char] of boolean;
   StartPos, LastPos: Integer;
begin
   FillChar(Skip[#0], Length(Skip) * SizeOf(Skip[#0]), 0);

   for I := 1 to Length(Chars) do
     Skip[Chars[I]] := true;

   Result := S; // Ergebnis vorbelegen
   StartPos := -1;

   for i := 1 to length (s) do // Prüfen, ob Text zu ersetzende Zeichen enthält
     if skip[S[i]] then begin
       StartPos := i;
       LastPos := i;
       break;
     end;

   if StartPos = -1 then exit; // [1] Text enthielt keine zu ersetzenden Zeichen

   for I := StartPos to Length(S) do
     if not Skip[S[I]] then
     begin
       Result[LastPos] := S[I];
       Inc(LastPos);
     end;

   SetLength(Result, LastPos-1);
end;

Ich bin mir nicht sicher, ob das im Normalfall etwas bringt.

Bei

Delphi-Quellcode:

Result := S;

wird ein neuer String erzeugt und S in Result kopiert.

Bei

Delphi-Quellcode:

SetLength(Result, LastPos-1);

wird dann noch einmal ein neuer String erzeugt und wieder alles kopiert.

Wenn du dagegen am Anfang nur die Länge von Result festlegst wird ebenfalls ein neuer String erzeugt, aber es werden keine Inhalte kopiert.
Erst, wenn am Ende die Länge von Result festgelegt wird, werden Inhalte kopiert.
Bei längeren Texten wird das zweifache Kopieren von Strings m.E. eher negative Auswirkungen haben.

Lediglich dann, wenn nichts "removed" wird, also S unverändert zurückgegeben wird, bringt das Vorteile.

[Amateurprofi]

Zitat:

Zitat von Namenloser (Beitrag 1295659)

Min/Max find ich jetzt nicht so glücklich, da kriegst du gerade die größten Schwankungen. Median oder Durchschnitt wären aussagekräftiger.

Wie dem auch sei, ich kann mir den Unterschied nur so erklären, dass entweder Delphis Pos-Routine wesentlich langsamer ist als das Freepascal-Äquivalent oder erhebliche Unterschiede zwischen den CPUs bestehen.

Probier es doch mal mit einer anders definierten Pos-Funktion:

Delphi-Quellcode:

function Pos(const Needle: MyChar; const Haystack: MyString): integer; inline;
var
  i: integer;
begin
  for i := 1 to length(Haystack) do
    if Haystack[i] = Needle then
    begin
      Result := i;
      exit;
    end;
  Result := 0;
end;

Mit der obigen Pos Funktion habe ich folgende Ergebnisse gekriegt:
32 Bit Umgebung
Ergebnisse gleich
Min und Max CPU-Ticks für 1000 Durchläufe
T1 Min 53844 Max 592624
T2 Min 20512 Max 749712

Zu

Zitat:

Min/Max find ich jetzt nicht so glücklich ...

Ich wollte damit nur mal sehen, wie die Zeiten durch systemseitige Interrupts beeinflusst werden.
Für mich sind eigentlich nur die Min-Werte aussagekräftig, wohlbemerkt in der Hoffnung, dass bei zumindest einem Durchlauf keine Interrupts dazwischen funken.
Durchschnittswerte sind für mich nicht aussagekräftig, denn die beinhalten dann ja Zeiten in denen das System irgend etwas macht, was mit der zu testenden Funktion überhaupt nichts zu tun hat.
Beim Vergleich ob man schneller mit dem Auto oder mit dem Zug von Hamburg nach Berlin kommt, wird man ja auch Testfahrten, bei denen der Zug oder das Auto eine Panne hatte, von der Wertung ausschließen.
Dass in der Praxis beide, Auto wie auch Zug, einmal eine Panne haben können, ist klar, jedoch kann dieser Fall nicht die Basis sein für die grundsätzliche Aussage, was denn schneller ist.

[Namenloser]

Zitat:

Zitat von Amateurprofi (Beitrag 1295664)

Zu

Zitat:

Min/Max find ich jetzt nicht so glücklich ...

Ich wollte damit nur mal sehen, wie die Zeiten durch systemseitige Interrupts beeinflusst werden.
Für mich sind eigentlich nur die Min-Werte aussagekräftig, wohlbemerkt in der Hoffnung, dass bei zumindest einem Durchlauf keine Interrupts dazwischen funken.
Durchschnittswerte sind für mich nicht aussagekräftig, denn die beinhalten dann ja Zeiten in denen das System irgend etwas macht, was mit der zu testenden Funktion überhaupt nichts zu tun hat.
Beim Vergleich ob man schneller mit dem Auto oder mit dem Zug von Hamburg nach Berlin kommt, wird man ja auch Testfahrten, bei denen der Zug oder das Auto eine Panne hatte, von der Wertung ausschließen.
Dass in der Praxis beide, Auto wie auch Zug, einmal eine Panne haben können, ist klar, jedoch kann dieser Fall nicht die Basis sein für die grundsätzliche Aussage, was denn schneller ist.

Allerdings ist das Handicap durch Interrupts für beide Funktionen gleich, und es sind meistens nur weniger Ausreißer vorhanden, von daher sind die Durchschnittswerte schon einigermaßen repräsentativ. Median wäre natürlich besser, aber umständlicher zu implementieren.

Die Min-Werte sind auch nicht unbedingt verlässlich. Der Tick-Counter ist nämlich zwischen den CPU-Kernen nicht synchron. Falls das Programm also während der Ausführung auf einen Kern verschoben wird, kriegst du inkonsistente Ergebnisse. Im Internet findest du Fälle, wo der Vergleich zweier aufeinanderfolgender Timestamps deshalb sogar negative Werte ergab. Du wirst also nach unten genau so Ausreißer kriegen wie nach oben.

[Uwe Raabe]

Zitat:

Zitat von Amateurprofi (Beitrag 1295663)

Bei

Delphi-Quellcode:

Result := S;

wird ein neuer String erzeugt und S in Result kopiert.

Das stimmt nicht ganz. Mit der Zuweisung wird zunächst nur der Referenzzähler des Strings erhöht. Erst wenn eine Änderung in Result erfolgt wird ein neuer String angelegt und der Inhalt kopiert.

Zitat:

Zitat von Amateurprofi (Beitrag 1295663)

Bei

Delphi-Quellcode:

SetLength(Result, LastPos-1);

wird dann noch einmal ein neuer String erzeugt und wieder alles kopiert.

Stimmt auch nur dann, wenn die neue Länge größer ist als die alte, was aber in diesem Fall gar nicht vorkommen kann.

Werden also keine Zeichen gelöscht, erfolgt auch kein Erzeugen eines neuen Strings. Andernfalls hat man auch nur einen String-Kopiervorgang. Wollte man auch den vermeiden, müsste man den OriginalString manipulieren. Dazu müsste S als var-Parameter deklariert werden und alle result durch S ersetzt werden. Die Zuweisung kann dann natürlich entfallen.

Delphi-Quellcode:

procedure RemoveCharsEx(var S: string; const Chars: string); // Chars CaseSensitive;
var
   I, Index: integer;
   Skip: array[Char] of boolean;
   StartPos, LastPos: Integer;
begin
   FillChar(Skip[#0], Length(Skip) * SizeOf(Skip[#0]), 0);

   for I := 1 to Length(Chars) do
     Skip[Chars[I]] := true;

   StartPos := -1;

   for i := 1 to length (s) do // Prüfen, ob Text zu ersetzende Zeichen enthält
     if skip[S[i]] then begin
       StartPos := i;
       LastPos := i;
       break;
     end;

   if StartPos = -1 then exit; // [1] Text enthielt keine zu ersetzenden Zeichen

   for I := StartPos to Length(S) do
     if not Skip[S[I]] then
     begin
       S[LastPos] := S[I];
       Inc(LastPos);
     end;

   SetLength(S, LastPos-1);
end;

[Amateurprofi]

Zitat:

Zitat von Uwe Raabe (Beitrag 1295699)

Zitat:

Zitat von Amateurprofi (Beitrag 1295663)

Bei

Delphi-Quellcode:

Result := S;

wird ein neuer String erzeugt und S in Result kopiert.

Das stimmt nicht ganz. Mit der Zuweisung wird zunächst nur der Referenzzähler des Strings erhöht. Erst wenn eine Änderung in Result erfolgt wird ein neuer String angelegt und der Inhalt kopiert.

Zitat:

Zitat von Amateurprofi (Beitrag 1295663)

Bei

Delphi-Quellcode:

SetLength(Result, LastPos-1);

wird dann noch einmal ein neuer String erzeugt und wieder alles kopiert.

Stimmt auch nur dann, wenn die neue Länge größer ist als die alte, was aber in diesem Fall gar nicht vorkommen kann.

Werden also keine Zeichen gelöscht, erfolgt auch kein Erzeugen eines neuen Strings. Andernfalls hat man auch nur einen String-Kopiervorgang. Wollte man auch den vermeiden, müsste man den OriginalString manipulieren. Dazu müsste S als var-Parameter deklariert werden und alle result durch S ersetzt werden. Die Zuweisung kann dann natürlich entfallen.

Zu

Zitat:

Das stimmt nicht ganz. Mit der Zuweisung wird zunächst nur der Referenzzähler des Strings erhöht. Erst wenn eine Änderung in Result erfolgt wird ein neuer String angelegt und der Inhalt kopiert.

Bei mir ist das anders.

Delphi-Quellcode:

PROCEDURE TMain.Test;
var S,R,Res:String; I:Nativeint;
begin
   S:='Delphi-Praxis';
   R:='aie';
   Res:=RemoveCharsEx('Delphi-Praxis','aie');
end;

Beim

Delphi-Quellcode:

Result := S;

wird @UStrAsg aufgerufen, und da läuft folgendes:

@UStrAsg:
00407654 85D2 test edx,edx
00407656 7426 jz $0040767e
00407658 8B4AF8 mov ecx,[edx-$08]
0040765B 41 inc ecx
0040765C 7F1C jnle $0040767a
0040765E 50 push eax
0040765F 52 push edx
00407660 8B42FC mov eax,[edx-$04]
00407663 E860FBFFFF call @NewUnicodeString
00407668 89C2 mov edx,eax
0040766A 58 pop eax
0040766B 52 push edx
0040766C 8B48FC mov ecx,[eax-$04]
0040766F D1E1 shl ecx,1
00407671 E886D0FFFF call Move

Hier ist das leider nicht direkt sichtbar, aber ich kann dir versichern, dass das Move ausgeführt wurde.

Zitat:

Zitat:

Zitat von Amateurprofi (Beitrag 1295663)

Bei

Delphi-Quellcode:

SetLength(Result, LastPos-1);

wird dann noch einmal ein neuer String erzeugt und wieder alles kopiert.

Stimmt auch nur dann, wenn die neue Länge größer ist als die alte, was aber in diesem Fall gar nicht vorkommen kann.

Ja, da hast du Recht.
Da erfolgt nur ein ReallocMem
Hab ich was dazu gelernt. Danke!

[Amateurprofi]

Zitat:

Zitat von Namenloser (Beitrag 1295666)

Zitat:

Zitat von Amateurprofi (Beitrag 1295664)

Zu

Zitat:

Min/Max find ich jetzt nicht so glücklich ...

Ich wollte damit nur mal sehen, wie die Zeiten durch systemseitige Interrupts beeinflusst werden.
Für mich sind eigentlich nur die Min-Werte aussagekräftig, wohlbemerkt in der Hoffnung, dass bei zumindest einem Durchlauf keine Interrupts dazwischen funken.
Durchschnittswerte sind für mich nicht aussagekräftig, denn die beinhalten dann ja Zeiten in denen das System irgend etwas macht, was mit der zu testenden Funktion überhaupt nichts zu tun hat.
Beim Vergleich ob man schneller mit dem Auto oder mit dem Zug von Hamburg nach Berlin kommt, wird man ja auch Testfahrten, bei denen der Zug oder das Auto eine Panne hatte, von der Wertung ausschließen.
Dass in der Praxis beide, Auto wie auch Zug, einmal eine Panne haben können, ist klar, jedoch kann dieser Fall nicht die Basis sein für die grundsätzliche Aussage, was denn schneller ist.

Allerdings ist das Handicap durch Interrupts für beide Funktionen gleich, und es sind meistens nur weniger Ausreißer vorhanden, von daher sind die Durchschnittswerte schon einigermaßen repräsentativ. Median wäre natürlich besser, aber umständlicher zu implementieren.

Die Min-Werte sind auch nicht unbedingt verlässlich. Der Tick-Counter ist nämlich zwischen den CPU-Kernen nicht synchron. Falls das Programm also während der Ausführung auf einen Kern verschoben wird, kriegst du inkonsistente Ergebnisse. Im Internet findest du Fälle, wo der Vergleich zweier aufeinanderfolgender Timestamps deshalb sogar negative Werte ergab. Du wirst also nach unten genau so Ausreißer kriegen wie nach oben.

Ja, das kenne ich dass gelegentlich bei zwei direkt aufeinander folgenden RDTSC der zweite Wert kleiner ist, als der erste.
Jedoch erfolgen bei dem Test keine RTDSC direkt hintereinander.
Und selbst wenn: Dann würde ich einen MinWert < 0 sehen, der natürlich nicht plausibel ist.
Bei Durchschnittswerten würde das in der Masse anderer Messungen untergehen.
So gesehen ist das ein weiteres Argument für MinWert Betrachtung.

Und unterschiedliche TSC auf verschiedenen Kernen lassen sich doch ganz einfach in den Griff kriegen.
Bei ernsthafteren Tests mache ich das in etwa so:

Delphi-Quellcode:

var PriorityClass,Priority:Integer; SaMask,PaMask,TaMask:NativeUInt;
begin
   // Thread auf eine CPU fixieren
   GetProcessAffinityMask(GetCurrentProcess,PaMask,SaMask);
   TaMask:=1;
   while TaMask and PaMask=0 do TaMask:=TaMask shl 1;
   SetThreadAffinityMask(GetCurrentThread,TaMask);
   // Thread auf höchste Priorität setzen
   PriorityClass:=GetPriorityClass(GetCurrentProcess);
   Priority:=GetThreadPriority(GetCurrentThread);
   SetPriorityClass(GetCurrentProcess,REALTIME_PRIORITY_CLASS);
   SetThreadPriority(GetCurrentThread,THREAD_PRIORITY_TIME_CRITICAL);
   // Zeitmessungen durchführen


   // Thread für alle CPUs freigeben und Priorität auf alten Wert stellen
   SetThreadAffinityMask(GetCurrentThread,PaMask);
   SetThreadPriority(GetCurrentThread,Priority);
   SetPriorityClass(GetCurrentProcess,PriorityClass);
end;

[Harry Stahl]

Also ich hatte es gestern auch erst einmal mit dem Debugger verfolgt, bevor ich mein posting gemacht hatte. Und da war es so, dass mit

Delphi-Quellcode:

Result := s;

neuer Speicher angefordert wurde. Anscheinend greift die String-Referenzierung nicht bei Rückgabe von String-Funktionsresultaten. Würde auch einen gewissen Sinn machen, da die Funktion ja direkt nach Rückkehr quasi nicht mehr existiert und insofern dazu keine Verwaltung stattfinden kann, ob ein referenzierender String (= die Funktion) sich verändert hat.

Dennoch ist es natürlich viel schneller, eine Zuweisung auf einen Rutsch zu machen, als Charweise in einer For-Schleife.

[Uwe Raabe]

Zitat:

Zitat von Amateurprofi (Beitrag 1295869)

Zu

Zitat:

Das stimmt nicht ganz. Mit der Zuweisung wird zunächst nur der Referenzzähler des Strings erhöht. Erst wenn eine Änderung in Result erfolgt wird ein neuer String angelegt und der Inhalt kopiert.

Bei mir ist das anders.

Delphi-Quellcode:

PROCEDURE TMain.Test;
var S,R,Res:String; I:Nativeint;
begin
   S:='Delphi-Praxis';
   R:='aie';
   Res:=RemoveCharsEx('Delphi-Praxis','aie');
end;

In diesem Fall hast du wohl Recht - allerdings nur, weil der Source-String hier eine Stringkonstante ist. Auch wenn man beim Aufruf die Variablen S und R benutzt (ich vermute das war deine Absicht), bekommt man das gleiche Verhalten, da der Rückgabewert einer Funktion immer ein referenz-gezählter String ist (eben keine Konstante).

Das ist allerdings ein Sonderfall, der (vermutlich) in der praktischen Anwendung der Funktion kaum zum Tragen kommt. Du kannst ja mal den folgenden Code durch den Debugger laufen lassen:

Delphi-Quellcode:

  
function RemoveCharsEx(const S, Chars: string): string;
begin
  result := S;
end;

procedure Main;
var
  S, R, Res: String;
begin
  S := 'Delphi-Praxis'; // Referenzzähler = -1
  R := 'aie';
  S := S + S; // Referenzzähler = 1
  Res := RemoveCharsEx(S, R);
end;

Sowohl unter XE2 als auch XE7 wird bei der Zuweisung lediglich der Referenzzähler erhöht.

[Amateurprofi]

Mich hat das Thema "Remove Chars" noch nicht ganz losgelassen.
Ich habe deshalb das Ganze in ASM umgesetzt und auch ein kleines Programm zum Testen der diversen Funktionen, die hier veröffentlicht wurden, geschrieben, besser gesagt ein bereits existierendes angepasst.

Im Anhang das komplette Programm mit Source-Dateien.
Die RemoveChars-Funktionen befinden sich in der Unit RC_Funcs.
Eine kurze Beschreibung ist der Bedienung.pfd enthalten.