StringReplace und doppelte Leerzeichen

[Pichel]

Hi...

Irgendwie ein absolut blödes Problem.

ich möchte in einem String keine doppelten Leerzeichen mehr haben.
Hierfür jetzt mal die Funktion StringReplace getestet.

Was bei beliebigen Zeichen funktioniert bringt mich hier fast zum Wahnsinn

Delphi-Quellcode:

s := StringReplace(s, '  ', ' ', [rfReplaceAll,rfIgnoreCase]);

funktioniert nicht und

Delphi-Quellcode:

s := StringReplace(s, #32#32, #32, [rfReplaceAll,rfIgnoreCase]);

auch nicht und

Delphi-Quellcode:

s := AnsiReplaceText(s, #32#32, #32);

bringt auch nicht den erwünschten Erfolg.

Any hint?

[mirage228]

Hi,

du könntest eventuell mit regulären Ausdrücken arbeiten.

Dann z.B. so einen Ausdruck wie (\s){2,} (oder ggf. direkt über die Angabe des Charakter-Codes, da \s ggf. auch andere Zeichen matched, soweit ich weiss) der nach mindestens 2 Leerzeichen matched suchen und das ganze Ergebnis mit einem Leerzeichen ersetzen.

mfG
mirage228

[sakura]

Zitat:

Zitat von Pichel

ich möchte in einem String keine doppelten Leerzeichen mehr haben.
Hierfür jetzt mal die Funktion StringReplace getestet.

Das funktioniert, wie auch bei anderen Zeichen mit StringReplace nicht. Wenn Du aus 'aa' einfach 'a' machen willst, dann wird aus dem String baac -> bac, und aus baaaac -> baac, ist bei Leerzeichen nicht anders.

Da musst Du Dir selbst eine kleine Funktion schreiben. Z.B.:

Delphi-Quellcode:

function RemoveDblSpaces(const InStr: string): string;
var
  LastIsSpace: Boolean;
  I, Cnt: Integer;
  Res: string;
begin
  SetLength(Res, Length(InStr));
  Cnt := 0;
  LastIsSpace := False;
  for I := 1 to Length(InStr) do
  begin
    if LastIsSpace and (InStr[I] = #32) then
      Continue;
    LastIsSpace := InStr[I] = #32;
    Inc(Cnt);
    Res[Cnt] := InStr[I];
  end;
  SetLength(Res, Cnt);
  Result := Res;
end;

...:cat:...

[Jasocul]

Alternative Lösung:

Delphi-Quellcode:

while Pos('  ', DeinString) > 0 do
  Delete(DeinString, Pos('  ', DeinString), 1);

oder

Delphi-Quellcode:

while Pos('  ', DeinString) > 0 do
  DeinString := StringReplace(DeinString, '  ', ' ', [rfReplaceAll]);

Kommen die doppelten Leerzeichen häufig in einem String vor, dann dürfte die zweite Variante schneller sein.

[sakura]

Zitat:

Zitat von Jasocul

Alternative Lösung:

Die Lösung funktioniert und ist schön kurz, aber hast Du Dir Gedanken über die Geschwindigkeit gemacht :shock:

...:cat:...

[Jasocul]

Zitat:

Zitat von sakura

Die Lösung funktioniert und ist schön kurz, aber hast Du Dir Gedanken über die Geschwindigkeit gemacht

Ich habe zumindest mit dieser Frage gerechnet. :zwinker:
Käme auf einen Versuch an. Vielleicht hat Pichel ja Lust, die Varianten zu vergleichen?

[sakura]

Zitat:

Zitat von Jasocul

Vielleicht hat Pichel ja Lust, die Varianten zu vergleichen?

Vielleicht, vielleicht aber auch nicht :mrgreen: Hier mal der TestCode (2 Labels auf einer Form)

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
const
  x: array[0..27] of string = (
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
    'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
    #32, #32#32
  );
  TEST = 1000;
var
  Start, Stop, Freq: Int64;
  I: Integer;
  Source, Work, Dest: string;
begin
  Source := '';
  for I := 0 to 5000 do
    Source := Source + x[Random(Length(x))];

  QueryPerformanceFrequency(Freq);

  QueryPerformanceCounter(Start);
  for I := 1 to TEST do
  begin
    Work := Source;
    Dest := RemoveDblSpaces(Work);
  end;
  QueryPerformanceCounter(Stop);
  Label1.Caption := Format('%f ms', [(Stop - Start) / Freq * 1000]);

  QueryPerformanceCounter(Start);
  for I := 1 to TEST do
  begin
    Work := Source;
    while Pos('  ', Work) > 0 do
      Delete(Work, Pos('  ', Work), 1);
    Dest := Work;
  end;
  QueryPerformanceCounter(Stop);
  Label2.Caption := Format('%f ms', [(Stop - Start) / Freq * 1000]);
end;

Variante 1: ca. 42 ms
Variante 2: ca. 1567 ms

Vernichtendes Urteil gegen die while/Delete-Schleife ;)

...:cat:...

[Pichel]

Zitat:

Zitat von Jasocul

Käme auf einen Versuch an. Vielleicht hat Pichel ja Lust, die Varianten zu vergleichen?

Also meine "alte" Variante brauchte 2.654sek

Delphi-Quellcode:

while Pos('  ', DeinString) > 0 do
  Delete(DeinString, Pos('  ', DeinString), 1);

2.592sek
und

Delphi-Quellcode:

while Pos('  ', DeinString) > 0 do
  DeinString := StringReplace(DeinString, '  ', ' ', [rfReplaceAll]);

1.573sek

und das ganze bei einer Stringlänge von 77000 Zeichen, nicht so "pralle"

[sakura]

Zitat:

Zitat von Pichel

Also meine "alte" Variante brauchte 2.654sek
[...]
und 1.573sek

und das ganze bei einer Stringlänge von 77000 Zeichen, nicht so "pralle"

Nimm mein, die hat auf meinem PC nur 0,78 Millisekunden benötigt :mrgreen:

...:cat:...

[Jasocul]

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

[sakura]

Zitat:

Zitat von Jasocul

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

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

...:cat:...

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

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

...:cat:...

[jbg]

Zitat:

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 :mrgreen: zu meiner Verteidigung. Obige Lösung hatte ich blind in den Browser getippt ;)

Zitat:

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:

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:

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:

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:

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:

Zitat von jbg

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

Stimmt, in der neuen Lösung auf Pointer gewechselt :shock:

Zitat:

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:

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;

...:cat:...

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

Zitat von sakura

Zitat:

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

[jbg]

Wenn du jetzt das @XXX[1] noch durch ein PChar(XXX) ersetzt, dann gewinnst du nochmal Zeit, denn @S[index] bewirkt einen UniqueString()-Aufruf. Und das jedes mal. Result ist aber schon ein neuer String, da er mit SetLength neuen Speicher bekommen hat. Ein UniqueString Aufruf ist also nicht notwendig und kostet nur Zeit.

[quoet="3_of_8"] Ihr streitet euch jetzt nicht ernsthaft um ein paar ms Prozessorzeit, oder? [/quote]
Bis jetzt sehe ich keinen Streit. Nur Optimierungs-Methoden, wie mit "einfachen" Mitteln Geschwindigkeit herausschlagen kann. Die PChar-Varianten sind leider ein No-Go wenn man für .NET programmiert. Dort gelten ganz andere Regeln. So ist es in .NET 1.1 besser, wenn man einen String zuerst in ein array of Char umwandlet und dann darauf zugreift, weil damit einige Checks wegfallen. Das funktioniert aber auch nur für bestimmte String-Längen. Usw...

[Pichel]

Zitat:

Zitat von sakura

Nimm mein, die hat auf meinem PC nur 0,78 Millisekunden benötigt

Stimmt, danke habe sie jetzt getestet : 0.741 Sek... aber habe auch vergessen Euch zu sagen, bei meinen Zeiten habe ich nur den Durchlauf der gesamten Funktion gemessen und Euch verschwiegen :wink: das da noch ein wenig mehr mit den 7k Zeichen passiert:

Delphi-Quellcode:

  s := AdjustLineBreaks(sl.Text, tlbsLF);
  s := StringReplace(s, #10, #32, [rfReplaceAll,rfIgnoreCase]);
  s := StringReplace(s, #9, #32, [rfReplaceAll,rfIgnoreCase]);
  Result := removeDblSpaces(s);

Das StringReplace müsste sich ja dann auch noch mit Deiner Funktion weiter optimieren lassen?!?

Btw: also die Hilfe in diesem Forum ist einfach die schnellste und beste, ihr seit genial, Dank an Euch!

[SirThornberry]

Dann will ich mich auch mal beteiligen:

Delphi-Quellcode:

function RemoveDlbSpaces(const AStr: String): String;
var LCount,
    LDstLen,
    LSpCnt,
    LSrcLen  : Integer;
    LDst,
    LSrc     : PChar;
begin
  LDstLen := 0;
  LSrcLen := Length(AStr);
  SetLength(result, LSrcLen);
  LSpCnt := 0;
  LSrc := PChar(AStr);
  LDst := PChar(result);
  for LCount := 1 to LSrcLen do
  begin
    if LSrc^ = #32 then
      inc(LSpCnt)
    else
      LSpCnt := 0;
    if (LSpCnt < 2) then
    begin
      LDst^ := LSrc^;
      inc(Cardinal(LDst));
      inc(LDstLen);
    end;
    inc(Cardinal(LSrc));
  end;
  SetLength(result, LDstLen);
end;

Bei meinen Tests hat diese Funktion nur 2/3 der Zeit von DerDan benötigt. Ich hoffe ich hab nicht vergessen irgendwas zu berücksichtigen aber ich denke meine Funktion macht das was die anderen auch machen in einer annehmbaren Zeit.

Vielleicht liegt es aber auch an den verschiedenen Testmethoden. Denn die Methode von jbg war bei mir schneller als die von DerDan (jedoch nicht so schnell wie meine).

Es gäbe auch noch die Variante hier mit einem Var-Parameter zu arbeiten (was ja sinn macht wenn man mit dem abgewandelten String weiterarbeiten will). Dann wäre das ganze sicher noch um einiges schneller.

[jbg]

Zitat:

Zitat von SirThornberry

Vielleicht liegt es aber auch an den verschiedenen Testmethoden. Denn die Methode von jbg war bei mir schneller als die von DerDan (jedoch nicht so schnell wie meine).

Es hängt auch von der verwendeten CPU ab, da diese manche Befehle schneller als andere ausführen.

Zitat:

Es gäbe auch noch die Variante hier mit einem Var-Parameter zu arbeiten (was ja sinn macht wenn man mit dem abgewandelten String weiterarbeiten will). Dann wäre das ganze sicher noch um einiges schneller.

Dabei müsste man trotzdem eine Kopie des Strings anfertigen, wenn man nicht mit StringReplace-Methoden arbeiten will (Delete+Insert). Und mit einem Rückgabe-String ist die Funktion etwas mächtiger und man kann sie mit Funktionsaufrufen speißen.

[Pichel]

Zitat:

Zitat von SirThornberry

Dann will ich mich auch mal beteiligen
Bei meinen Tests hat diese Funktion nur 2/3 der Zeit von DerDan benötigt.

Also in meiner App jetzt die Testergebnisse: bisher bei 0.751 und nun 0.741

Ggf. liegt die geringe Verbesserung auch noch an den blöden StringReplace aufrufen in welchen ich ja eh nur einzelne Zeichen ersetzt... werde diesebezüglich noch nen bischen basteln und dann mal weitere messergebnisse posten.

[Pichel]

Zitat:

Zitat von SirThornberry

function RemoveDlbSpaces(const AStr: String): String;

Also wie gesagt, ich habe ja immer meine gesamte Funktion (mit dem StringReplace) gemessen und daher die letzte "kleine" Verbesserung.
Da ich ja lediglich zusätzlich noch #9, #13 und #10 ersetzen bzw. löschen will hab ich die Funktion nun entsprechend mal angepasst und nun braucht das ganze nur noch 3,77 ms hingegen vorher 0.751 sek!!!.
Genial, das reicht ;-))) !

