Schnellstes Entfernen von Chars aus einem String?

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

[Amateurprofi]

Zitat von Namenloser:

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.

@Namenloser:
Hast du denn einmal die von dir vorgeschlagene Funktion laufen lassen?

Wenn "JA", dann hättest du merken müssen
1) In der ersten Zeile SetLength(Result, AStr); sollte eine Fehlermeldung kommen, dass man der Länge eines Strings keinen String zuweisen kann.

2) Bei if Pos(CharsToRemove, AStr[i]) = 0 then sollte dir aufgefallen sein, dass du die Position eines Strings innerhalb eines Chars abfragst, was natürlich immer 0 ergibt.

3) Bei

Delphi-Quellcode:

Result[NewLength] := AStr[i];
       inc(NewLength);

sollte es scheppern, weil du Result[0] ein Char zuweisen willst.

Zu

Zitat:

Das ist für mich der beste Kompromiss aus Geschwindigkeit, Funktionalität und Einfachheit.

Die Fragestellung in #1 war

Zitat:

Was ist die SCHNELLSTE Methode, um aus einem String alle Zeichen eines anderen Strings zu entfernen?

Es war also weder ein Kompromiss noch Funktionalität noch Einfachheit gefragt, sondern ausschließlich Schnelligkeit.

Sorry, falls du dich angegriffen fühlen solltest; aber wenn jemand einen Code der gleich 3 so offensichtliche Fehler enthält und so nicht einmal kompilierbar ist, als "Besten Kompromiss" vorstellt, dann juckt es mich schon in den Fingern.

Ich habe, nachdem ich die Fehler in deinem Code korrigiert habe, beide Funktionen laufen lassen, deine aus #28 und meine aus #19.
Als String, aus dem Zeichen entfernt werden sollen, habe ich den letzten Absatz deines Beitrages #28
und als String mit zu entfernenden Zeichen deinen Nick "Namenloser" benutzt.
Die Ergebnisse waren für mich nicht überraschend.

So habe ich getestet;

Delphi-Quellcode:

PROCEDURE TMain.Test;
FUNCTION TimeStamp:Int64;
asm
   rdtsc
   {$IFDEF CPUX64}
   shl   rdx,32
   or    rax,rdx
   {$ENDIF}
end;
const
   S='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.';
   R='Namenloser';
   Res:Array[Boolean] of String=('Ergebnisse verschieden','Ergebnisse gleich');
var
   T0,T1,T2:Int64; S1,S2:String;
