AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein Delphi Schnellstes Entfernen von Chars aus einem String?
Thema durchsuchen
Ansicht
Themen-Optionen

Schnellstes Entfernen von Chars aus einem String?

Ein Thema von PeterPanino · begonnen am 29. Mär 2015 · letzter Beitrag vom 14. Apr 2015
Antwort Antwort
Seite 1 von 2  1 2      
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.111 Beiträge
 
Delphi XE2 Professional
 
#1

AW: Schnellstes Entfernen von Chars aus einem String?

  Alt 31. Mär 2015, 00:07
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;
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#2

AW: Schnellstes Entfernen von Chars aus einem String?

  Alt 31. Mär 2015, 06:23
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.

Geändert von Dejan Vu (31. Mär 2015 um 06:39 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von TRomano
TRomano

Registriert seit: 24. Nov 2004
Ort: Düsseldorf
196 Beiträge
 
Delphi 11 Alexandria
 
#3

AW: Schnellstes Entfernen von Chars aus einem String?

  Alt 31. Mär 2015, 09:37
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
Thomas Forget
  Mit Zitat antworten Zitat
4dk2

Registriert seit: 4. Sep 2007
176 Beiträge
 
#4

AW: Schnellstes Entfernen von Chars aus einem String?

  Alt 31. Mär 2015, 09:41
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
  Mit Zitat antworten Zitat
4dk2

Registriert seit: 4. Sep 2007
176 Beiträge
 
#5

AW: Schnellstes Entfernen von Chars aus einem String?

  Alt 31. Mär 2015, 10:11
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;
  Mit Zitat antworten Zitat
Bjoerk

Registriert seit: 28. Feb 2011
Ort: Mannheim
1.384 Beiträge
 
Delphi 10.4 Sydney
 
#6

AW: Schnellstes Entfernen von Chars aus einem String?

  Alt 31. Mär 2015, 10:56
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;
  Mit Zitat antworten Zitat
Benutzerbild von DeddyH
DeddyH

Registriert seit: 17. Sep 2006
Ort: Barchfeld
27.666 Beiträge
 
Delphi 12 Athens
 
#7

AW: Schnellstes Entfernen von Chars aus einem String?

  Alt 31. Mär 2015, 11:26
Hat denn auch mal jemand getestet, wie lange die erste Schleife braucht, wenn Chars sehr groß ist (1 GB oder mehr)?
Detlef
"Ich habe Angst vor dem Tag, an dem die Technologie unsere menschlichen Interaktionen übertrumpft. Die Welt wird eine Generation von Idioten bekommen." (Albert Einstein)
Dieser Tag ist längst gekommen
  Mit Zitat antworten Zitat
mm1256

Registriert seit: 10. Feb 2014
Ort: Wackersdorf, Bayern
642 Beiträge
 
Delphi 10.1 Berlin Professional
 
#8

AW: Schnellstes Entfernen von Chars aus einem String?

  Alt 31. Mär 2015, 11:37
Ich hab alle Tests mit einer knapp 1 GB großen Textdatei gemacht. 3 Chars die ersetzt werden sollen, insgesamt 31805 Ersetzungen. Die Zeitunterschiede der letzten Versionen (einschließlich Zacherl + DeddyH's Versionen) sind marginal, d.h. Unterschiede sind zumindest unter Win8.1/64 nicht messbar. Die paar Ticks Differenz die ich noch messen kann, sind zudem mit normalen Messmethoden via TickCount nicht permanent nachvollziehbar (CPU-Cache usw.)

Ist also schon fast Geschmacksache, was man nimmt: Strings, PChars oder das Bool-Array.
Gruss Otto PS: Sorry wenn ich manchmal banale Fragen stelle. Ich bin Hobby-Programmierer und nicht zu faul die SuFu zu benutzen
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
44.555 Beiträge
 
Delphi 12 Athens
 
#9

AW: Schnellstes Entfernen von Chars aus einem String?

  Alt 31. Mär 2015, 12:09
Hat denn auch mal jemand getestet, wie lange die erste Schleife braucht, wenn Chars sehr groß ist (1 GB oder mehr)?
Dann sollte man sich überlegen das andersrum anzugehn, anstatt massig auszuschließen,
definiert man dort die paar erlauben Zeichen.
Ein Therapeut entspricht 1024 Gigapeut.
  Mit Zitat antworten Zitat
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.111 Beiträge
 
Delphi XE2 Professional
 
#10

AW: Schnellstes Entfernen von Chars aus einem String?

  Alt 31. Mär 2015, 16:12
Hat denn auch mal jemand getestet, wie lange die erste Schleife braucht, wenn Chars sehr groß ist (1 GB oder mehr)?
Lange braucht sie.
Aber hast du auch hinterfragt, wie lange "Pos" braucht, um X Mal ein Zeichen in einem 1GB-String NICHT zu finden?

Hab ich mal gemacht, aber mit "nur" 1 MB.

Delphi-Quellcode:
SetLength(R,1000000);
   for I:=1 to Length(R) do R[I]:=Chr(Random(26)+Ord('A'));
32 Bit Umgebung
Ergebnisse gleich
Min und Max CPU-Ticks für 1 Durchläufe
T1 Min 1529298460 Max 1529298460
T2 Min 6510004 Max 6510004


PS:
R ist hier nicht die in meiner Test-Prozedur deklarierte Konstante sondern eine Variable.
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2      

 

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 23:18 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz