Diese Funktion schneller machen?

[Pseudemys Nelsoni]

ok, diese funktion ist nur ein beispiel, aber viele meiner andere laufen genauso ab...

Delphi-Quellcode:

function fmtstr(const s: string; const c: char): string;
var
  i: integer;
  b: boolean;
begin
  result := ''; b := false;
  for i := 1 to length(s) do
  begin
    if s[i] = c then
    begin
      if (result = '') or (b = true) then
        continue;
      b := true;
    end
    else b := false;
    result := result + s[i];
  end;
  if (result <> '') and (result[length(result)] = c) then
    setstring(result, pchar(result), length(result)-1);
end;

ziel dieser funktion ist es einen string "ordentlich" zu machen, anhand des seperators.... also wenn ich z.b so einen string übergebe:

Zitat:

..hi.bla.....blubb....

wird die funktion:

Zitat:

hi.bla.blubb

zurückgeben.

wenn ich diese funktion 1million mal in einer schleife aufrufe dauert das ganze ca 1,094 sekunden....

gibt es irgendwie eine schnellere methode für diese funktion? es sollten keine funktionen aus der VCL verwendet werden.

[jbg]

Zitat:

Zitat von Pseudemys Nelsoni

result := result + s[i];

Das kostet auf Dauer sehr viel Rechenzeit, da ein neuer Speicherbereich mit einem Byte mehr reserviert wird, der alte String dort hinein kopiert und das Zeichen angehängt wird. Zusätzlich muss der alte String-Speicher freigegeben werden.
Und dieses Prozedere wird nun 1 Mio mal ausgeführt.
Besser du setzt Result vor der Schleife auf die Worst-Case Länge (in deinem Fall SetLength(Result, Length(S))). Nun kannst du die Zeichen direkt zuweisen "Inc(RealLen);Result[RealLen] := S[i];". Nach dem Schleifendurchlauf setzt du nun mit SetLength(Result, RealLen) die entgültige Länge fest.

Zitat:

Delphi-Quellcode:

  if (result <> '') and (result[length(result)] = c) then
    setstring(result, pchar(result), length(result)-1);

Hätte es nicht auch SetLength(Result, Length(Result) - 1) getan?


Für was brauchst du denn b. Das wird doch gar nicht ausgewertet.

[Pseudemys Nelsoni]

hallo jbg,

danke für deine antwort, ich werde versuchen es umzusetzen.

b ist true wenn das letzte zeichen der seperator war, so vermeide ich das ein seperator doppelt geschrieben wird.


EDIT:

Delphi-Quellcode:

function fmtstr(const s: string; const c: char): string;
var
  i, len: integer;
  b: boolean;
