Schnellstes Entfernen von Chars aus einem String?

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