Existe-t-il une routine GetToken rapide pour Delphi?

Question

Dans mon programme, je traite des millions de chaînes qui ont un caractère spécial, par ex. "|" séparer les jetons dans 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é initialement développé par Fastcode et est maintenant inclus dans la bibliothèque StrUtils de Delphi.

J'ai récemment mis à jour vers Delphi 2009 et mes chaînes sont toutes Unicode. Cette fonction GetTok fonctionne toujours et fonctionne toujours bien.

J'ai parcouru les nouvelles bibliothèques dans Delphi 2009 et il y a beaucoup de nouvelles fonctions et ajouts.

Mais je n'ai pas vu une fonction GetToken comme j'ai besoin dans l'une des nouvelles bibliothèques Delphi, dans les différents projets fastcode, et je ne trouve rien avec une recherche Google autre que Zarko Gajic's: Delphi Split/Tokenizer Functions, qui n'est pas aussi optimisée que ce que j'ai déjà.

Toute amélioration, même 10% serait perceptible dans mon programme. Je sais qu'une alternative est StringLists et de garder toujours les jetons séparés, mais cela a une grande surcharge de mémoire et je ne suis pas sûr si j'ai fait tout ce travail pour convertir si ce serait plus rapide.

Ouf. Donc, après toute cette longue discussion, ma question est vraiment:

Connaissez-vous des implémentations très rapides d'une routine GetToken? Une version optimisée d'assembleur serait idéale?

Sinon, y a-t-il des optimisations que vous pouvez voir dans mon code ci-dessus qui pourraient faire une amélioration? Suivi: Barry Kelly a mentionné une question que j'ai posée il y a un an sur l'optimisation de l'analyse des lignes dans un fichier. À ce moment-là, je n'avais même pas pensé à ma routine GetTok qui n'était pas utilisée pour la lecture ou l'analyse syntaxique. Ce n'est que maintenant que j'ai vu le transparent de ma routine GetTok qui m'a conduit à poser cette question. Jusqu'à la réponse de Carl Smotricz et Barry, je n'avais jamais pensé à relier les deux. Tellement évident, mais ça ne s'est pas enregistré. Merci d'avoir fait remarquer cela.

