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

[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 von 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;

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.