Schnellstes Entfernen von Chars aus einem String?

[PeterPanino]

Ich war jetzt im Hintergrund dauernd am Testen, und immer wenn ich eine Antwort schreiben wollte, ist mir ein anderer zuvor gekommen.

DeddyHs Variante ist tatsächlich bei weitem die schnellste, die StringReplace-Variante die mit Abstand langsamste. Bei DeddyH muss man natürlich vorher noch das Charset erstellen.

EDIT: Revidiere mich. Die letzte Variante von Zacherl ist tatsächlich am schnellsten: 10000 Durchgänge in 0,003 Sekunden bei 10 Zeichen langen Strings! Fantastisch!

[himitsu]

StringReplace ist nicht das Schnellste, aber sehr einfach.

Außerdem wurden ein paar Fakten vergessen, denn solche Dinge hängen vom Kontext ab.
* Wie lang sind die Strings?
* Was für Zeichen sollen entfernt werden?
* Wieviele Zeichen sollen entfernt werden, so durchschnittlich in Prozenz?
* Was ist schnell? (wie schnell , bzw. oft soll das gemacht werden)
* ...

[Uwe Raabe]

Die Variante mit dem TSysCharSet funktioniert allerdings nur für AnsiChar (TSysCharSet = set of AnsiChar ) bzw. bei NextGen-Compilern für Zeichen deren Ordnungszahl im Bereich 0..255 liegt.

[PeterPanino]

Danke an alle fürs Mitmachen!

[Amateurprofi]

Hier meine Version, die besonders bei längeren Strings recht flott arbeitet.

Zu einigen anderen Vorschlägen die auf TSysCharSet basieren.

Ich finde, die Vorschläge gehen an der Fragestellung vorbei, denn es war ja nicht gefragt,
Zeichen zu entfernen, die in einem TSysCharSet enthalten sind, sondern Zeichen, die
in einem anderen String enthalten sind.

In dem Zusammenhang :
Was macht ihr, wenn Zeichen zu entfernen sind, die keine Ansizeichen sind z.B. '√'

Delphi-Quellcode:

FUNCTION RemoveChars(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[C] then begin
         Inc(J);
         Result[J]:=C;
      end;
   end;
   SetLength(Result,J);
   FreeMem(P);
end;

[PeterPanino]

Zitat von Amateurprofi:

Was macht ihr, wenn Zeichen zu entfernen sind, die keine Ansizeichen sind z.B. '√'

set of Char verwenden?

Die Frage ist aber auch: Wieso ist das Nachsehen in einem Char Set schneller als Pos?

[himitsu]

Es gibt kein Set of Char WideChar.

Unit System.Character oder der Char-Helper.

[Uwe Raabe]

Zitat von himitsu:

Es gibt kein Set of Char WideChar.

Genau

Weil ein Set compilerbedingt nur aus maximal 256 Elementen bestehen kann.

Zitat von PeterPanino:

Die Frage ist aber auch: Wieso ist das Nachsehen in einem Char Set schneller als Pos?

Weil der Test auf ein gesetztes Bit in einem der CPU genehmen Speicherbereich (z.B. DWORD) deutlich schneller geht als die Suche nach einem bestimmten Substring in einem String.

[Popov]

Ohne mir nun den Code von Pos anzugucken - Pos kann mehr als nur ein Zeichen vergleichen, es kann ganze Zeichenketten vergleichen. Somit ist der Code vermutlich anders aufgebaut und dadurch langsammer.

Man kann sich das Pas auch sparen und direkt die Chars überprüfen. Dann muss man drauf achten, dass keiner der Strings leer ist. Hier ein Beispiel:

Delphi-Quellcode:

function RemoveCharsFromString(const AStr, CharsToRemove: string): string;
var
  i, k: Integer;
begin
  Result := AStr;
  if Length(CharsToRemove) = 0 then
    Exit;
  for k := 0 to Length(CharsToRemove) do
    for i := Length(Result) downto 0 do
      if Length(Result) > 0 then
        if CharsToRemove[k] = Result[i] then
          Delete(Result, i, 1);
end;

[Namenloser]

Zitat von Popov:

O

Delphi-Quellcode:

function RemoveCharsFromString(const AStr, CharsToRemove: string): string;
var
  i, k: Integer;
begin
  Result := AStr;
  if Length(CharsToRemove) = 0 then
    Exit;
  for k := 0 to Length(CharsToRemove) do
    for i := Length(Result) downto 0 do
      if Length(Result) > 0 then
        if CharsToRemove[k] = Result[i] then
          Delete(Result, i, 1);
end;

Delete ist keine gute Idee, da bei jedem zu löschenden Zeichen alle nachfolgenden Elemente umkopiert werden müssen, was im Average und Worst Case zu quadratischer Laufzeit führt.

Ich würde folgendes vorschlagen:

Delphi-Quellcode:

function RemoveCharsFromString(const AStr, CharsToRemove: string): string;
var
  i, NewLength: Integer;
begin
  SetLength(Result, AStr);
  NewLength := 0;
  for i := 1 to Length(AStr) do
  begin
    if Pos(CharsToRemove, AStr[i]) = 0 then
    begin
      Result[NewLength] := AStr[i];
      inc(NewLength);
    end;
  end;
  SetLength(Result, NewLength);
end;

Das ist für mich der beste Kompromiss aus Geschwindigkeit, Funktionalität und Einfachheit. Wenn man will, kann man das Pos natürlich auch noch durch eine eigene Schleife ersetzen.

Wenn man unbedingt noch mehr rausholen will:

Zu Sets bzw. Array of Bool[Char] ist zu sagen, dass es wohl schon einen Sinn haben dürfte, weshalb Set auf 256 Elemente begrenzt ist. Mit jedem weiteren Element wächst auch der Speicherverbrauch. Bei WideChar belegt Array of Bool bereits 65 Kilobyte. Würde man statt Bools einzelne Bits verwenden wie bei Set , sind es immer noch 8 Kilobyte. Das ist zu groß um komplett in den CPU-Cache geladen zu werden. Würde man sequenziell durch den Bereich durchlaufen, wäre das zwar kein Problem, aber Sets sind prinzipbedingt Random Access. Würde mich nicht wundern, wenn es schneller wäre, einfach in einer Schleife durch die zu löschenden Elemente zu gehen und immer zu vergleichen (wie in meinem Code), solange es eine überschaubare Anzahl Zeichen ist, die entfernt werden soll.

Für allerhöchste Performance würde ich eine Hashmap empfehlen (Open Addressing).