StringReplace und doppelte Leerzeichen

[sakura]

Zitat von Jasocul:

Ok, OK, Ich gebe auf. War schon klar, dass das schneller ist, aber so eklatant? Das, ich 'abe nischt erwartet.

Beschäftige Dich mal ein wenig mit der String-Behandlung von Delphi. Immer wenn Du den via Delete/StringReplace änderst, wird mind. einmal neuer Speicher reserviert, kopiert, verschoben, etc. Das dauert einfach seine Zeit. Und genau da habe ich angesetzt. Ich habe im Voraus den max. benötigten Speicher reserviert, dann die entsprechenden Bytes kopiert und anschließend den überschüssigen Speicher wieder freigegeben. Daraus folgen nur noch zwei externe Aufrufe (zum OS), der Rest ist einfach Byteschubserei und alles in einem Durchlauf

......

[Jasocul]

Das war mir schon soweit klar (ehrlich). Deswegen war mir auch bewusst, dass es schneller sein wird. Meistens sind die zu verarbeitenden Strings allerdings nicht so groß, dass es ernsthaft was ausmacht. Ob man nun 0,02 oder 0,03 ms wartet, ist dann eigentlich egal.
Aber ich will mein Lösungen nicht großartig verteidigen. Sakuras Lösung ist definitiv besser und kommt auch in meine Sammlung. Vielleicht brauche ich das irgendwann einmal.

Ergänzung:
Eventuell kann es sinnvoll sein, gleich am Anfang der Funktion zu prüfen, ob das Leer-Zeichen überhaupt doppelt enthalten ist. Wenn man sonst einen langen String hat, wird der ja einmal komplett durchlaufen ohne, dass es erforderlich wäre.

[sakura]

Zitat von Jasocul:

Ob man nun 0,02 oder 0,03 ms wartet, ist dann eigentlich egal. Aber ich will mein Lösungen nicht großartig verteidigen.

Darfst Du ruhig. Es kommt immer auf das Einsatzziel an. Will man hin und wieder mal einen kurzen Text "putzen und polieren", dann reicht Deine Lösung vollends und ist leicht zu verstehen. Muss man größere Datenmengen bearbeiten oder auch sehr häufig kleinere mal "putzen", dann wird Optimierung interessant

......

[jbg]

Zitat von sakura:

Daraus folgen nur noch zwei externe Aufrufe (zum OS), der Rest ist einfach Byteschubserei und alles in einem Durchlauf

Wobei man deine Funktion auch noch mit ein paar kleineren Änderungen schneller machen kann.

Das fängt z.B. schon mal damit an, dass man sich das InStr[I] in eine lokale Char Variable zwischen speichern kann (die dann vom Compiler in ein Register geschoben wird). Des weiteren ist es schneller, wenn man InStr[I + 1] schreibt, und I von 0 bis Length-1 laufen lässt (am besten auch noch rückwärts, die die Verarbeitungsreihenfolge in diesem Code sowieso irrelevant ist, weil sowieso keine MultiByteChars beachtet werden [das ist jetzt keine Kritik]). Außerdem wird die Prüfung auf InStr[I] = #32 zuweimal durchgeführt, also einmal zu viel. Das Res[Cnt]:=InStr[I] ist auch nicht unbedingt das schnellste, weil somit in jedem Schleifendurchlauf UniqueString() von der Compiler-Magic aufgerufen wird. Die Hilfsvariable Res ist eigentlich auch nicht notwendig, da man gleich mit Result arbeiten kann und sich somit am Ende den LStrAsg() Aufruf (=Zuweisung) sparen kann.

Man sieht, dass man noch einiges herausholen kann, ohne gleich auf Hand-optimierten Assembler zurückgreifen zu müssen. Ob der Aufwand aber dem Nutzen entspricht ist dann eine andere Geschichte.

[marabu]