begin
   T0:=TimeStamp;
   S1:=RemoveCharsFromString(S,R);
   T1:=TimeStamp;
   S2:=RemoveChars(S,R);
   T2:=TimeStamp;
   Dec(T2,T1);
   Dec(T1,T0);
   ShowMessage(Res[S1=S2]+#13+IntToStr(T1)+#13+IntToStr(T2));
end;

[Namenloser]

Zitat von Amateurprofi:

@Namenloser:
Hast du denn einmal die von dir vorgeschlagene Funktion laufen lassen?

Nein, ich habe hier kein Delphi und auch schon länger nichts mehr damit gemacht. Das war nur schnell im Beitragseditor dahingeschrieben. Vielleicht hast du es auch schon mal erlebt, wenn du eine Weile nicht mit einer Sprache gearbeitet hast, dass man etwas einrostet und z.B. mal nicht daran denkt, dass der String bei 1 anfängt.

Zitat von Amateurprofi:

Die Fragestellung in #1 war

Zitat:

Was ist die SCHNELLSTE Methode, um aus einem String alle Zeichen eines anderen Strings zu entfernen?

Es war also weder ein Kompromiss noch Funktionalität noch Einfachheit gefragt, sondern ausschließlich Schnelligkeit.

Na ja weißte, er verrät nirgendwo, wofür er das braucht. Nicht immer meinen Leute wirklich das, was sie sagen. Kann ja z.B. sein, dass er vorher mit mehrfachem StringReplace gearbeitet hat und eine Geschwindigkeitserhöhung um den Faktor 1000 (wenn man #9 glaubt) ihm bereits mehr als ausreicht. Letztendlich ist sowieso immer alles ein Kompromiss. Du wirst immer eine Lösung finden, die noch 1% schneller ist und dafür 1000 mal so kompliziert. Irgendwo muss man halt die Reißleine ziehen, und nach meiner Erfahrung tut man das am besten so früh wie möglich. Außerdem ist es, ohne die Eingangsdaten zu kennen, gar nicht möglich, zu beantworten, was wirklich am schnellsten ist.

Ich habe es schon etliche Male hier erlebt, dass jemand die Frage stellt „Wie mache ich am schnellsten X?“ und damit einen Optimierungswettbewerb über mehrere Seiten entfacht. Zwei Tage und zehn Seiten später kommt der Threadersteller wieder vorbei und sagt „Danke für eure Mühe, aber ich verwende nun die Lösung aus Beitrag #2, die ist für mich schnell genug“

Zitat von Amateurprofi:

Ich habe, nachdem ich die Fehler in deinem Code korrigiert habe, beide Funktionen laufen lassen, deine aus #28 und meine aus #19.
Als String, aus dem Zeichen entfernt werden sollen, habe ich den letzten Absatz deines Beitrages #28
und als String mit zu entfernenden Zeichen deinen Nick "Namenloser" benutzt.
Die Ergebnisse waren für mich nicht überraschend.

So habe ich getestet;

Dann könntest du ja wenigstens das Ergebnis posten.


EDIT:

Okay, ich habe jetzt zum Testen mal schnell FreePascal installiert. Testprogramm im Anhang. Hier sind die Ergebnisse:

Code:

[dev]$ ./test
Ergebnisse gleich
38388
55680
[dev]$ ./test
Ergebnisse gleich
44436
54428
[dev]$ ./test
Ergebnisse gleich
40326
45034
[dev]$ ./test
Ergebnisse gleich
38809
48323

Meine ist also nicht nur einfacher, sondern auch durchweg schneller. (CPU i7 4790K, 64 Bit)
Was sagst du nun?

Wenn ich String durch WideString ersetze und Char durch WideChar, ist es sogar noch ein bisschen krasser:

Code:

[dev]$ ./test
Ergebnisse gleich
43000
74935

[Dejan Vu]

Ich behaupte mal, das der Overhead bei der 'SET' Methode zu groß ist, um hier bei einem einmaligen Aufruf eine höhere Performance zu erzielen. Schließlich muss Speicher alloziiert, genullt und individuell gefüllt werden.

Wenn die Problemstellung beinhaltet, verschieden Strings von den immer gleichen Zeichen zu befreien, dann könnte es Sinn machen, das Bit-Array vorher (einmalig) zu initialisieren.

Allerdings ist bei mir (Delphi) das Ergebnis nicht reproduzierbar.

Code:

118764
24780

Es scheint also, der 'Sieger' ist abhängig vom Compiler.

[Amateurprofi]

Zitat von Namenloser:

Meine ist also nicht nur einfacher, sondern auch durchweg schneller. (CPU i7 4790K, 64 Bit)
Was sagst du nun?

Dazu sage ich, dass ich das nicht nachvollziehen kann.
Auf meinem Rechner (I7 2600K) sind die Ergebnisse so:

32 Bit Umgebung
Ergebnisse gleich
Min und Max CPU-Ticks für 1000 Durchläufe
T1 Min 141756 Max 358172
T2 Min 18144 Max 137786

64 Bit Umgebung
Ergebnisse gleich
Min und Max CPU-Ticks für 1000 Durchläufe
T1 Min 165112 Max 377076
T2 Min 19936 Max 146812

Ich habe die Test Prozedur noch etwas angepasst.
Beide Prozeduren laufen jeweils 1000 Mal und ich halte Min und Max CPU-Ticks fest.

Delphi-Quellcode:

So sieht die Test Prozedur jetzt aus:
PROCEDURE TMain.Test;
FUNCTION TimeStamp:Int64;
asm
   rdtsc
   {$IFDEF CPUX64}
   shl   rdx,32
   or    rax,rdx
   {$ENDIF}
end;
FUNCTION NStr(V:Int64; Len:Integer):String;
begin
   Str(V:Len,Result);
end;
const
   S='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.';
   R='Namenloser';
   Res:Array[Boolean] of String=('Ergebnisse verschieden','Ergebnisse gleich');
   Count=1000;
var
   T0,T1,T2,MinT1,MaxT1,MinT2,MaxT2:Int64; S1,S2,S3:String; I,Len:Integer;

begin
   MinT1:=High(Int64);
   MinT2:=High(Int64);
   MaxT1:=0;
   MaxT2:=0;
   for I:=1 to Count do begin
      T0:=TimeStamp;
      S1:=RemoveCharsFromString(S,R);
      T1:=TimeStamp;
      S2:=RemoveChars(S,R);
      T2:=TimeStamp;
      Dec(T2,T1);
      Dec(T1,T0);
      MinT1:=Min(MinT1,T1);
      MaxT1:=Max(MaxT1,T1);
      MinT2:=Min(MinT2,T2);
      MaxT2:=Max(MaxT2,T2);
   end;
   Len:=Trunc(Log10(Max(MaxT1,MaxT2)))+2;
   S3:={$IFDEF CPUX64}'64'{$ELSE}'32'{$ENDIF}+' Bit Umgebung'+#13#10+
       Res[S1=S2]+#13#10+
       'Min und Max CPU-Ticks für '+IntToStr(Count)+' Durchläufe'+#13#10+
       'T1 Min '+NStr(MinT1,Len)+'  Max '+NStr(MaxT1,Len)+#13#10+
       'T2 Min '+NStr(MinT2,Len)+'  Max '+NStr(MaxT2,Len);
   Clipboard.AsText:=S3;
   ShowMessage(S3);
end;

[Dejan Vu]

Das habe ich hier auch schon bemerkt.

Da kann man mal wieder sehen, das man sich widersprechen und doch recht haben kann.

Vom algorithmischen Aufwand ist die Version mit Pos vom Aufwand O(n*m), (n=Länge des Strings, m=Anzahl der zu eliminierenden Zeichen), die Version mit dem BitArray dagegen O(n).

PS: Wieso misst Du die Zeit so komisch? Ich würde das so machen:
Führe 'RemoveChars' 1000x aus und miss die Zeit, danach führe 'RemoveCharsFromString' 1000x aus. Teile beide Zeiten durch 1000. Damit hast Du auch die 18ms Ungenauigkeit vom 'TimeStamp' (falls es die gibt) bereinigt.