Delphi-Quellcode:

function CollapseString(const AStr: String): String;
var LCount,
    LDstLen,
    LSpCnt,
    LSrcLen  : Integer;
    LDst,
    LSrc     : PChar;
begin
  LDstLen := 0;
  LSrcLen := Length(AStr);
  SetLength(result, LSrcLen);
  LSpCnt := 0;
  LSrc := PChar(AStr);
  LDst := PChar(result);
  for LCount := 1 to LSrcLen do begin
    if (LSrc^ = #10)
    or (LSrc^ = #13)
    or (LSrc^ = #9)
      then LSrc^ := #32;
    if LSrc^ = #32
      then inc(LSpCnt)
      else LSpCnt := 0;
    if (LSpCnt < 2) then begin
      LDst^ := LSrc^;
      inc(Cardinal(LDst));
      inc(LDstLen);
    end;
    inc(Cardinal(LSrc));
  end;
  SetLength(result, LDstLen);
end;

[DerDan]

Ich hab mal die Tips berücksichtigt und meine Funktion ein wenig zusammengefasst:
ich find ihn noch lesbarer wie meinen Alten.

Tatsächlich gibts wohl Abweichungen im Bereich der 20% alleine durch unterschiedliche CPU, HW und was weis ich.

Schade das niemand eine Assembler Lösung anbietet.


mfg

DerDan

Delphi-Quellcode:

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

Code:

Zeit1(   35,40 ms)/Zeit2    81,14% =   -18,86% (SirThornberry)
Zeit2(   43,63 ms)/Zeit2   100,00%             (sakura)
Zeit3(   32,77 ms)/Zeit2    75,12% =   -24,88% (derDan neu)
Zeit4(   36,84 ms)/Zeit2    84,44% =   -15,56% (jbg)

[alzaimar]

Das hier ist bei einem AMD 64 noch etwas (8%) schneller:

Delphi-Quellcode:

Function RemoveDblSpaces4(const InStr: string): string;
var
  Src, Dst: PChar;
begin
  SetLength(Result, Length(InStr));
  Src := Pointer (InStr);
  Dst := Pointer (Result);
  while (Src^ > #0) do Begin
    If PWord(Src)^ <> $2020 Then Begin // $2020 = 2 Blanks hintereinander
      Dst^:= Src^;
      inc (Dst);
      End;
    inc (Src);
  end;
  SetLength(Result, (Integer(Dst) - Integer(@Result[1])));
end;

Grob getestet, das Gerüst ist von DerDan.

[DerDan]

Zitat:

Zitat von alzaimar

Das hier ist bei einem AMD 64 noch etwas (8%) schneller:

Auch auf einem Intel, hab dort zwischen 1 bis 5 % bessere Geschwindigkeit


Respekt


DerDan

[Elvis]

Ich hatte in der Mittagspause auch mal ein wenig Lust auf den Thread bekommen... :mrgreen:
Ich habe alzaimar Idee aufgegriffen und den Character noch variabel gemacht.
Außerdem mag ich es nicht, wenn man Funktionen abhängig von #0 macht:

Delphi-Quellcode:

function RemoveDblSpaces5(const inputString : String; const character : Char) : String;
var
  currentChar, destinationChar : PChar;
  doubleChar :      Word;
  inputEndAddress : Integer;
begin
  doubleChar := (Byte(character) shl 8) + Byte(character);

  SetLength(Result, Length(inputString));

  destinationChar := Pointer(Result);
  currentChar     := Pointer(inputString);

  inputEndAddress:= (Length(inputString) * SizeOf(Char)) + Integer(currentChar);

  while Integer(currentChar) < inputEndAddress do
  begin
    destinationChar^ := currentChar^;

    repeat
      Inc(currentChar);
    until PWord(currentChar)^ <> doubleChar;

    Inc(destinationChar);
  end;

  SetLength(Result, (Integer(destinationChar) - Integer(@Result[1])));
end;

Ich habe es gerade mal mit 3 unterschiedlich großen Dateien(1KB, 32KB, 110KB: alles hässliche PL/SQL Skripts :mrgreen:) getestet.
Ich habe es nochmal auf der VM wiederholt, da ich dort eine etwas konstatere Auslastung habe als auf der übervölkerten "richtigen" Maschine.

Output

10000 iterations
File: small.txt
-> RemoveDblSpaces3: 43.49 ms
-> RemoveDblSpaces4: 31.32 ms
-> RemoveDblSpaces5: 22.69 ms
File: medium.txt
-> RemoveDblSpaces3: 2043.64 ms
-> RemoveDblSpaces4: 1581.14 ms
-> RemoveDblSpaces5: 1528.30 ms
File: large.txt
-> RemoveDblSpaces3: 7639.53 ms
-> RemoveDblSpaces4: 5031.43 ms
-> RemoveDblSpaces5: 5115.06 ms

VM Output

10000 iterations
File: small.txt
-> RemoveDblSpaces3: 44,02 ms
-> RemoveDblSpaces4: 22,79 ms
-> RemoveDblSpaces5: 22,49 ms
File: medium.txt
-> RemoveDblSpaces3: 2798,26 ms
-> RemoveDblSpaces4: 2411,56 ms
-> RemoveDblSpaces5: 2697,73 ms
File: large.txt
-> RemoveDblSpaces3: 8291,78 ms
-> RemoveDblSpaces4: 6943,51 ms
-> RemoveDblSpaces5: 6741,50 ms

[Pichel]

Ey... Leute....

Seid Ihr verrückt ;) (ich meine das absolut nett) :angel:

Es ist ja jetzt fast ein Wettstreit um die schnellste Funktion entstanden. Nein nicht nur fast, es ist.

Warum macht man daraus nicht gleich einen kompletten StringReplace Ersatz, denn das einzige was man zu StringReplace in den Foren findet ist, daß es "*rschlahm" ist :wink:

Ich würde mich gerne auch noch weiter produktiv an diesem Thema beteiligen, aber hier seid Ihr bereits so weit das ich da besser nur noch interessiert lese und lerne.

[DerDan]

Code:

Zeit1(   36,34 ms)/Zeit2    81,83% =   -18,17% (SirThornberry)
Zeit2(   44,41 ms)/Zeit2   100,00%             (sakura)
Zeit3(   34,89 ms)/Zeit2    78,57% =   -21,43% (jbg)
Zeit4(   29,93 ms)/Zeit2    67,41% =   -32,59% (DerDan)
Zeit5(   34,20 ms)/Zeit2    77,01% =   -22,99% (Elvis)

Ich habs mit der Testsuite von sakure aus einem der 1. Beiträge getestet (#7)

Tatsächlich sollte man mal richtige Testdaten Haben ...


mfg

DerDan

[jbg]

Zitat:

Zitat von Pichel

Warum macht man daraus nicht gleich einen kompletten StringReplace Ersatz, denn das einzige was man zu StringReplace in den Foren findet ist, daß es "*rschlahm" ist :wink:

Warum das Rad neu erfinden:

AnsiStringReplace vom FastCode Projekt sollte reichen. Schneller wird es wohl nicht gehen.

[DerDan]

Code:

Zeit1(   96,32 ms)/Zeit2    94,11% =    -5,89% (SirThornberry)
Zeit2(  102,35 ms)/Zeit2   100,00%             (sakura)
Zeit3(   90,74 ms)/Zeit2    88,66% =   -11,34% (jbg)
Zeit4(   72,29 ms)/Zeit2    70,64% =   -29,36% (DerDan)
Zeit5(   78,48 ms)/Zeit2    76,68% =   -23,32% (Elvis)

Testergebins mit einem Pascal Quelltext,

wie man sieht alles stark von den Eingangsdaten abhängig


mfg

derDan

Wer misst misst mist:


ich habe meinen Quelltext nochmals überprüft und festgestellt, dass
ich Zeit3 und Zeit 4 vertauscht habe:

korrekt ist das:

Code:

Zeit1(  378,25 ms)/Zeit2    88,62% =   -11,38% (SirThornberry)
Zeit2(  426,82 ms)/Zeit2   100,00%             (sakura)
Zeit3(  371,47 ms)/Zeit2    87,03% =   -12,97% (DerDan)
Zeit4(  317,78 ms)/Zeit2    74,45% =   -25,55% (jbg)
Zeit5(  345,66 ms)/Zeit2    80,98% =   -19,02% (Elvis)

Sorry vielmals

und Danke an Elvis der mir eine PN geschickt hat und ich daraufhin nochmals getestet habe
und meinen Fehler gefunden habe.

DerDan

[alzaimar]

Etwas verspätet, aber hier eine kleine Vergleichsgrafik. Erstellt wurden 5 Randomstrings (10 Mio Zeichen) mit mehr oder weniger häufigen doppelten Leerzeichen. Das Laufzeitverhalten ist stark Abhängig von der Häufigkeit. Lustigerweise kommt man dann zu anderen Ergebnissen, zumindest auf einem AMD.
http://www.edwebservice.de/uploads/ab0cabdd5f.bmp

[Fuchtel]

Hallo alzamir,

ist ganz hübsch, erinnert mich irgendwie an eine Gaussche Normalverteilung (mit 0 Punkt bei 50%).

Wenn Du jetzt noch die einzelnen Algorithmen der RemoveDblSpaces Functionen zum rauskopieren mit einbauen wuerdest, dann könnte jeder nach seiner CPU und abgeschätzten Prozentanteil, die passende Function gleich übernehmen.

Oder veröffentliche doch gleich den Quelltext.

Gruß Fuchtel

[Elvis]

Wieviel schulde ich dir für die Statistik? :mrgreen:
btw: Wie ich bereits angedeutet habe, packt mal irgendwo ein #0 in den String und probiert es noch mal. :twisted:
Meins ist zwar eigentlich eine Kopie von alzaimars Code, bei mir muss aber ein Integer anstatt einem Byte verglichen werden[1], dafür stopt die Funktion nicht beim ersten #0.
Es ist aber möglich, dass meine mit weniger Operationen auskommt wenn die Anzahl der aufeinander folgenden Doubletten steigt[2].

Fazit: Mal wieder eine nette Exkursion zurück in unmanaged, pointerverseuchte Gefilde. :stupid:

[1] Adresse hinter dem letzten Zeichen vs #0
[2] Solange muss sie ja nicht gegen die aktuelle Position prüfen.

[alzaimar]

Zitat:

Zitat von Fuchtel

Oder veröffentliche doch gleich den Quelltext

Ja, könnte ich machen, aber die Routinen stehen hier doch sowieso alle...
@Elvis: Schulden werden per :cheers: beglichen. :mrgreen:

[Fuchtel]

Hallo alzaimar,

nein, ich meinte, um die Option in dein Vergleichschart einzubauen, anhand des Ergebnisses
die passende Funktion von dort gleich in die Zwischenablage zu Übernehmen.

Gruß Fuchtel

[Elvis]

Zitat:

Zitat von Fuchtel

Hallo alzaimar,

nein, ich meinte, um die Option in dein Vergleichschart einzubauen, anhand des Ergebnisses
die passende Funktion von dort gleich in die Zwischenablage zu Übernehmen.

Wozu soll das gut sein? :gruebel:
Du würdest eigentlich nur 2 Funktionen brauchen. Eine, die besser mit Mini-Strings umgehen kann und eine für den Rest. Die für den Rest wird wohl immer noch schnell genug für die meisten Anwendungen von Mini-Strings sein. ;)

Ich denke nicht, dass alzaimar so offensichtlich Copy&Waste-"Programmierer" unterstützen würde. ;)