Y at-il une routine rapide GetToken Pour Delphi?
https://stackoverflow.com/questions/1694001
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Dans mon programme, je traite des millions de chaînes qui ont un caractère spécial, par exemple "|" de séparer les jetons à l'intérieur de chaque chaîne. J'ai une fonction de retourner le jeton n'th, et voici:
function GetTok(const Line: string; const Delim: string; const TokenNum: Byte): string;
{ LK Feb 12, 2007 - This function has been optimized as best as possible }
var
I, P, P2: integer;
begin
P2 := Pos(Delim, Line);
if TokenNum = 1 then begin
if P2 = 0 then
Result := Line
else
Result := copy(Line, 1, P2-1);
end
else begin
P := 0; { To prevent warnings }
for I := 2 to TokenNum do begin
P := P2;
if P = 0 then break;
P2 := PosEx(Delim, Line, P+1);
end;
if P = 0 then
Result := ''
else if P2 = 0 then
Result := copy(Line, P+1, MaxInt)
else
Result := copy(Line, P+1, P2-P-1);
end;
end; { GetTok }
J'ai développé cette fonction quand j'utilisais Delphi 4. Il appelle la routine de PosEx très efficace qui a été développé à l'origine par Fastcode et est maintenant inclus dans la bibliothèque StrUtils de Delphes.
J'ai récemment mis à jour à Delphi 2009 et mes cordes sont tous Unicode. Cette fonction GetTok fonctionne toujours et fonctionne encore bien.
Je suis passé par les nouvelles bibliothèques de Delphi 2009 et il y a beaucoup de nouvelles fonctions et ajouts.
Mais je ne l'ai pas vu une fonction GetToken comme je l'ai besoin dans l'une des nouvelles bibliothèques Delphi, dans les différents projets de fastcode, et je ne peux pas trouver quoi que ce soit avec une recherche Google autre que Zarko Gajic de:. Delphi Fonctions de Split / Tokenizer qui n'est pas aussi optimisé que ce que je l'ai déjà
Toute amélioration, même 10% serait perceptible dans mon programme. Je sais une alternative est StringLists et de toujours garder les jetons séparés, mais cela a une grande mémoire sage en tête et je ne sais pas si je l'ai fait tout ce travail pour convertir que ce serait plus vite.
Ouf. Alors, après tout ce discours de longue haleine, ma question est vraiment:
Connaissez-vous des implémentations très rapide d'une routine GetToken? Une version optimisée assembleur serait idéal?
Dans le cas contraire, yat il des optimisations que vous pouvez voir à mon code ci-dessus qui pourrait apporter une amélioration?
Followup: Barry Kelly a mentionné une question que je posais il y a un an sur l'optimisation l'analyse syntaxique des lignes dans un fichier. A cette époque, je l'avais même pas pensé à ma routine GetTok qui n'a pas été utilisé pour la lecture ou que l'analyse syntaxique. Il est seulement maintenant que j'ai vu la tête de ma routine GetTok qui m'a amené à poser cette question. Jusqu'à ce que Carl Smotricz et les réponses de Barry, je ne l'avais jamais pensé à relier les deux. Si évident, mais ça n'a pas été enregistré. Merci de remarquer cela.
Oui, mon Delim est un seul caractère, donc évidemment j'ai une optimisation importante que je peux faire. Mon utilisation de Pos et PosEx dans la routine GetTok (ci-dessus) m'a aveuglé à l'idée que je peux le faire plus rapidement avec un caractère par caractère au lieu de recherche, avec des bouts de code comme:
while (cp^ > #0) and (cp^ <= Delim) do
Inc(cp);
Je vais passer par les réponses de tout le monde et essayer les différentes suggestions et de les comparer. Ensuite, je vais poster les résultats.
Confusion. Ok, maintenant je suis vraiment perplexe
Je pris la recommandation de Carl et Barry pour aller avec PChars, et voici ma mise en œuvre:
function GetTok(const Line: string; const Delim: string; const TokenNum: Byte): string;
{ LK Feb 12, 2007 - This function has been optimized as best as possible }
{ LK Nov 7, 2009 - Reoptimized using PChars instead of calls to Pos and PosEx }
{ See; https://stackoverflow.com/questions/1694001/is-there-a-fast-gettoken-routine-for-delphi }
var
I: integer;
PLine, PStart: PChar;
begin
PLine := PChar(Line);
PStart := PLine;
inc(PLine);
for I := 1 to TokenNum do begin
while (PLine^ <> #0) and (PLine^ <> Delim) do
inc(PLine);
if I = TokenNum then begin
SetString(Result, PStart, PLine - PStart);
break;
end;
if PLine^ = #0 then begin
Result := '';
break;
end;
inc(PLine);
PStart := PLine;
end;
end; { GetTok }
Sur le papier, je ne pense pas que vous pouvez faire beaucoup mieux que cela.
Alors je mets les deux routines à la tâche et utilisé AQtime pour voir ce qui se passe. La course que j'avais inclus 1,108,514 appels à GetTok.
Temps AQtime la routine originale à 0,40 seconde. Les millions d'appels ont Pos 0,10 secondes. Un demi-million de copies TokenNum = 1 a pris 0,10 secondes. Les 600 000 appels PosEx seulement a pris 0.03 secondes.
Alors je chronométré ma nouvelle routine avec AQtime pour la même course et exactement les mêmes appels. AQtime rapporte que ma nouvelle routine « rapide » a pris 3,65 secondes, ce qui est 9 fois plus longtemps. Le coupable selon AQtime a été la première boucle:
while (PLine^ <> #0) and (PLine^ <> Delim) do
inc(PLine);
La ligne while, qui a été exécuté 18 millions de fois, a été signalé à 2,66 secondes. La ligne inc, exécuté 16 millions de fois, a été dit de prendre 0,47 secondes.
Maintenant, je pensais que je savais ce qui se passait ici. J'ai eu un problème similaire avec AQtime dans une question que je posais l'année dernière: Pourquoi CharInSet plus rapide que la déclaration de cas?
Encore une fois, il était Barry Kelly qui m'a clued. En fait, un profileur instrumentant comme AQtime dOES ne sont pas nécessairement le travail pour microoptimization. Elle ajoute une tête à chaque ligne qui peut inonder les résultats qui est montré clairement dans ces chiffres. Les 34 millions de lignes exécutées dans mon nouveau « code optimisé » submergent plusieurs millions de lignes de mon code d'origine, avec apparemment peu ou pas de frais généraux des routines Pos et PosEx.
Barry m'a donné un exemple de code utilisant QueryPerformanceCounter pour vérifier qu'il avait raison, et dans ce cas il était.
D'accord, donc nous allons faire la même chose maintenant avec QueryPerformanceCounter pour prouver que ma nouvelle routine est plus rapide et pas 9 fois plus lent que AQtime dit qu'il est. Donc ici, je vais:
function TimeIt(const Title: string): double;
var i: Integer;
start, finish, freq: Int64;
Seconds: double;
begin
QueryPerformanceCounter(start);
for i := 1 to 250000 do
GetTokOld('This is a string|that needs|parsing', '|', 1);
for i := 1 to 250000 do
GetTokOld('This is a string|that needs|parsing', '|', 2);
for i := 1 to 250000 do
GetTokOld('This is a string|that needs|parsing', '|', 3);
for i := 1 to 250000 do
GetTokOld('This is a string|that needs|parsing', '|', 4);
QueryPerformanceCounter(finish);
QueryPerformanceFrequency(freq);
Seconds := (finish - start) / freq;
Result := Seconds;
end;
Donc, ce testera 1.000.000 appels à GetTok.
Mon ancienne procédure avec les appels Pos et PosEx a pris 0,29 secondes. Le nouveau avec PChars a pris 2,07 secondes.
Maintenant, je suis complètement embrouillé! Quelqu'un peut-il me dire pourquoi la procédure PChar est non seulement plus lent, mais est de 8 à 9 fois plus lent!
Mystère résolu! Andreas a dit dans sa réponse à changer le paramètre Delim d'une chaîne à un Char. Je serai toujours en utilisant simplement un char, donc au moins pour ma mise en œuvre ce qui est très possible. Je suis étonné de voir ce qui est arrivé.
Le temps pour les 1 million d'appels est passé de 1,88 secondes à .22 secondes.
Et étonnamment, le temps de ma routine originale Pos / PosEx est passé de 0,29 à 0,44 secondes quand je l'ai changé est le paramètre Delim à un Char.
Franchement, je suis déçu par l'optimiseur de Delphi. Ce Delim est un paramètre constant. L'optimiseur aurait remarqué que la même conversion se produit dans la boucle et aurait déplacé de telle sorte qu'il ne serait fait une fois.
Double vérifier mes paramètres de génération de code, oui j'ai optimisation Format vrai et chaîne cocher.
Bottom line est que la nouvelle routine PChar avec correction d'Andrea est environ 25% plus rapide que mon original (.22 par rapport à .29).
Je veux toujours donner suite aux autres commentaires ici et les tester.
Mise hors optimisation et mise sous format chaîne de vérification augmente seulement le temps de 0,22 à 0,30. Il ajoute au sujet de la même chose à l'original.
L'avantage d'utiliser le code assembleur, ou d'appeler des routines écrites en assembleur comme Pos ou PosEx est qu'ils ne sont pas soumis à ce que les options de génération de code que vous avez défini. Ils seront toujours courir de la même façon, d'une manière pré-optimisé et non pléthorique.
Je l'ai réaffirmé au cours des derniers jours, que la meilleure façon de comparer le code pour microoptimization est de regarder et comparer le code Assembleur dans la fenêtre CPU. Ce serait bien si Embarcadero pourrait faire cette fenêtre un peu plus pratique, et nous permettent de copier des parties au presse-papiers ou d'imprimer des sections de celui-ci.
En outre, je injustement claqué AQtime plus tôt dans ce post, pensant que le temps supplémentaire ajouté pour ma nouvelle routine était uniquement en raison de l'instrumentation at-il ajouté. Maintenant que je revenir en arrière et vérifier avec le paramètre Char au lieu de chaîne, la boucle while est en baisse à .30 secondes (2,66) et la ligne inc est en baisse à .14 secondes (de 0,47). Il est étrange que la ligne inc descendrait aussi bien. Mais je me usé de tous ces tests déjà.
Je pris l'idée de Carl de boucle par des personnages, et récrit ce code avec cette idée. Il est une autre amélioration, jusqu'à .19 secondes de .22. Ainsi, voici le meilleur à ce jour:
function GetTok(const Line: string; const Delim: Char; const TokenNum: Byte): string;
{ LK Nov 8, 2009 - Reoptimized using PChars instead of calls to Pos and PosEx }
{ See; https://stackoverflow.com/questions/1694001/is-there-a-fast-gettoken-routine-for-delphi }
var
I, CurToken: Integer;
PLine, PStart: PChar;
begin
CurToken := 1;
PLine := PChar(Line);
PStart := PLine;
for I := 1 to length(Line) do begin
if PLine^ = Delim then begin
if CurToken = TokenNum then
break
else begin
CurToken := CurToken + 1;
inc(PLine);
PStart := PLine;
end;
end
else
inc(PLine);
end;
if CurToken = TokenNum then
SetString(Result, PStart, PLine - PStart)
else
Result := '';
end;
Il peut y avoir encore quelques optimisations mineures à cela, comme la comparaison CurToken = Tokennum, qui devrait être le même type, Entier ou octet, selon le plus rapide.
Mais disons, je suis heureux maintenant.
Merci encore à la communauté StackOverflow Delphi.
La solution
Votre nouvelle fonction (celle avec PChar) devrait déclarer "Delim" Char et non comme Chaîne . Dans votre implémentation actuelle le compilateur doit convertir le pline ^ car en une chaîne pour le comparer avec « Delim ». Et cela se produit dans une boucle serrée résultant est un succès énorme performance.
function GetTok(const Line: string; const Delim: Char{<<==}; const TokenNum: Byte): string;
{ LK Feb 12, 2007 - This function has been optimized as best as possible }
{ LK Nov 7, 2009 - Reoptimized using PChars instead of calls to Pos and PosEx }
{ See; http://stackoverflow.com/questions/1694001/is-there-a-fast-gettoken-routine-for-delphi }
var
I: integer;
PLine, PStart: PChar;
begin
PLine := PChar(Line);
PStart := PLine;
inc(PLine);
for I := 1 to TokenNum do begin
while (PLine^ <> #0) and (PLine^ <> Delim) do
inc(PLine);
if I = TokenNum then begin
SetString(Result, PStart, PLine - PStart);
break;
end;
if PLine^ = #0 then begin
Result := '';
break;
end;
inc(PLine);
PStart := PLine;
end;
end; { GetTok }
Autres conseils
Il fait une grande différence ce que « Delim » devrait être. S'il est prévu d'être un seul caractère, vous êtes beaucoup mieux marcher à travers le caractère de chaîne par caractère, idéalement par un PChar, et tester spécifiquement.
Si c'est une longue chaîne, Boyer-Moore et recherches similaires ont une phase de mise en place pour les tables de saut, et la meilleure façon serait de construire les tables une fois, et les réutiliser pour chaque découverte ultérieure. Cela signifie que vous devez l'état entre les appels, et cette fonction serait mieux comme méthode sur un objet à la place.
Vous pourriez être intéressé par Voici le programme complet j'ai utilisé pour l'analyse comparative.
Voici les résultats:
*** count=3, Length(src)=200
GetTok1: 595 ms
GetTok2: 547 ms
GetTok3: 2366 ms
GetTok4: 407 ms
GetTokBK: 226 ms
*** count=6, Length(src)=350
GetTok1: 1587 ms
GetTok2: 1502 ms
GetTok3: 6890 ms
GetTok4: 679 ms
GetTokBK: 334 ms
*** count=9, Length(src)=500
GetTok1: 3055 ms
GetTok2: 2912 ms
GetTok3: 13766 ms
GetTok4: 947 ms
GetTokBK: 446 ms
*** count=12, Length(src)=650
GetTok1: 4997 ms
GetTok2: 4803 ms
GetTok3: 23021 ms
GetTok4: 1213 ms
GetTokBK: 543 ms
*** count=15, Length(src)=800
GetTok1: 7417 ms
GetTok2: 7173 ms
GetTok3: 34644 ms
GetTok4: 1480 ms
GetTokBK: 653 ms
En fonction des caractéristiques de vos données, si le délimiteur est susceptible d'être un caractère ou non, et comment vous travaillez avec elle, différentes approches peuvent être plus rapide.
(je fait une erreur dans mon programme plus tôt, je ne mesure pas pour chaque style de routine les mêmes opérations. Je mis à jour le lien pastebin et les résultats de référence.)
Delphi compile le code très efficace; dans mon expérience, il était très difficile de faire mieux en assembleur.
Je pense que vous devriez juste signaler un PChar (ils existent encore, ne le font pas, ils se sont séparés, je Delphi autour de 4,0?) Au début de la chaîne et l'incrémenter tout en comptant « | » s, jusqu'à ce que vous avez trouvé n-1 d'entre eux. Je pense que ce sera plus rapide que d'appeler PosEx à plusieurs reprises.
Prenez note de cette position, puis incrémenter le pointeur un peu plus jusqu'à ce que vous appuyez sur le tuyau suivant. Sortez votre sous-chaîne. Fait.
Je ne devine, mais je ne serais pas surpris si cela était proche du plus rapide ce problème peut être résolu.
EDIT: Voici ce que j'avais à l'esprit. Ce code est, hélas, non compilé et non testé, mais il doit démontrer ce que je voulais dire.
En particulier, Delim est traité comme un seul char, que je crois en fait un monde de différence si cela est conforme aux exigences, et le caractère à pline est testé une seule fois. Enfin, il n'y a pas de comparaison plus contre TokenNum; Je crois qu'il est plus rapide de décrémenter un compteur à 0 pour compter délimiteurs.
function GetTok(const Line: string; const Delim: string; const TokenNum: Byte): string;
var
Del: Char;
PLine, PStart: PChar;
Nth, I, P0, P9: Integer;
begin
Del := Delim[1];
Nth := TokenNum + 1;
P0 := 1;
P9 := Line.length + 1;
PLine := PChar(line);
for I := 1 to P9 do begin
if PLine^ = Del then begin
if Nth = 0 then begin
P9 := I;
break;
end;
Dec(Nth);
if Nth = 0 then P0 := I + 1
end;
Inc(PLine);
end;
if (Nth <= 1) or (TokenNum = 1) then
Result := Copy(Line, P0, P9 - P0);
else
Result := ''
end;
L'utilisation assembleur serait un micro-optimisation. Il y a des gains beaucoup plus à avoir en optimisant l'algorithme. Ne pas faire des beats de travail à faire dans le travail le plus rapidement possible, à chaque fois.
Un exemple serait si vous avez des endroits dans votre programme où vous avez besoin de plusieurs jetons de la même ligne. Une autre procédure qui retourne un tableau de jetons que vous pouvez ensuite indexer devrait être plus rapide que d'appeler votre fonction plus d'une fois, en particulier si vous laissez la procédure ne retourne tous les jetons, mais seulement autant que vous avez besoin.
Mais en général, je suis d'accord avec la réponse de Carl (1), en utilisant un PChar pour la numérisation serait probablement plus rapide que votre code actuel.
Ceci est une fonction que j'ai eu dans ma bibliothèque personnelle pour un certain temps que je l'utilise abondamment. Je crois que c'est la version la plus récente de celui-ci. J'ai eu plusieurs versions dans le passé sont optimisés pour une variété de raisons différentes. Celui-ci tente de prendre en compte les chaînes entre guillemets, mais si ce code est supprimé, il fait la fonction légèrement plus vite.
J'ai en fait un certain nombre d'autres routines, CountSections et ParseSectionPOS étant quelques exemples.
Unfortuately cette routine est ansi / pchar basée uniquement. Bien que je ne pense pas qu'il serait difficile de le déplacer vers unicode. Peut-être que je l'ai déjà fait ... Je vais devoir vérifier.
Note:. Cette routine est 1 basée dans l'indexation de ParseNum
function ParseSection(ParseLine: string; ParseNum: Integer; ParseSep: Char; QuotedStrChar:char = #0) : string;
var
wStart, wEnd : integer;
wIndex : integer;
wLen : integer;
wQuotedString : boolean;
begin
result := '';
wQuotedString := false;
if not (ParseLine = '') then
begin
wIndex := 1;
wStart := 1;
wEnd := 1;
wLen := Length(ParseLine);
while wEnd <= wLen do
begin
if (QuotedStrChar <> #0) and (ParseLine[wEnd] = QuotedStrChar) then
wQuotedString := not wQuotedString;
if not wQuotedString and (ParseLine[wEnd] = ParseSep) then
begin
if wIndex=ParseNum then
break
else
begin
inc(wIndex);
wStart := wEnd+1;
end;
end;
inc(wEnd);
end;
result := copy(ParseLine, wStart, wEnd-wStart);
if (length(result) > 0) and (QuotedStrChar <> #0) and (result[1] = QuotedStrChar) then
result := AnsiDequotedStr(result, QuotedStrChar);
end;
end; { ParseSection }
Dans votre code, je pense que c'est la seule ligne qui peut être optimisé:
Result := copy(Line, P+1, MaxInt)
Si vous calculez la nouvelle longueur là, il pourrait être un peu plus rapide, mais pas les 10% que vous recherchez.
Votre algorithme tokenizing semble assez OK. Pour l'optimiser, je courrais à travers un profileur (comme AQtime de AutomatedQA) avec sous-ensemble représentatif de vos données de production. Cela vous pointer vers le point le plus faible.
La seule fonction RTL qui se rapproche à celui-ci est dans l'unité des classes:
procedure TStrings.SetDelimitedText(const Value: string);
Il tokenizes, mais utilise à la fois QuoteChar et délimiteur , mais vous utilisez uniquement un délimiteur.
Il utilise le SetString fonction dans l'unité de système qui est un moyen assez rapide pour définir le contenu d'une chaîne basée sur un PChar / PAnsiChar / PUnicodeChar et une longueur.
Cela pourrait vous obtenir une certaine amélioration aussi bien; d'autre part, Copier est très rapide aussi.
Je ne suis pas la personne blâmer toujours l'algorithme, mais si je regarde la première partie de la source, le problème est que pour la chaîne N, vous faites le POS / posexes pour chaîne 1..n-1 à nouveau aussi.
Cela signifie pour les éléments N, vous somme (n, n-1, n-2 ... 1) Poses (= + / - 0,5 * N ^ 2)., Alors que seulement N sont nécessaires
Si vous mettez en cache simplement la position du dernier résultat trouvé, par exemple dans un enregistrement qui est passé par le paramètre VAR, vous pouvez gagner beaucoup.
type
TLastPosition = record
elementnr: nombre entier; // dernière tokennumber
elementpos: nombre entier; // index de caractère de dernier match
fin;
et puis quelque chose
si tokennum = (lastposition.elementnr + 1), puis commencer newpos: = posex (delim, ligne, lastposition.elementpos); fin;
Malheureusement, je n'ai pas le temps de l'écrire, mais j'espère que vous avez l'idée
