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

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