Diese funktion schneller machen?

[Pseudemys Nelsoni]

moin,

ich habe vor langer zeit mal folgende funktion geschrieben, die ich SEHR oft benutze (meistens zum parsen):

Delphi-Quellcode:

function GetTok(str: string; Tok: integer; sep: char): string;
var
  index: integer;
begin
  result := '';
  if (str = '') or (str = sep) or (Tok < 1) or (sep = '') then
    exit;
  if (pos(sep, str) = 0) and (Tok = 1) then
  begin
    result := str;
    exit;
  end;
  str := str + sep;
  while pos(sep+sep, str) > 0 do
    delete(str, pos(sep+sep, str), 1);
  if pos(sep, str) = 1 then
    delete(str, 1, 1);
  index := 1;
  while pos(sep, str) > 0 do
  begin
    if Tok = index then
    begin
      result := copy(str, 1, pos(sep, str)-1);
      exit;
    end
    else
    begin
      delete(str, 1, pos(sep, str));
      inc(index);
    end;
  end;
end;

ich rufe sie z.b so auf:

Delphi-Quellcode:

MeinString := 'Dies ist ein string';
s := GetTok(MeinString, 2, ' ');

das ergebnis wäre dann:

Zitat:

ist

nur sieht mir die funktion ziemlich lang aus und frage mich daher ob sie mein programm vielleicht langsam macht und es evtl eine schnellere variante gibt? (natürlich one stringlist...)

[Matze]

Mittels der Unit StrUtils geht es auf jedenfall kürzer, ob der Code dann schneller ist, weiß ich nicht.

Du kannst dann nämlich PosEx verwenden.

Edit: Welche Funktion hinter PosEx steckt, weiß ich allerdings auswendig nicht.

[mirage228]

Hi,

einmal gibt es da das Explode in der Code Library, dass einen String nach einem Seperator auflistet.

In deiner Funktion könntest Du noch das "const" vor dem String Parameter ergänzen.

mfG
mirage228

[Pseudemys Nelsoni]

hallo matze,

wie bekomme ich denn mit posex() den teil den ich aus dem hauptstring möchte? wie ich sehe gibt posex einen integer und kein string zurück

hallo mirage, stimmt, const könnt ich noch dranhängen, danke

[Matze]

Du bekommst den Index eines Strings, ab einer bestimmten Position und kann dir dann die 2 Indizes (in deinem Fall meistens Leerzeichen) merken und mittels Copy den String erhalten.

[choose]

Dein Problem lässt sich allgemein, wenn ich es richtig erkenne, wie folgt beschreiben:

Code:

Gib genau den Teil eines Strings zurück, der durch bestimmte Kriterien eingegrenzt ist.

Um diese Grenzen gemäß Deiner Kriterien zu ermitteln, verwendest Du allerdings recht rechenintensive Stringoperationen wie "Konkatenation", "Löschen von Zeichen", ...

Versuche stattdessen die Kriterien zu überprüfen, ohne die Strings zu verändern (zB über die Zeichenpositionen innerhalb des Strings), so dass folgender Pseudo-Code schneller zum Ergebnis führt:

Delphi-Quellcode:

function CalcBoundInStringStartingAt(const AString: string; 
  const AStart: Index; ...): Integer;
begin
  Result := AStart;
  while Result<Length(AString) and not DoesCriteriaMatch(...) do
    Inc(Result);
end;

function GetTok(const AString: string; ...): string;
var
  myLowerBound: Integer;
  myUpperBound: Integer;
begin
  myLowerBound := CalcBoundInStringStartingAt(AString, 1, ...);
  myUpperBound := CalcBoundInStringStartingAt(AString, Succ(myLowerBound), ...);
  
  UseBoundsToObtainResult(AString, myLowerBound, myUpperBound);
end;

Zu beachten sind selbstverstädnlich die Grenzfällen, bei denen die Kriterien nicht erfüllt sind, etc.

[Stevie]

Hi,

Delphi-Quellcode:

function GetTok(str: string; Tok: integer; sep: char): string;
var
  i, j: integer;
  b: Boolean;
  pos: Integer;