Mit Blick auf das Laufzeitverhalten könnte auch der Verzicht auf byteweises Schieben weitere Verbesserung bringen. Die Code-Zeile von Peter würde ich dann aber immer noch als Kommentar drüber schreiben, damit man beim Draufschauen erkennt, was der Code macht. Der Funktionsname alleine reicht da manchmal nicht - bei mir heißt diese Funktion z.B. Collapse().

Grüße vom marabu

[sakura]

SO, bevor ich Dich jetzt auseinander nehme zu meiner Verteidigung. Obige Lösung hatte ich blind in den Browser getippt

Zitat von jbg:

Wobei man deine Funktion auch noch mit ein paar kleineren Änderungen schneller machen kann.

Das war mir klar, daher habe ich mal Deine Aussage alle einzeln getestet. Es zeigt sich, dass man nie immer sagen sollte.

Zitat von jbg:

Das fängt z.B. schon mal damit an, dass man sich das InStr[I] in eine lokale Char Variable zwischen speichern kann (die dann vom Compiler in ein Register geschoben wird).

Der Gewinn lag hier bei unter 0,1%, hätte ich mehr erwartet.

Zitat von jbg:

Des weiteren ist es schneller, wenn man InStr[I + 1] schreibt, und I von 0 bis Length-1 laufen lässt

Macht gar keinen Unterschied. Einfacher Grund, intern wird immer noch rückwärts gezählt und eine zweite Variable für meine Aufrufe genutzt

Zitat von jbg:

(am besten auch noch rückwärts, die die Verarbeitungsreihenfolge in diesem Code sowieso irrelevant ist, weil sowieso keine MultiByteChars beachtet werden [das ist jetzt keine Kritik]).

Dazu war ich jetzt zu faul, auch habe ich keine schnelle Lösung dafür gefunden...

Zitat von jbg:

Außerdem wird die Prüfung auf InStr[I] = #32 zuweimal durchgeführt, also einmal zu viel.

Hier wirst Du überrascht sein, eine einmalige Prüfung und das Speichern in einer weiteren Variable (gleiche kann ja nicht genutzt werden, da der alte Wert noch wichtig wird), verbraucht ca. 7% mehr Rechenzeit. Also besser wie es jetzt ist

Zitat von jbg:

Das Res[Cnt]:=InStr[I] ist auch nicht unbedingt das schnellste,

Stimmt, in der neuen Lösung auf Pointer gewechselt

Zitat von jbg:

Die Hilfsvariable Res ist eigentlich auch nicht notwendig, da man gleich mit Result arbeiten kann und sich somit am Ende den LStrAsg() Aufruf (=Zuweisung) sparen kann.

Dadurch wird allerdings das EAX Register blockiert, welches evtl. durch den Compiler anders für Optimierungen genutzt werden könnte. Es macht hier keinen Unterschied, ist i.A. aber nicht zu empfehlen. Result sollte nach Möglichkeit immer erst am Ende direkt angesprochen werden.

Zitat von jbg:

Man sieht, dass man noch einiges herausholen kann, ohne gleich auf Hand-optimierten Assembler zurückgreifen zu müssen.

Oh Gott, dazu fehlt mir jetzt die Zeit. Aber das Rumspielen war schon einmal interessant, und hat noch einmal ca. 60% Performancegewinn gebracht. Aber das reicht mir jetzt, wer will, der darf weiter machen

Delphi-Quellcode:

function RemoveDblSpaces2(const InStr: string): string;
var
  LastIsSpace, IsSpace: Boolean;
  I: Integer;
  Src, Dst: PChar;
  Res: string;
begin
  SetLength(Res, Length(InStr));
  LastIsSpace := False;
  Src := @InStr[1];
  Dec(Src);
  Dst := @Res[1];
  Dec(Dst);
  for I := 0 to Length(InStr) - 1 do
  begin
    Inc(Src);
    IsSpace := Src^ = #32;
    if LastIsSpace and IsSpace then
      Continue;
    LastIsSpace := IsSpace;
    Inc(Dst);
    Dst^ := Src^;
  end;
  SetLength(Res, (Integer(Dst) - Integer(@Res[1])));
  Result := Res;
end;

......