begin
  Result := '';
  if s <> '' then
  begin
    setlength(result, length(s));
    len := 0; b := false;
    for i := 1 to length(s) do
    begin
      if s[i] = c then
      begin
        if (result[1] = #0) or (b = true) then
          continue;
        b := true;
      end
      else b := false;
      len := len + 1;
      result[len] := s[i];
    end;
    if result[length(result)] = c then
      setlength(result, len-1)
    else setlength(result, len);
  end;
end;

was ist denn hier falsch?

wenn ich das tue:

Zitat:

test := fmtstr('s.u...', '.');

dann ist test "s.u."


wieso ist der punkt am ende noch da?

[jbg]

Zitat:

Delphi-Quellcode:

if (result[1] = #0) or (b = true) then

Das ist nicht dasselbe wie oben. Das Result[1] zeigt dir nicht an, dass der String leer ist. Das kannst du mit "len = 0" prüfen. Und ein "b = true" kann tötlich enden. Lass einfach das "=true" weg. Und bei "b=false" kann man auch schreiben "not b". Beides ist erstens kürzer und auch irgendwie besser erkennbar.

Zitat:

Delphi-Quellcode:

    if result[length(result)] = c then
      setlength(result, len-1)
    else setlength(result, len);

Das Length(Result) ist zu diesem Zeitpunkt ja nicht zwangsläufig das letzte Zeichen. Das steht nämlich in Result[len]. Und du kannst hier die zwei SetLength aufrufe zu einem machen, indem du bei dem TRUE-Code der if-Abfrage einfach Len dekrementierst. Das ist nämlich der einzige Unterschied zum anderen SetLength() Aufruf.

[Pseudemys Nelsoni]

moin jbg,

habe es nun so:

Delphi-Quellcode:

function fmtstr(const s: string; const c: char): string;
var
  i, len: integer;
  b: boolean;
begin
  if s <> '' then
  begin
    len := 0; b := false;
    setlength(result, length(s));
    result[1] := #0;
    for i := 1 to length(s) do
    begin
      if s[i] = c then
      begin
        if (result[1] = #0) or (b) then
        begin
          b := true;
          continue;
        end;
        b := true;
      end
      else b := false;
      len := len + 1;
      result[len] := s[i];
    end;
    if result[len] = c then
      setlength(result, len-1)
    else setlength(result, len);
  end;
end;

funktioniet einwandfrei, danke nochmal.

was meinst du mit "tödlich" enden? generell meine boolesche variable dort oder das ich "= true" benutzt habe?

btw: kann ich das doppelte "b := true" irgendwie zu einem machen?

[Robert Marquardt]

Ich wuerde das letzte Zeichen am Ende einmal pruefen und gegebenenfalls weghauen.
Damit verschwindet dieser unsinnige und unelegante Test mit der booleschen Variablen.

[Pseudemys Nelsoni]

brauche die variable aber für die mittleren seperatoren, wenn B true ist, dann war das zeichen davor bereits der seperator

[Muetze1]

Moin!

Ich frage mich ob es nicht schneller sein würde, mit Pos ein doppelten Separator zu suchen und wenn man was findet einfach ab da mit der Schleife weiter zu laufen und zu sehen wieviele Separatoren noch kommen. Wenn man in der Schleife einen nicht Separator findet, dann kannst du mit Delete() doch bei der Position von Pos()+1 bis zur aktuellen Stelle die Zeichen löschen und gut. Sollte das nicht schneller gehen als auch noch die Strings in der grossen Schleife durchzugehen. Und mit Pos() klappt es auch, da ein .. nachher nicht mehr zu finden sein sollte.

Nur mal so als Idee...

MfG
Muetze1

[jim_raynor]

Zitat:

Zitat von Muetze1

Sollte das nicht schneller gehen als auch noch die Strings in der grossen Schleife durchzugehen. Und mit Pos() klappt es auch, da ein .. nachher nicht mehr zu finden sein sollte.

Ich bezweifel das ständige Pos aufrufe schneller sind.
1. Ist ein Funktionsaufruf immer "Verhältnismäßig" langsam.
2. geht Pos immer von Anfang den String durch. Macht also viele unnütze Aktionen.
3. Bei Delete ist doch das gleiche Probleme wie viele SetLengths. Es wird jedes mal neuer Speicher angefordert und alter freigegeben. Was insgesamt sicherlich negativ auf die Performance ausschlagen wird.

Einzige Optimierung die mir noch einfallen würde ist, am Anfang alle Separatoren zu überspringen.

Delphi-Quellcode:

var
  Start: Integer;
begin
  Len:=Length(s);
Start:=1;
  while (result[Start]=c) and (Start<Len) do
    inc(Start);
for i := Start to length(s) do

(irgendwie sowas) Dadurch spart man sich das result[1] = #0 im if.

Statt Len := Len+1 benutze inc(Len);

statt immer s[i] und result[len] zu machen könntest du auch einen Pointer (PChar) verwenden, der immer erhöht wird.[/delphi]

[Robert Marquardt]

Wie waere es denn mit
Result := StringReplace(S, Ch + Ch, Ch, [rfReplaceAll]);
Dann muss nur noch auf ein Ch am Ende getestet werden.

[ibp]

Zitat:

Zitat von Robert Marquardt

Wie waere es denn mit
Result := StringReplace(S, Ch + Ch, Ch, [rfReplaceAll]);
Dann muss nur noch auf ein Ch am Ende getestet werden.

Zitat:

Zitat von Pseudemys Nelsoni

...es sollten keine funktionen aus der VCL verwendet werden.

[Chewie]

Zitat:

Zitat von ibp

Zitat:

Zitat von Robert Marquardt

Wie waere es denn mit
Result := StringReplace(S, Ch + Ch, Ch, [rfReplaceAll]);
Dann muss nur noch auf ein Ch am Ende getestet werden.

Zitat:

Zitat von Pseudemys Nelsoni

...es sollten keine funktionen aus der VCL verwendet werden.

StringReplace ist auch nicht Teil der VCL, sondern der RTL ;) .

[ibp]

ok ok :duck: geb mich geschlagen, bitte nicht mit schneebällen werfen :freak:

[sECuRE]

Hi,

spaßeshalber hab ich mal 'nen vergleich zwischen StringReplace und Nelsonis Variante gemacht, raus kam bei StringReplace 1297 Ticks und bei der anderen lediglich 62 Ticks (bei jeweils 100000x aufrufen). Pos + StringReplace ist also definitiv die langsamere Methode ;)

cu

[Pseudemys Nelsoni]

@mütze: das ganze sollte wenn überhaupt nur die funktionen aus der Unit "System" bzw "Windows" verwenden

@jim: der + operator ist aber (unbedeutend?) schneller als inc().

@Robert: dann müsste ich die unit SysUtils einbinden.

Zitat:

statt immer s[i] und result[len] zu machen könntest du auch einen Pointer (PChar) verwenden, der immer erhöht wird.[/delphi]

das interessiert mich ^^, hast du ein beispiel dafür? ich arbeite kaum mit pchars

[jim_raynor]

Zitat:

Zitat von Pseudemys Nelsoni

Zitat:

statt immer s[i] und result[len] zu machen könntest du auch einen Pointer (PChar) verwenden, der immer erhöht wird.[/delphi]

das interessiert mich ^^, hast du ein beispiel dafür? ich arbeite kaum mit pchars

Kein Beispiel sondern deine Funktion direkt umgeschrieben:

Delphi-Quellcode:

function fmtstr(const s: string; const c: char): string;
var
  i, len  : integer;
  ResLen  : Integer;
  b       : boolean;
  Start   : Integer;
  resPtr  : PChar;
  sPtr    : PChar;

  endsPtr : Pchar;
begin
  if s <> '' then
  begin
    b := false;

    Len:=Length(s);
    setlength(result, len);
    Start:=1;
    sPtr:=Addr(s[1]);
    resPtr:=Addr(result[1]);
    endsPtr:=Addr(s[length(s)]);

    while (sPtr^=c) and (sPtr<endsPtr) do
    begin
      inc(Start);
      inc(sPtr);
    end;

    ResLen:=0;

    for i := Start to Len do
    begin
      if (sPtr^ <> c) or (not b) then
      begin
        resPtr^ := sPtr^;
        inc(resPtr);
        inc(ResLen);
      end;

      b:=sPtr^=c;

      inc(sPtr);
    end;
    if (resPtr-1)^ = c then
      setlength(result, reslen-1)
    else
      setlength(result, reslen);
  end;
end;

Sieht zwar Länger aus, denke aber, dass es so schneller ist, da die ganzen Indexzugriffe entfallen. Ist natürlich bissle kryptisch, wenn Fragen sind, dann frag.

[Nothine]

Zitat:

Zitat von Pseudemys Nelsoni

@jim: der + operator ist aber (unbedeutend?) schneller als inc().

wie soll das gehen wenn beide anweisungen den selben maschinencode erzeugen? :gruebel:

[edit]

Zitat:

Zitat von Meine OH

...
X wird um 1 inkrementiert oder um N, wenn N angegeben ist. Das bedeutet, Inc(X) entspricht der
Anweisung X := X + 1, und Inc(X, N) ist mit der Anweisung X := X + N identisch. Inc generiert jedoch hochoptimierten Maschinencode und ist besonders für Schleifen geeignet.
...

[jim_raynor]

Zitat:

Zitat von Nothine

wie soll das gehen wenn beide anweisungen den selben maschinencode erzeugen? :gruebel:

Zitat:

Zitat von Meine OH

... Inc generiert jedoch hochoptimierten Maschinencode und ist besonders für Schleifen geeignet....

Sie generieren eben nicht identischen Maschienencode. Die OH sagt doch alles.

[Pseudemys Nelsoni]

danke jim, ich testes gleich mal :)

btw: in der OH steht irgendwo "Tipp: der + operator ist schneller als inc"

[Robert_G]

OT:

Zitat:

Zitat von Pseudemys Nelsoni

danke jim, ich testes gleich mal :)

btw: in der OH steht irgendwo "Tipp: der + operator ist schneller als inc"

Da steht höchstens, dass + schneller als concat ist. ;) Ich bezweifle einen Unterschied zwischen + und inc() im Kompilat.