begin
  Result := '';
  if (Sep = '') or (Tok < 1) then
    Exit;
  j := 1;
  b := False;
  pos := 0;
  for i := 1 to length(str) do
  begin
    if str[i] = sep then
    begin
      if not b then
      begin
        Inc(j);
        b := True;
      end;
      if j > Tok then
        Break
      else
        Continue;
    end
    else
      b := False;
    if (pos = 0) and (j = Tok) then
      pos := i;
  end;
  if Pos > 1 then
    Result := Copy(str, pos, i - pos);
end;

ist in jedem meiner Testfälle schneller als deine Funktion.

MfG
Stevie

P.S. Gibt's PosEx erst in Delphi7? Hab hier Delphi6Pro an der Arbeit und find das Teil nicht!?
Edit: Nochmal geändert...

[negaH]

Delphi-Quellcode:

function ExtractToken(const Text: String; Index: Integer; const Seperator: Char = ' '): String;
var
  S,D: PChar;
begin
  S := PChar(Text);
  while (S^ <> #0) and (Index > 0) do
  begin
    if S^ = Separator then Dec(Index);
    Inc(S);

// falls mehrere Seperatoren nacheinander möglich sind, ohne Index zu ändern dann so
//
//    if S^ = Seperator then
//    begin
//      Dec(Index);
//      repeat
//        Inc(S);
//      until S^ <> Seperator;
//    end else Inc(S);
  end;
  D := S;
  while (D^ <> #0) and (D^ <> Separator) do 
    Inc(D);
  SetString(Result, S, D - S);
end;

Gruß Hagen

[Nothine]

Zitat:

Zitat von negaH

Delphi-Quellcode:

S := PChar(Text);

wäre

Delphi-Quellcode:

S := Pointer(Text);

nicht schneller? :gruebel:

[negaH]

Warum sollte es ?

Gruß Hagen

[Nothine]

weil S := PChar(Text) intern LStrToPChar aufruft, S := Pointer(Text) dagegen übergibt wirklich nur die adresse von @Text[1] an S

[GaP]

Hi,

ich stell einfach mal die Funktion mit der ich solche Aufgaben erledige in den Raum, ob sie schneller ist oder nicht kann ich nicht sagen, vllt. kann ja noch jemand Tipps geben... :)

Delphi-Quellcode:

function W(Wort: Integer; Text, Zeichen: String): String;
var Anfang, Ende, i: Integer;
begin
  Anfang := 0;
  Ende := 0;
  if Pos(Zeichen, Text) = 0 then Result := '' else begin
    if Wort = 1 then begin
      Anfang := Pos(Zeichen, Text);
      Result := MidStr(Text, 1, Anfang-1);
    end
    else begin
      for i:=1 to Wort-1 do Anfang := PosEx(Zeichen, Text, Anfang+1);
      if PosEx(Zeichen, Text, Anfang+1) = 0 then Ende := Length(Text)
      else Ende := PosEx(Zeichen, Text, Anfang+1)-Anfang-1;
      Result := MidStr(Text, Anfang+1, Ende);
    end;
  end;
end;

[negaH]

@Nothine: tja, das sind solche internen Änderungen zwischen den einzelnen Delphi Versionen. Bis Delphi 5 bin ich mir sicher das intern PChar(String) identisch zu Pointer(String) ist. Wenn aber in Delphi 7 intern LStrToPChar() aufgerufen wird dann muß das seine Gründe haben. Da wir unbedingt einen 0-terminierten PChar benötigen würde ich es so lassen wie es ist. Einfach der Kompatibilität halber.

Grundsätzlich dürfte damit meine Funktion nicht wesentlich langsammer werden, und davon mal abgesehen ist sie um vielfaches schneller als alle Varianten die mit Pos(), PosEx(), MidStr(), Delete() usw. arbeiten. Und meiner Meinung nach sogar viel einfacher zu verstehen ;)

Gruß Hagen

[DeerHunter]

mal eine Frage am Rande: wo ist der unterschied zwischen Pos und PosEx? letzteres scheint es wohl erst ab Delphi 7 zu geben, oder?

