Schnellstes Entfernen von Chars aus einem String?

[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.