Schnellstes Entfernen von Chars aus einem String?

[Amateurprofi]

Zitat von Dejan Vu:

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

[Amateurprofi]

Zitat von DeddyH:

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.

[Amateurprofi]

Zitat von himitsu:

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.

[himitsu]

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

[Harry Stahl]

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

[himitsu]

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.

[Dejan Vu]

Zitat von Amateurprofi:

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.

[Harry Stahl]

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

[himitsu]

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.

[Namenloser]

Zitat von 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

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)