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 6 von 7   « Erste     456 7      
Amateurprofi

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

AW: Schnellstes Entfernen von Chars aus einem String?

  Alt 31. Mär 2015, 16:48
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.
N mal laufen lassen und dann die Zeit durch N teilen heißt, dass alles, was das System in der Zeit macht, in die Zeitmessung einfließt.
Genau das möchte ich mit den Einzelmessungen ja vermeiden.
Die Annahme ist, dass zumindest bei einem der Durchläufe keine Interrupts stattfinden.

"TimeStamp" braucht minimal so um die 25 CPU-Ticks (nicht ms), aber da kann man auch Überraschungen erleben.
Versuch mal
Delphi-Quellcode:
   MinT1:=High(Int64);
   MaxT1:=0;
   for I:=1 to 1000000 do begin
      T0:=TimeStamp;
      T1:=TimeStamp;
      Dec(T1,T0);
      MinT1:=Min(MinT1,T1);
      MaxT1:=Max(MaxT1,T1);
   end;
   ShowMessage(IntToStr(MinT1)+#13+IntToStr(MaxT1));
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
Amateurprofi

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

AW: Schnellstes Entfernen von Chars aus einem String?

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

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

AW: Schnellstes Entfernen von Chars aus einem String?

  Alt 31. Mär 2015, 17:59
Hier ging es ja um Geschwindigkeit und da ist Stack nunmal schneller.
Ja, es entfällt AllocMem und FreeMem, aber dafür hast du zusätzlich FillChar.
AllocMem verwendet zum Füllen des Memories mit Nullen eine ähnliche Methode wie FillChar, allerdings ohne den Overhead den FillChar nun einmal hat.
Unterm Strich dürfte das ein Nullsummenspiel sein.
Kannst ja mal testen.
Meine Messungen bei 1 Mio Durchläufen ergaben, das AllocMem+FreeMem geringfügig schneller war, wenn ich die Min-Zeiten ansah, dafür, auch das sei gesagt, deutlich mehr, bei dem Max-Zeiten.
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

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

AW: Schnellstes Entfernen von Chars aus einem String?

  Alt 31. Mär 2015, 18:03
Ich mach es teils so und teils so.
Aber statt Alloc-Zeugs verwende ich lieber dynamische Arrays, mit automatischer Freigabe.

entweder statisch oder dynamisch und selten manuell
Neuste Erkenntnis:
Seit Pos einen dritten Parameter hat,
wird PoSex im Delphi viel seltener praktiziert.
  Mit Zitat antworten Zitat
Benutzerbild von Harry Stahl
Harry Stahl

Registriert seit: 2. Apr 2004
Ort: Bonn
2.534 Beiträge
 
Delphi 11 Alexandria
 
#55

AW: Schnellstes Entfernen von Chars aus einem String?

  Alt 31. Mär 2015, 18:27
Das müsste man noch mal wie untenstehend etwas beschleunigen können. Wie viel das schneller ist, hängt davon ab, ob der Text zu ersetzende Zeichen enthält und wenn ja, ab wann.

In der vorherigen Variante erfolgen IMMER Allokationen von Speicherbereich und zuweisende Speicheroperationen, auch wenn der Text gar keine zu ersetzende Zeichen enthält (eben durch das charweise kopieren).

Hier erfolgt das kopieren nur dann, wenn zu ersetzenden Zeichen vorhanden sind und nur ab der Stelle, wo das erste zu ersetzende Zeichen vorliegt. Liegt kein zu ersetzendes Zeichen vor, steigt die Funktion schon bei [1] aus und liefert den unveränderten String als Ergebnis zurück. Wenn man also viele Aufrufe dieser Funktion im Programmablauf hat und oft gar keine Ersetzungen vorgenommen werden müssen, dann sollte die Sache noch mal spürbar beschleunigt werden können.

Delphi-Quellcode:
function RemoveCharsEx(const S, Chars: string): string; // Chars CaseSensitive;
var
   I, Index: integer;
   Skip: array[Char] of boolean;
   StartPos, LastPos: Integer;
begin
   FillChar(Skip[#0], Length(Skip) * SizeOf(Skip[#0]), 0);

   for I := 1 to Length(Chars) do
     Skip[Chars[I]] := true;

   Result := S; // Ergebnis vorbelegen
   StartPos := -1;

   for i := 1 to length (s) do // Prüfen, ob Text zu ersetzende Zeichen enthält
     if skip[S[i]] then begin
       StartPos := i;
       LastPos := i;
       break;
     end;

   if StartPos = -1 then exit; // [1] Text enthielt keine zu ersetzenden Zeichen

   for I := StartPos to Length(S) do
     if not Skip[S[I]] then
     begin
       Result[LastPos] := S[I];
       Inc(LastPos);
     end;

   SetLength(Result, LastPos-1);
end;
Zum Aspekt der Surrogates hat himitsu ja schon einen Hinweis gegeben (seltsamerweise hat es bei einem Test auch mit Surrogates funktioniert, aber das war wohl nur Zufall).
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

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

AW: Schnellstes Entfernen von Chars aus einem String?

  Alt 31. Mär 2015, 19:02
Ja, wenn man einen Surrogare entfernt und nur der vorkommt, dann klappt es, aber versuch mal von zwei Aufeinanderfolgenden nur Einen zu entfernen, ohne den Anderen zu schrotten.
Bei einer Einzelzeichenbearbeitung (Char) praktisch unmöglich.
Neuste Erkenntnis:
Seit Pos einen dritten Parameter hat,
wird PoSex im Delphi viel seltener praktiziert.
  Mit Zitat antworten Zitat
Dejan Vu
(Gast)

n/a Beiträge
 
#57

AW: Schnellstes Entfernen von Chars aus einem String?

  Alt 31. Mär 2015, 20:03
N mal laufen lassen und dann die Zeit durch N teilen heißt, dass alles, was das System in der Zeit macht, in die Zeitmessung einfließt.
Ich sorge dafür, das ein Durchlauf ca. 1 Sekunde braucht. Das Messe ich 10x und dann reicht mir das. Wenn ich das für jeden Kandidaten direkt hintereinander mache, dann bekomme ich -bis auf das Grundrauschen- reproduzierbare Ergebnisse, und zwar auf +/- 5% genau. Das reicht mir vollkommen aus. Genauer kann man das eh nicht hinbekommen.

Daher die Frage. Aber so muss ich das auch mal probieren.
  Mit Zitat antworten Zitat
Benutzerbild von Harry Stahl
Harry Stahl

Registriert seit: 2. Apr 2004
Ort: Bonn
2.534 Beiträge
 
Delphi 11 Alexandria
 
#58

AW: Schnellstes Entfernen von Chars aus einem String?

  Alt 31. Mär 2015, 21:14
@himitsu: Ich bin im Prinzip ja Deiner Meinung.

Allerdings stimmt der Praxis-Test damit nicht überein: Aus dem anliegenden Screenshot ist erkennbar, dass im zu ersetzenden Text am Anfang direkt zwei Surrogates-Chars nebeneinander liegen, nach Aufruf der Remove-Funktion wird nur das eine ersetzt, das andere (und der sonstige Text) bleibt (unbeschädigt) erhalten. Warum, ist mir selber momentan ein Rätsel.

Edit: Eigentlich bin ich davon ausgegangen, dass in dem Falle, wo Surrogates beteiligt sind, beim Durchlaufen des zu ersetzenden Strings für jede Stelle (IsSurrogate[i]) aufgerufen werden müsste und dann eben bei Bejahung die Kopieraktion mit zwei UTF-16-Chars zu erfolgen hätte.
Miniaturansicht angehängter Grafiken
unicode.jpg  

Geändert von Harry Stahl (31. Mär 2015 um 21:20 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

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

AW: Schnellstes Entfernen von Chars aus einem String?

  Alt 31. Mär 2015, 21:33
Wenn man die WideChar einzeln behandelt, dann geht in diesem Prozess die Verbindung zwischen High-Surrogate und Low-Surrogate verloren.

1234AB5AC6789

Wenn ich nun AB279 entferne, dann müsste eigentlich 1345AC68 [B] raus kommen,
aber wenn man einzeln A B 2 7 9 entfernt, dann wird auch ein Teil (A) des zweiten Surrogates entfernt.
Und 1345C68 ist nunmal falsch.

Wenn man "Texte" zusammenhängend verarbeitet (z.B. Pos), dann gibt es eigentlich nie ein Problem, da dort die Verbindung bestehen bleibt,
aber bei dieser Art der getrennten Verarbeitung war's das halt.

Das ist auch der Grund, warum man für High- und Low-Surrogate nicht den selben Bereich genutzt hat, auch wenn das vom Speicherverbrauch her schlechter ist, da der Wert doppelt soviel Werte in einem Char blockiert.
Allergings ist so eine implizite Trennung und Erkennung an nur einem einzelnen Char möglich, um was es sich dabei haandelt und ob der zweite Teil davor oder dahinter liegt.
Neuste Erkenntnis:
Seit Pos einen dritten Parameter hat,
wird PoSex im Delphi viel seltener praktiziert.

Geändert von himitsu (31. Mär 2015 um 21:38 Uhr)
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#60

AW: Schnellstes Entfernen von Chars aus einem String?

  Alt 1. Apr 2015, 00:42
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
Min/Max find ich jetzt nicht so glücklich, da kriegst du gerade die größten Schwankungen. Median oder Durchschnitt wären aussagekräftiger.

Wie dem auch sei, ich kann mir den Unterschied nur so erklären, dass entweder Delphis Pos-Routine wesentlich langsamer ist als das Freepascal-Äquivalent oder erhebliche Unterschiede zwischen den CPUs bestehen.

Probier es doch mal mit einer anders definierten Pos-Funktion:
Delphi-Quellcode:
function Pos(const Needle: MyChar; const Haystack: MyString): integer; inline;
var
  i: integer;
begin
  for i := 1 to length(Haystack) do
    if Haystack[i] = Needle then
    begin
      Result := i;
      exit;
    end;
  Result := 0;
end;
Bei mir ändert sich dadurch nicht wirklich was:
Code:
[dev]$ ./test
Ergebnisse gleich
35883
69671
[dev]$ ./test
Ergebnisse gleich
44440
85332
[dev]$ ./test
Ergebnisse gleich
34680
71640
Allerdings interessanterweise nur im WideChar-Fall. Im 8-Bit-Fall ist meine Routine damit nun leicht langsamer als deine. Ich vermute daher, dass Freepascals Pos-Routine im 8-Bit-Fall irgendwelche SSE-Instructions verwendet.

Edit: Okay, letzteres lag wohl nur an der Optimierungsstufe:

AnsiString, ohne eigene Pos-Funktion:
fpc test.pas
Ergebnisse gleich
38464
46625
fpc -O3 test.pas
Ergebnisse gleich
36628
40034

AnsiString, mit eigener Pos-Funktion:

fpc test.pas
Ergebnisse gleich
58889
46354

fpc -O3 test.pas
Ergebnisse gleich
39852
42474

WideString, ohne eigene Pos-Funktion:
fpc test.pas
Ergebnisse gleich
41160
73345
fpc -O3 test.pas
Ergebnisse gleich
39369
67631

WideString, mit eigener Pos-Funktion:

fpc test.pas
Ergebnisse gleich
62403
73024
fpc -O3 test.pas
Ergebnisse gleich
34298
64443


(Sorry, bin zu faul, herauszufinden, wie man hier eine Tabelle formatiert)

Geändert von Namenloser ( 1. Apr 2015 um 01:27 Uhr)
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 6 von 7   « Erste     456 7      

 

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 22:22 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz