Schnellstes Entfernen von Chars aus einem String?

[PeterPanino]

Hallo! Was ist die SCHNELLSTE Methode, um aus einem String alle Zeichen eines anderen Strings zu entfernen? Also z.B.:

Delphi-Quellcode:

function RemoveCharsFromString(const AStr, CharsToRemove: string): string;

[mkinzler]

Ich habe keinen Vergleich, aber ich würde mal Testen, ob StringReplace() schnell genug ist.

[Popov]

StringReplace wurde immer ein Zeichen ersetzen. Man müsste es somit für jeden Zeichen wiederholen (was auch keine Arbeit wäre).

Ansonsten aus dem Kopf:

Delphi-Quellcode:

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

[mkinzler]

Nein, man kann der Funktion auch Sagen, dass sie alle Vorkommnisse erseten soll.
(rfReplaceAll in Flags)

[mm1256]

Zitat:

Zitat von Popov (Beitrag 1295256)

StringReplace wurde immer ein Zeichen ersetzen. Man müsste es somit für jeden Zeichen wiederholen (was auch keine Arbeit wäre).

Ansonsten aus dem Kopf:

Delphi-Quellcode:

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

Müsste man mal testen, was schneller wäre...auch aus dem Kopf und ungetestet:

Delphi-Quellcode:

function RemoveCharsFromString(const AStr, CharsToRemove: string): string;
var
  i,p: integer;
  ch: char;
begin
  Result := AStr;
  for i := 1 to Length(CharsToRemove) do begin
    p := Pos(CharsToRemove[i],Result);
    if p > 0 then
    repeat
      Delete(Result,p,1);
      p := Pos(CharsToRemove[i],Result);
    until P = 0;
  end;
end;

[Zacherl]

Zitat:

Zitat von mkinzler (Beitrag 1295257)

Nein, man kann der Funktion auch Sagen, dass sie alle Vorkommnisse erseten soll.
(rfReplaceAll in Flags)

Ja, alle Vorkommen des Such-Strings. Der Threadersteller will aber glaube ich jedes Zeichen im CharToRemove String entfernen.

[Popov]

So wie ich den TE verstanden habe hat er z. B. den Text "Hallo große Welt!" und möchte nun alle l und e entfernen, so das "Hao groß Wt!" rauskommt. Ich mag mich irren, denn ich hab StringReplace schon lange nicht genutzt. Also mit rfReplaceAll werden alle l in einem Vorgang entfert, aber nicht auch e. Für e müsste man einen zweiten Durchlauf machen. In etwa so:

Delphi-Quellcode:

function RemoveCharsFromString(const AStr, CharsToRemove: string): string;
var
  i: Integer;
begin
  Result := AStr;
  for i := 1 to Length(CharsToRemove) do
    Result := StringReplace(Result, CharsToRemove[i], '', [rfReplaceAll, rfIgnoreCase]);
end;

(dieses Mal nicht aus dem Kopf ;) )

[mkinzler]

Wenn man einen höheren IQ als ich hat, könnte man das aus der Frage herauslesen, aber "einfach gestrickte Typen" wie ich, haben den feinen Kniff glatt überlesen. :oops:

[Zacherl]

Erster Versuch, der DEUTLICH schneller ist, als alle anderen bisher geposteten Lösungen:

Delphi-Quellcode:

function RemoveCharsFromString(const AStr: String; CharsToRemove: TSysCharSet): string;
var
  I, J: Integer;
begin
  SetLength(Result, Length(AStr));
  J := 1;
  for I := 1 to Length(AStr) do
  begin
    if (not (AStr[I] in CharsToRemove)) then
    begin
      Result[J] := AStr[I];
      J := J + 1;
    end;
  end;
  SetLength(Result, J - 1);
end;

Getestet mit einem 256KiB großen Zufallsstring (bestehend aus 'a'..'z') und CharsToRemove mit 'a' und 'z':

Code:

mm1256  :   656ms
Popov    : 1359ms
Zacherl1:     0ms

[Neumann]

Warum so kompliziert, einfach mal die Beschreibung von SysUtils.StringReplace lesen

So wie ich das verstehe, ersetzt diese einen Teilstring durch einen neuen, nicht einzelne Zeichen.

Also braucht man nur diese aufrufen mit RepaceAll und fertig. Wenn der Strig nicht Megabites gross ist sehe ich auch keine Notwendigkeit, über die Geschwindigkeit nachzudenken.

[BadenPower]

Zitat:

Zitat von Neumann (Beitrag 1295263)

Warum so kompliziert, einfach mal die Beschreibung von SysUtils.StringReplace lesen

So wie ich das verstehe, ersetzt diese einen Teilstring durch einen neuen, nicht einzelne Zeichen.

Er will aber nicht nur Teilstrings ersetzten, sondern in StringA jedes Zeichen, welches in StringB vorkommt.

[DeddyH]

Wie schnell ist denn diese Variante im Vergleich?

Delphi-Quellcode:

function RemoveCharsFromString(const AStr: string; CharsToRemove: TSysCharSet): string;
var
  PSrc, PDest, PCurrent: PChar;
begin
  SetLength(Result, Length(AStr));
  PSrc := PChar(AStr);
  PDest := PChar(Result);
  PCurrent := PDest;
  while PSrc^ <> #0 do
    begin
      {$IFDEF UNICODE}
      if not CharInSet(PSrc^, CharsToRemove) then
      {$ELSE}
      if not(PSrc^ in CharsToRemove) then
      {$ENDIF}
        begin
          PCurrent^ := PSrc^;
          PCurrent := CharNext(PCurrent);
        end;
      PSrc := CharNext(PSrc);
    end;
  SetString(Result, PDest, PCurrent - PDest);
end;

[mm1256]

Zitat:

Zitat von Zacherl (Beitrag 1295262)

Getestet mit einem 256KiB großen Zufallsstring (bestehend aus 'a'..'z') und CharsToRemove mit 'a' und 'z':

Code:

mm1256  :   656ms
Popov    : 1359ms
Zacherl1:     0ms

Soeben auch verglichen...es kommt aber in Zacherl's Ergebnis nicht das selbe raus. Suche noch, woran es liegt

EDIT: So funktionierts tatsächlich am schnellsten:

Delphi-Quellcode:

function RemoveCharsFromString(const AStr, CharsToRemove: string): string;
var
  i: Integer;
  S: set of Char;
begin
  s := [];
  for i := 1 to Length(CharsToRemove)
  do S := S + [CharsToRemove[i]];
  Result := '';
  for i := 1 to Length(AStr) do
  if not CharInSet(AStr[i],S)
  then Result := Result + AStr[i];
end;

Und das Ergebnis stimmt auch ;-)

EDIT-2

ooops...Deddy's Variante ist noch schneller. 1 MB Text mit 3 Ersetzungen dauert nur ein paar Ticks....geil ;-)

[Zacherl]

Hatte noch nen SetLength am Ende vergessen und mir ist wohl ein -1 bei der Schleife reingerutscht. So funktioniert es und ist sogar noch schneller als DeddyHs Version:

Delphi-Quellcode:

function RemoveCharsFromString(const AStr: String; CharsToRemove: TSysCharSet): string;
var
  I, J: Integer;
begin
  SetLength(Result, Length(AStr));
  J := 1;
  for I := 1 to Length(AStr) do
  begin
    if (not (AStr[I] in CharsToRemove)) then
    begin
      Result[J] := AStr[I];
      J := J + 1;
    end;
  end;
  SetLength(Result, J - 1);
end;

100MiB String mit 2 Ersetzungen:

Code:

Zacherl : 641
DeddyH  : 1578