[DerDan]

Ich hab mich auch mal versucht:

meine Version ist 15 bis 25% schneller als die letzte von sakura!

Delphi-Quellcode:

function RemoveDblSpaces3(InStr: string): string;
var
  Src, Dst: PChar;
begin
  InStr := InStr + #0;
  // I := 0;
  SetLength(Result, Length(InStr));
  Src := @InStr[1];
  Dst := @Result[1];
  while (Src^ > #0) do
  begin
    while (Src^ <> #32) and (Src^ <> #0) do
    begin
      Dst^ := Src^;
      inc (Src);
      inc (Dst);
    end;
    if Src^ = #32 then
    begin
      Dst^ := Src^;
      inc (Src);
      inc (Dst);
      while (Src^ = #32) do
      begin
        inc (Src);
      end;
    end;
  end;
  SetLength(Result, (Integer(Dst) - Integer(@Result[1])));
end;

Bei meinen Versuchen hat das zwichenspeichern der Result Variablen in einen eigenen String
laufzeit gekostet.
Wie man sieht kommt meine Version ohne Bool Variablen aus, was sicher auch dazu beiträgt das es schnell wird


mfg

Der Dan

[jbg]

Zitat von sakura:

Zitat von jbg:

Die Hilfsvariable Res ist eigentlich auch nicht notwendig, da man gleich mit Result arbeiten kann und sich somit am Ende den LStrAsg() Aufruf (=Zuweisung) sparen kann.

Dadurch wird allerdings das EAX Register blockiert, welches evtl. durch den Compiler anders für Optimierungen genutzt werden könnte. Es macht hier keinen Unterschied, ist i.A. aber nicht zu empfehlen. Result sollte nach Möglichkeit immer erst am Ende direkt angesprochen werden.

Da Result hierbei ein String ist, besteht da nicht das Problem mit dem blockierten EAX Register. Ohne die Hilfsvariable Res spart man sich zudem einen vom Compiler eingefügten try/finally-Block.

Folgende Funktion macht maximal 2 Speicherzugriffe pro Schleifendurchlauf (BDS 2006)

Delphi-Quellcode:

function RemoveDblSpaces3(const InStr: string): string;
type
  IntPtr = Integer;
var
  LastIsSpace: Boolean;
  IsSpace: Boolean;
  Ch: Char;
  PResult, PInStr: PChar;
begin
  if InStr = '' then
  begin
    Result := '';
    Exit;
  end;
  SetLength(Result, Length(InStr));

  PInStr := Pointer(InStr);
  PResult := Pointer(Result);

  LastIsSpace := False;
  while True do
  begin
    Ch := PInStr^;
    if Ch = #0 then
      Break;
    IsSpace := Ch = #32;
    if not (IsSpace and LastIsSpace) then
    begin
      PResult^ := Ch;
      Inc(PResult);
    end;
    LastIsSpace := IsSpace;
    Inc(PInStr);
  end;
  SetLength(Result, IntPtr(PResult) - IntPtr(Result));
end;

Kleine Statistik (darf natürlich jeder selbst nachprüfen):

Code:

Jasocul   : 100.00%  ( while Pos('  ') <> 0 ... )
sakura (1):   2.69%
sakura (2):   1.76%
jbg:      :   1.22%

[3_of_8]

Ihr streitet euch jetzt nicht ernsthaft um ein paar ms Prozessorzeit, oder?

[DerDan]

Hab getested:

Code:

Zeit1( 5643,38 ms)/Zeit2 13886,51% (
Zeit2(   40,64 ms)/Zeit2   100,00% (sakura)
Zeit3(   33,04 ms)/Zeit2    81,31% (DerDan)
Zeit4(   34,33 ms)/Zeit2    84,47% (jbg)

Eigendlich gehts nicht um ein paar ms sonden um % und wie du siehst rentiert sich das!

Überleg mal die Daten w#ren größer und die angaben nicht ms sondern sec


dann müstes du im ersten Fall 5643 sec auf ein ergebnis warten


mfg

DerDan