Oui, mon Delim est un seul caractère, donc évidemment j'ai une optimisation majeure 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 la recherche de caractère au lieu, avec des bouts de code comme:

 while (cp^ > #0) and (cp^ <= Delim) do  
     Inc(cp); 

Je vais parcourir les réponses de chacun et essayer les différentes suggestions et les comparer. Ensuite, je posterai les résultats.

---

Confusion: Bon, 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. J'ai donc mis 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. AQTime a chronométré la routine d'origine à 0,40 seconde. Le million d'appels à Pos a pris 0.10 secondes. Un demi-million de TokenNum = 1 copies a pris 0,10 secondes. Les 600 000 appels PosEx n'ont pris que 0,03 seconde.

Puis j'ai chronométré ma nouvelle routine avec AQTime pour le même passage et exactement les mêmes appels. AQTime rapporte que ma nouvelle routine "rapide" a pris 3,65 secondes, ce qui est 9 fois plus long. Le coupable selon AQtime a été la première boucle:

 while (PLine^ <> #0) and (PLine^ <> Delim) do 
     inc(PLine); 

La ligne de temps, qui a été exécuté 18 millions de fois, a été rapportée à 2.66 secondes. La ligne inc, exécutée 16 millions de fois, aurait pris 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 j'ai posée l'année dernière: Why is CharInSet faster than Case statement?

Encore une fois c'était Barry Kelly qui m'a clued dedans. Fondamentalement, un profileur d'instrumentation comme AQTime ne fait pas nécessairement le travail pour microoptimization. Il ajoute un surcoût à chaque ligne qui peut masquer les résultats qui sont clairement indiqués dans ces nombres. Les 34 millions de lignes exécutées dans mon nouveau "code optimisé" submergent les quelques millions de lignes de mon code original, avec apparemment peu ou pas de frais généraux des routines Pos et PosEx. Barry m'a donné un échantillon de code en utilisant QueryPerformanceCounter pour vérifier qu'il avait raison, et dans ce cas il l'était. Bon, alors faisons la même chose maintenant avec QueryPerformanceCounter pour prouver que ma nouvelle routine est plus rapide et pas 9 fois plus lente comme le dit AQTime. Alors voilà:

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; 

Cela 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 déconcerté! Quelqu'un peut-il me dire pourquoi la procédure PChar est non seulement plus lente, mais est 8 à 9 fois plus lent?

---

Mystery résolu! Andreas a dit dans sa réponse de changer le paramètre Delim d'une chaîne à un Char. Je vais toujours utiliser juste un Char, donc au moins pour ma mise en œuvre c'est très possible. J'ai été étonné de ce qui est arrivé.

La durée du 1 million d'appels est passée de 1,88 secondes à 0,22 seconde.

Et étonnamment, le temps pour ma routine Pos/PosEx d'origine est passé de .29 à .44 secondes lorsque j'ai changé son 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 dû remarquer que la même conversion se produisait dans la boucle et devrait l'avoir déplacée afin qu'elle ne soit effectuée qu'une seule fois.

Double vérification de mes paramètres de génération de code, oui j'ai Optimisation True et vérification de format chaîne désactivée.

La ligne de fond est que la nouvelle routine PChar avec la réparation d'Andrea est environ 25% plus rapide que mon original (.22 contre .29).

Je veux toujours faire un suivi sur les autres commentaires ici et les tester. La désactivation de l'optimisation et l'activation de la vérification de format de chaîne ne font qu'accroître la durée de .22 à .30. Il ajoute à peu près la même chose à l'original. L'avantage d'utiliser du code assembleur ou des routines d'appel écrites en assembleur comme Pos ou PosEx est qu'elles ne sont PAS sujettes aux options de génération de code que vous avez définies. Ils fonctionneront toujours de la même manière, de manière pré-optimisée et non-ballonnée.

J'ai réaffirmé ces derniers jours que la meilleure façon de comparer le code pour la microoptimisation est de regarder et de comparer le code assembleur dans la fenêtre CPU. Ce serait bien si Embarcadero pouvait rendre cette fenêtre un peu plus pratique, et nous permettre de copier des parties dans le presse-papiers ou d'en imprimer des sections.

En outre, j'ai injustement critiqué AQTime plus tôt dans ce post, en pensant que le temps supplémentaire ajouté pour ma nouvelle routine était uniquement à cause de l'instrumentation ajoutée. Maintenant que je reviens et que je vérifie avec le paramètre Char au lieu de String, la boucle while est à 0,30 seconde (à partir de 2,66) et la ligne inc à 0,14 seconde (à partir de 0,47). Étrange que la ligne inc descendrait aussi bien. Mais je suis déjà épuisé par tous ces tests. J'ai pris l'idée de Carl de boucler par des caractères, et ai réécrit ce code avec cette idée. Il fait une autre amélioration, jusqu'à 0,19 secondes de 0,22. Voici donc maintenant le meilleur jusqu'à présent:

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.

Answer 1

Votre nouvelle fonction (celle avec PChar) doit déclarer "Delim" comme Char et non comme Chaîne. Dans votre implémentation actuelle, le compilateur doit convertir le caractère PLine^en une chaîne pour le comparer avec "Delim". Et cela se produit dans une boucle serrée résultant en un énorme succès de 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 } 

Answer 2

Delphi compile en un code très efficace; d'après mon expérience, il était très difficile de faire mieux en assembleur.

Je pense que vous devriez juste pointer un PChar (ils existent toujours, n'est-ce pas? Je me suis séparé de Delphi autour de 4.0) au début de la chaîne et l'incrémenter en comptant "|" s, jusqu'à ce que trouvé n-1 d'entre eux. Je pense que cela sera plus rapide que d'appeler PosEx à plusieurs reprises. Prenez note de cette position, puis augmentez encore le pointeur jusqu'à ce que vous atteigniez le tuyau suivant. Retirez votre sous-chaîne. Terminé.

Je ne fais que deviner, 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 en tête. Ce code est, hélas, non compilé et non testé, mais il devrait démontrer ce que je voulais dire.

En particulier, Delim est traité comme un seul char, ce qui, je crois, fait toute la différence si cela répond aux exigences, et le caractère de PLine n'est testé qu'une seule fois. Enfin, il n'y a plus de comparaison avec TokenNum; Je crois qu'il est plus rapide de décrémenter un compteur à 0 pour compter les 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; 

Answer 3

L'utilisation de l'assembleur serait une micro-optimisation. Il y a beaucoup plus de gains à obtenir en optimisant l'algorithme. Ne pas travailler, c'est faire 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 renvoie un tableau de jetons dans lequel vous pouvez indexer devrait être plus rapide que d'appeler votre fonction plus d'une fois, surtout si vous laissez la procédure ne pas retourner tous les jetons, mais seulement autant que vous le souhaitez.

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.

Answer 4

C'est une fonction que j'ai eu dans ma bibliothèque personnelle pendant un certain temps que j'utilise beaucoup. Je crois que c'est la version la plus récente. J'ai eu plusieurs versions dans le passé étant optimisé pour une variété de raisons différentes. Celui-ci essaie de prendre en compte les chaînes de caractères Quoted, mais si ce code est supprimé, cela rend la fonction un peu plus rapide.

J'ai effectivement un certain nombre d'autres routines, CountSections et ParseSectionPOS étant un couple d'exemples.

Malheureusement cette routine est basée uniquement sur ansi/pchar. Bien que je ne pense pas qu'il serait difficile de le déplacer en unicode. Peut-être que j'ai déjà fait ça ... Je vais devoir vérifier ça.

Remarque: Cette routine est basée sur 1 dans l'indexation 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 } 

Answer 5

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% Tu recherches.

Votre algorithme de tokenizing semble plutôt correct. Pour l'optimiser, je passerais par un profileur (comme AQTime de AutomatedQA) avec un sous-ensemble représentatif de vos données de production. Cela vous dirigera vers le point le plus faible.

La seule fonction RTL qui se rapproche est celui-ci dans l'unité 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 la fonction SetString dans l'unité Système qui est un moyen très rapide de définir le contenu d'une chaîne basée sur un PChar/PAnsiChar/PUnicodeChar et une longueur.

Cela pourrait vous apporter une certaine amélioration aussi; d'autre part, Copie est vraiment rapide aussi.

Answer 6

Cela fait une grande différence sur ce que "Delim" devrait être. Si l'on s'attend à ce qu'il ne s'agisse que d'un seul personnage, il est préférable de faire défiler la chaîne caractère par caractère, idéalement via un PChar, et de tester spécifiquement.S'il s'agit d'une longue chaîne, Boyer-Moore et les recherches similaires ont une phase de configuration pour les tables de sauts, et la meilleure façon serait de construire les tables une fois, et de les réutiliser pour chaque découverte suivante. Cela signifie que vous avez besoin d'un état entre les appels, et cette fonction serait mieux comme une méthode sur un objet à la place.

Vous pourriez être intéressé par this answer I gave to a question some time before, about the fastest way to parse a line in Delphi. (Mais je vois que c'est vous qui a posé la question! Néanmoins, dans la résolution de votre problème, je hew à la façon dont je l'ai décrit l'analyse syntaxique, pas en utilisant PosEx comme vous utilisez, en fonction sur ce que Delim ressemble normalement)

---

MISE à JOUR. OK, j'ai passé environ 40 minutes à regarder cela. Si vous savez que le délimiteur va être un caractère, vous êtes à peu près toujours mieux avec la deuxième version (c'est-à-dire l'analyse PChar), mais vous devez passer Delim en tant que personnage. Au moment de l'écriture, vous convertissez l'expression PLine^ - de type Char - en une chaîne pour la comparaison avec Delim. Ce sera très lent. même l'indexation dans la chaîne, avec Delim[1] sera également un peu lent. Toutefois, en fonction de la taille de vos lignes et du nombre de pièces délimitées que vous souhaitez retirer, il est préférable d'utiliser une approche résumable plutôt que de sauter des pièces délimitées indésirables dans la routine de création de jetons. Si vous appelez GetTok avec des index successivement croissants, comme vous le faites actuellement dans votre mini-benchmark, vous obtiendrez des performances O (n * n), où n est le nombre de sections délimitées. Cela peut être transformé en O (n) si vous sauvegardez l'état de l'analyse et le restaurez pour l'itération suivante, ou empaquetez tous les éléments extraits dans un tableau.

Voici une version qui effectue tous les jetons une fois et renvoie un tableau. Il doit cependant marquer deux fois, afin de connaître la taille du tableau. D'autre part, seule la deuxième segmentation doit extraire les chaînes:

// Do all tokenization up front. 
function GetTok4(const Line: string; const Delim: Char): TArray<string>; 
var 
    cp, start: PChar; 
    count: Integer; 
begin 
    // Count sections 
    count := 1; 
    cp := PChar(Line); 
    start := cp; 
    while True do 
    begin 
    if cp^ <> #0 then 
    begin 
     if cp^ <> Delim then 
     Inc(cp) 
     else 
     begin 
     Inc(cp); 
     Inc(count); 
     end; 
    end 
    else 
    begin 
     Inc(count); 
     Break; 
    end; 
    end; 

    SetLength(Result, count); 
    cp := start; 
    count := 0; 

    while True do 
    begin 
    if cp^ <> #0 then 
    begin 
     if cp^ <> Delim then 
     Inc(cp) 
     else 
     begin 
     SetString(Result[count], start, cp - start); 
     Inc(cp); 
     Inc(count); 
     end; 
    end 
    else 
    begin 
     SetString(Result[count], start, cp - start); 
     Break; 
    end; 
    end; 
end; 

Voici l'approche résumable. Les charges et les magasins de la position actuelle et le caractère delimiter ont un coût, bien que:

type 
    TTokenizer = record 
    private 
    FSource: string; 
    FCurrPos: PChar; 
    FDelim: Char; 
    public 
    procedure Reset(const ASource: string; ADelim: Char); inline; 
    function GetToken(out AResult: string): Boolean; inline; 
    end; 

procedure TTokenizer.Reset(const ASource: string; ADelim: Char); 
begin 
    FSource := ASource; // keep reference alive 
    FCurrPos := PChar(FSource); 
    FDelim := ADelim; 
end; 

function TTokenizer.GetToken(out AResult: string): Boolean; 
var 
    cp, start: PChar; 
    delim: Char; 
begin 
    // copy members to locals for better optimization 
    cp := FCurrPos; 
    delim := FDelim; 

    if cp^ = #0 then 
    begin 
    AResult := ''; 
    Exit(False); 
    end; 

    start := cp; 
    while (cp^ <> #0) and (cp^ <> Delim) do 
    Inc(cp); 

    SetString(AResult, start, cp - start); 
    if cp^ = Delim then 
    Inc(cp); 
    FCurrPos := cp; 
    Result := True; 
end; 

Here's the full program I used for benchmarking.

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, les différentes approches peuvent être plus rapides.

(je fait une erreur dans mon programme plus tôt, je ne mesure pas les mêmes opérations pour chaque style de routine. Je mis à jour le lien pastebin et les résultats de référence.)

Answer 7

Je ne suis pas la personne qui blâme 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 la chaîne 1..n -1 encore une fois aussi. Cela signifie que pour N éléments, vous faites sum (n, n-1, n-2 ... 1) POSes (= +/- 0.5 * N^2), alors que N sont nécessaires.

Si vous mettez simplement en cache la position du dernier résultat trouvé, par ex. dans un enregistrement qui est passé par le paramètre VAR, vous pouvez gagner beaucoup.

type
TLastPosition = enregistrement elementnr: nombre entier; // last tokennumber elementpos: entier; // index des caractères du dernier match end;

et puis quelque chose

si tokennum = (lastposition.elementnr + 1) puis commence 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