[Nothine]

@Hagen: klar, ich sag ja auch gar nichts gegen deine funktionen, du bist der profi hier, nich ich :mrgreen: und es ging ja auch nur darum wie man es schneller macht, und eine einfache pointerzuweisung is nu ma schneller :roll: und ich glaube ich muss dich enttäuschen, aber die information das intern LStrToPChar aufgerufen wird habe ich gerade eben meinem delphi 5(!) entnommen :wink:

@DeerHunter: jap, PosEx is erst später hinzugekommen und definiert zusätzlich einen start-offset, bei dem die suche beginnt

[negaH]

Stimmt, habe gerade nochmal in die RTL reingeschaut ;)

Allerdings muss PChar(String) dann benutzt werden, denn wenn Pointer(String) == NIL ist, wandelt _LStrToPChar() -> PChar(String) diesen NIL Zeiger in einen Zeiger auf einen PChar mit Null-Terminator um.
Wenn man also Pointer(String) benutzen will so muß man danach zusätzlich abfragen ob dieser Zeiger NIL ist. Dies wird dann aber wirklich nur 4-8 CPU Takte schneller sein als ein PChar(String).

Es lohnt also nicht sich vom "Standardkonformen" Weg zu entfernen und Pointer(String) statt PChar(String) zu benutzen.

Gruß Hagen

[Nothine]

okok, weniger tippen müsste man natürlich bei S := PChar(Text), andererseits stellt sich die frage ob man nicht eh am anfang der routine prüft ob Text = '', weil was will man aus einem leeren string schon an tokens oder indizes auslesen? :roll:

[negaH]

Ja, man könnte jeden Spezialfall mit einer eigenen Abfrage programmieren. Ich persönlich hasse das aber. Lieber die Funktionen so allgemein, kurz und schnell wie möglich halten.
Zb. in meinem obigem Vorschlag würde bei Text = '';

Delphi-Quellcode:

