Schnellstes Entfernen von Chars aus einem String?

[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 von Amateurprofi:

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 von Daniel:

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

Vielleicht eine neue Rubrik hier im Forum? Kata

[Neutral General]

Zitat von Uwe Raabe:

Zitat von Daniel:

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

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

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