[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

Delphi-Quellcode:

TSysCharSet

funktioniert allerdings nur für AnsiChar (

Delphi-Quellcode:

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:

Zitat von Amateurprofi (Beitrag 1295273)

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.

[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

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

[Daniel]

Zitat:

Zitat von Amateurprofi (Beitrag 1295289)

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.

Und auch wenn es noch so in den Fingern juckt, sollten wir in der Lage sein, eine skizzierte Lösung als solche zu erkennen - und nicht vergessen, dass wir hier alle an einem Strang ziehen: Nämlich eine performante Lösung für ein Problem zu finden. Dieser Thread hat fast sportliche Ansätze angenommen, was ich grundsätzlich gut finde. Vielleicht sollten wir häufiger an solchen kleinen softwaretechnischen Knochen knabbern.

[Uwe Raabe]

Zitat:

Zitat von Daniel (Beitrag 1295296)

Vielleicht sollten wir häufiger an solchen kleinen softwaretechnischen Knochen knabbern.

:thumb:

Vielleicht eine neue Rubrik hier im Forum? Kata

[Neutral General]

Zitat:

Zitat von Uwe Raabe (Beitrag 1295303)

Zitat:

Zitat von Daniel (Beitrag 1295296)

Vielleicht sollten wir häufiger an solchen kleinen softwaretechnischen Knochen knabbern.

:thumb:

Vielleicht eine neue Rubrik hier im Forum? Kata

Bin dafür :) Sowas macht immer Spaß und was am Ende am besten klappt ist meistens überraschend!

[Amateurprofi]

Zitat:

Zitat von Namenloser (Beitrag 1295290)

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.

[TRomano]

Zeitmessungen sind immer so eine Sache ... wenn ich messe, dann fahre ich erst einmal die CPU hoch (mit verschiedenen sinnfreien Berechnungen), damit ich aus eventuellen Stromspar-Modi´s rauskomme, dann wird mehrmals RDTSC aufgerufen und die Differenz in Ticks gemittlelt (zwischen den RDTSC), damit man dieses später vom Ergebnis abziehen kann. Das verbessert die Messergebnisse, genau wie das Hochziehen der Prozess-Priorität, damit nicht irgendwelche Windows-Events das Ergebnis verfälschen.
Genaueres kann man auch im MASM32-Forum lesen, weil die dort immer wieder genaue Messungen zu verschiedenen Algorithmen durchführen.

Gruß Thomas

[4dk2]

Interessant auch:
Bei euern letzten Versuchen ist die Geschwindigkeit von Delphi 7 zu XE3 auch nochmal anders.
Die RemoveCharsFromString() Variante wird mit XE3 schneller gegenüber D7,
Die Zweite variante RemoveChars() wird mit XE3 deutlich langsamer als bei D7.

TGESx = durchschnitt aus 1000x

XE3:

Code:

TGES1: 111026,18900
TGES2: 47264,11200

D7:

Code:

TGES1: 347124,48100
TGES2: 24214,50800

[4dk2]

Noch eine Anmerkung,

Amateurprofi, habe deine Routine noch ein bisl verbessert,
Das Verzichten auf die Zuweisung von C, bringt nochmal ca 13% mehr Geschwindigkeit bei mir.

Delphi-Quellcode:

function StringTest(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[S[I]] then begin
         Inc(J);
         Result[J]:=S[I];
      end;
   end;
   SetLength(Result,J);
   FreeMem(P);
end;

[Bjoerk]

Japp. Das dürfte auch der Minimale Zeitunterschied zu Zacherl gewesen sein. Wenn man sprechende Variablenbezeichner einführt, sieht man man auch daß es sich um einen BoyerMoore für Substrings der Länge 1 handelt. Habs in meine Sammlung aufgenommen (hab öfters mal ein BlankReplace und dergleichen). Thanx to Zacherl und Amateurprofi. :)

Delphi-Quellcode:

class function TStrUtils.RemoveChars(const S, Chars: string): string; // Chars CaseSensitive;
var
  I, Index: integer;
  Skip: array[Char] of boolean;
begin
  FillChar(Skip[#0], Length(Skip) * SizeOf(Skip[#0]), 0);
  for I := 1 to Length(Chars) do
    Skip[Chars[I]] := true;
  SetLength(Result, Length(S));
  Index := 0;
  for I := 1 to Length(S) do
    if not Skip[S[I]] then
    begin
      Inc(Index);
      Result[Index] := S[I];
    end;
  SetLength(Result, Index);
end;