Schnellstes Entfernen von Chars aus einem String?

[himitsu]

Es gibt kein Set of Char WideChar.

Unit System.Character oder der Char-Helper.

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

[Uwe Raabe]

Zitat:

Zitat von himitsu (Beitrag 1295279)

Es gibt kein Set of Char WideChar.

Genau :!:

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

Zitat:

Zitat von PeterPanino (Beitrag 1295278)

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.

[DeddyH]

Zitat:

Zitat von Amateurprofi (Beitrag 1295273)

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.

Mal von der Ansi-Problematik abgesehen: worin besteht rein technisch der Unterschied?

[hathor]

http://alexandrecmachado.blogspot.de...or-delphi.html
http://www.alex7691.com/download/StrUtilsEx.pas
http://www.alex7691.com/download/FastStringReplace.zip
...
They ran a challenge for a faster StringReplace (Ansi StringReplace challenge), and the 'winner' was 14 times faster than the Delphi RTL:
http://fastcode.sourceforge.net/

[Amateurprofi]

Zitat:

Zitat von DeddyH (Beitrag 1295282)

Zitat:

Zitat von Amateurprofi (Beitrag 1295273)

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.

Mal von der Ansi-Problematik abgesehen: worin besteht rein technisch der Unterschied?

Wurde zwar schon in vorherigen Beiträgen beantwortet, aber trotzdem
Set hat max 256 Elemente.
Set kann keine WideChars.

Die "nur" 256 Elemente sollte bei diesem Anwendungsfall keine Rolle spielen.

Keine WideChars halte ich eher für kritisch, weil die Funktion ev. nicht das macht, was der Anwender erwartet.
Du kannst z.B. einem TSysCharSet mit Include(SetName,AnsiChar($221A)) ein Wurzelzeichen hinzufügen. nur ist es dann im Set eben nicht mehr das Wurzelzeichen sondern #$1A.
In einem Programm wird es ev. so sein, dass der Anwender die zu entfernenden Zeichen in ein Edit eingibt. Die Zeichen werden dann in ein Set übertragen.
Und der Anwender fragt sich dann was er falsch macht, wenn das Ergebnis nicht seinen Erwartungen entspricht.

[Zacherl]

Habe mal meine Funktion entsprechend angepasst:

Delphi-Quellcode:

function RemoveCharsFromString(const AStr, CharsToRemove: String): string;
var
  I, J: Integer;
  L: array[Char] of Boolean;
begin
  FillChar(L, SizeOf(L), #0);
  for I := 1 to Length(CharsToRemove) do
  begin
    L[CharsToRemove[I]] := true;
  end;
  SetLength(Result, Length(AStr));
  J := 1;
  for I := 1 to Length(AStr) do
  begin
    if (not L[AStr[I]]) then
    begin
      Result[J] := AStr[I];
      J := J + 1;
    end;
  end;
  SetLength(Result, J - 1);
end;

Ist sogar interessanterweise schneller als mein Ursprünglicher Code mit dem Set. Amateurprofis Funktion hat ähnliche Performance.

Code:

Zacherl (set): 641
Zacherl (lookup): 438
Amateurprofi: 500

[Namenloser]

Zitat:

Zitat von Popov (Beitrag 1295280)

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;

Delphi-Quellcode:

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

Delphi-Quellcode:

Array of Bool

bereits 65 Kilobyte. Würde man statt Bools einzelne Bits verwenden wie bei

Delphi-Quellcode:

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:

Zitat von Namenloser (Beitrag 1295288)

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

Delphi-Quellcode:

Array of Bool

bereits 65 Kilobyte. Würde man statt Bools einzelne Bits verwenden wie bei

Delphi-Quellcode:

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

Delphi-Quellcode:

SetLength(Result, AStr);

sollte eine Fehlermeldung kommen, dass man der Länge eines Strings keinen String zuweisen kann.

2) Bei

Delphi-Quellcode:

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:

Zitat von Amateurprofi (Beitrag 1295289)

@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:

Zitat von Amateurprofi (Beitrag 1295289)

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:

Zitat von Amateurprofi (Beitrag 1295289)

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