while (S^ <> #0) ... do;

schon zuschlagen. D.h. eine einzigste Abfrage. Dann weiter:

Delphi-Quellcode:

D := S;
while (D^ <> #0) do ;

eine Zuweisung -> "MOV Reg1, reg2" und eine Abfrage wiederum.
Und am Schluß

Delphi-Quellcode:

  SetString(Result, S,D - S);

eine Subtraktion "SUB ECX,EDX"und ein CALL _SetLength(EAX, EDX, ECX);

Damit ist der UNWAHRSCHEINLICHSTE Fall, das Text == '' ist, genügend abgedeckt. Viel wahrscheinlicher sind aber Strings <> '', und somit würde eine ständige vorherige und spezielle Abfrage auf Text = '' eher bremsen als sinnvoll sein.

Programmiere immer nur soviel wie absolut nötig ist, verkompliziere nicht die Logik mit Abfragen die vom Programmfluß eher am unwahrscheinlichsten sind. Als Resulat kommt eine Lösung heraus die man leicht versteht und gut optimiert und denoch kurz und bündig ist.

Momentan sehe ich echt keinen Grund bzw. weitere Möglichkeit meine Funktion weiter zu verbessern.

Gruß Hagen

[Nothine]

obwohl sie gegen ende umständlicher aussieht, ist diese

Delphi-Quellcode:

function ExtractToken(const Text: string; Index: Integer; const Separator: Char = ' '): string;
var S,D: PChar;
begin
  S := PChar(Text);
  while (S^ <> #0) and (Index > 0) do begin
    if S^ = Separator then Dec(Index);
    Inc(S);
  end;
  D := S;
  while (D^ <> #0) and (D^ <> Separator) do Inc(D);
  SetLength(Result,D-S);
  D := Pointer(Result);
  while (S^ <> Separator) and (S^ <> #0) do begin
    D^ := S^;
    Inc(S);
    Inc(D);
  end;
end;

funktion auf meinem system bei 10000000 wiederholungen ca. 600 millisekunden schneller, bitte um test deinerseits

edit: nur noch zur info, zeitversuch nach dem GetTickCount-prinzip

[negaH]

probier mal

Delphi-Quellcode:

  R := Pointer(Result); 
  while S < D do 
  begin 
    R^ := S^; 
    Inc(S); 
    Inc(R); 
  end;

// oder
  
  R := Pointer(Result);
  for I := 0 to D - S -1 do
    R[I] :=  S[I];

Das SetString() langsammer sein kann auf modernen CPU's im Gegensatz zu einer eigenen Loop kann durchaus so sein. Allerdings beachte das du mit dynamisch allozierten Strings arbeitest, und dein Test eventuell immer wieder die gleichen Speicherbereiche benutzt da der Speicher Manager so arbeitet. In einem solchen Falle, und nur in einem solchen Fall, kann eine einfache Loop schneller sein als das REP MOVSW in Copy()->SetString().
Du solltest also deine Tests so aufbauen das nacheinander, sozusagen verschachtelt immer wieder neue Speicherbereiche alloziert werden. Zudem solltest du die Funktion INNERHALB von vielen anderen Funktionen testen. Also simulierst du die wahrscheinlichst realen Bedingungen der Anwendung der Funktion innerhalb eines Programmes. Ich vermute das du einfach in deinen Tests in einer Schleife die Funktion mit den gleichen Daten aufgerufen hast. Solche Test sagen fast garnichts über die realen Verhältnisse der Funktion in realen Programmen aus.

Gruß Hagen

[phXql]

Delphi-Quellcode:

var t_list: TStringList;
begin
  result := '';
  t_list := TStringList.Create;
  try
    t_list.Delimiter = sep;
    t_list.Text := Text;
    result := t_list[index];
  finally
    FreeAndNil(t_list);
  end;
end;

ungetestet. schau mal wie schnell die is...

// Edit: VERDAMMT! wer lesen kann is klar im vorteil... :/
Ignoriert diesen Post einfach...

[Stevie]

Moin,

ich hab bei Tests festgestellt, dass eure Funktionen etwas von der ursprünglichen abweichen, was das Erkennen des richtigen Teilstrings angeht. Die ursprüngliche liefert bei einem Sep = ' ' den ersten String bis zu einem Leerzeichen zurück, wenn man Index = 1 angibt, aber eure erst den String nach dem ersten Leerzeichen!

[negaH]

Jo, das ist richtig, und ich finde es auch logischer. Viele Indizes, sei es Arrays[], TList, TStrings usw. gehen von 0 bis Count -1, man arbeitet also viel öfters 0-basiert als 1-basiert. Das erste Element sollte den Index 0 haben. Du kannst das aber sehr einfach ändern, indem du als erstes in der Funktion Dec(Index); aufrufst.

Gruß Hagen

[Stevie]

Zitat:

Zitat von negaH

Jo, das ist richtig, und ich finde es auch logischer.

Jo, das find ich allerdings auch... Was macht deine Funktion eigentlich bei zwei Separatoren hintereinander?? Leerer String (logischer) oder als einen betrachten (imho von der Ursprungsfunktion so gemacht)?

[negaH]

Im Source der Funktion habe ich ein Stückchen auskommentiert. Lies dazu mal den Kommentar, der beantwortet exakt diese Frage. Die normale Funktion betrachtet jeden einzelnen Separator als Separator für einen Teilsting. Zb. bei einem String wie "rot,grün,gelb,,blau" wäre es logisch das der String zwischen ",," eben auch gezählt wird und einen eigenen Index besitzt. Nun, die Standardvorgehensweise meiner Funktion ist jeden Sepeartor zu zählen.
Anderst du meine Funktion aber so ab das das asukommentierte aktiv ist so arbeitet die Funktion so wie die es dir wünscht. D.h. die beiden ",," würde als 1 Separator gezählt.

Gruß Hagen

[Stevie]

Zitat:

Zitat von negaH

Im Source der Funktion habe ich ein Stückchen auskommentiert. Lies dazu mal den Kommentar, der beantwortet exakt diese Frage.

Wer lesen kann, ist klar im Vorteil! :wall: :roll: Sorry... :angel2: