Schnellstes Entfernen von Chars aus einem String?

[4dk2]

Interessant auch:
Bei euern letzten Versuchen ist die Geschwindigkeit von Delphi 7 zu XE3 auch nochmal anders.
Die RemoveCharsFromString() Variante wird mit XE3 schneller gegenüber D7,
Die Zweite variante RemoveChars() wird mit XE3 deutlich langsamer als bei D7.

TGESx = durchschnitt aus 1000x

XE3:

Code:

TGES1: 111026,18900
TGES2: 47264,11200

D7:

Code:

TGES1: 347124,48100
TGES2: 24214,50800

[4dk2]

Noch eine Anmerkung,

Amateurprofi, habe deine Routine noch ein bisl verbessert,
Das Verzichten auf die Zuweisung von C, bringt nochmal ca 13% mehr Geschwindigkeit bei mir.

Delphi-Quellcode:

function StringTest(const S,Remove:String):String;
type
   TBA=Array[Char] of Boolean;
   TPBA=^TBA;
var P:TPBA; I,J:Integer; C:Char;
begin
   P:=AllocMem(SizeOf(TBA));
   for I:=1 to Length(Remove) do P[Remove[I]]:=True;
   SetLength(Result,Length(S));
   J:=0;
   for I:=1 to Length(S) do begin
      //C:=S[I];
      if not P[S[I]] then begin
         Inc(J);
         Result[J]:=S[I];
      end;
   end;
   SetLength(Result,J);
   FreeMem(P);
end;

[Bjoerk]

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;

[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 von DeddyH:

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.

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

[Amateurprofi]

Zitat von DeddyH:

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.