Esiste una routine veloce GetToken per Delphi?

Question

Nel mio programma, elaboro milioni di stringhe che hanno un carattere speciale, ad es. "|" per separare i token all'interno di ciascuna stringa. Ho una funzione per restituire il token n'th, e questo è esso:

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 } 

ho sviluppato questa funzione indietro quando stavo usando Delphi 4. Si chiama la routine PosEx molto efficiente che è stato originariamente sviluppato da FASTCODE e è ora incluso nella libreria StrUtils di Delphi.

Recentemente ho aggiornato a Delphi 2009 e le mie stringhe sono tutte Unicode. Questa funzione GetTok funziona ancora e funziona ancora bene.

Ho passato le nuove librerie in Delphi 2009 e ci sono molte nuove funzioni e aggiunte ad esso.

Ma non ho visto una funzione GetToken come ho bisogno in nessuna delle nuove librerie Delphi, nei vari progetti fastcode, e non riesco a trovare nulla con una ricerca su Google diversa da Zarko Gajic's: Delphi Split/Tokenizer Functions, che non è così ottimizzata come quello che ho già.

Qualsiasi miglioramento, anche il 10% sarebbe evidente nel mio programma. So che un'alternativa è StringList e tenere sempre separati i token, ma questo ha un grande overhead di memoria e non sono sicuro di aver fatto tutto il possibile per convertire se sarebbe stato più veloce.

Whew. Quindi, dopo tutto questo lungo colloquio, la mia domanda è davvero:

Sai qualche implementazione molto veloce di una routine GetToken? Una versione ottimizzata per assemblatori sarebbe l'ideale?

In caso contrario, ci sono ottimizzazioni che è possibile vedere nel mio codice sopra che potrebbero migliorare?

---

ollowup: Barry Kelly citato una domanda ho chiesto un anno fa su come ottimizzare l'analisi delle linee in un file. A quel tempo non avevo nemmeno pensato alla mia routine GetTok che non era usata per quella lettura o analisi. Solo ora ho visto il sovraccarico della mia routine GetTok che mi ha portato a fare questa domanda. Fino alle risposte di Carl Smotricz e Barry, non avevo mai pensato di collegare i due. Così ovvio, ma non è stato registrato. Grazie per la segnalazione.

Sì, il mio Delim è un singolo carattere, quindi ovviamente ho qualche ottimizzazione importante che posso fare. Il mio uso di Pos e PosEx nella routine GetTok (sopra) mi ha accecato l'idea che posso farlo più velocemente con un carattere di ricerca di carattere, invece, con i pezzi di codice come:

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

ho intenzione di passare attraverso le risposte di tutti e provare i vari suggerimenti e confrontarli. Quindi posterò i risultati.

---

Confusione: Ok, ora sono davvero perplesso.

ho preso Carl e Barry di raccomandazione per andare con PChars, e qui è la mia realizzazione:

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 } 

Sulla carta, non credo che si può fare molto meglio di questo.

Così ho inserito entrambe le routine nell'attività e ho utilizzato AQTime per vedere cosa sta succedendo.Nella corsa che avevo incluso 1,108,514 chiamate a GetTok.

AQTime ha programmato la routine originale a 0,40 secondi. Il milione di chiamate a Pos ha richiesto 0,10 secondi. Mezzo milione di TokenNum = 1 copie ha richiesto 0,10 secondi. Le 600.000 chiamate PosEx hanno richiesto solo 0,03 secondi.

Poi ho programmato la mia nuova routine con AQTime per la stessa esecuzione e esattamente le stesse chiamate. AQTime riporta che la mia nuova routine "veloce" ha richiesto 3.65 secondi, ovvero 9 volte di più. Il colpevole secondo AQTime stato il primo ciclo:

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

La linea mentre, che è stata eseguita 18 milioni di volte, è stato segnalato in 2,66 secondi. Si dice che la linea inc, eseguita 16 milioni di volte, impieghi 0,47 secondi.

Ora pensavo di sapere cosa stava succedendo qui. Ho avuto un problema simile con AQTime in una domanda che ho posto l'anno scorso:. Why is CharInSet faster than Case statement?

Ancora una volta è stato Barry Kelly che mi risparmiandoci in sostanza, un profiler strumentazione come AQTime non necessariamente fare il lavoro per microoptimization. Aggiunge un overhead ad ogni linea che può sommergere i risultati che è mostrato chiaramente in questi numeri. Le 34 milioni di linee eseguite nel mio nuovo "codice ottimizzato" sommergono le diverse milioni di righe del mio codice originale, con un sovraccarico apparentemente piccolo o nullo delle routine Pos e PosEx.

Barry mi ha fornito un esempio di codice utilizzando QueryPerformanceCounter per verificare che fosse corretto, e in tal caso lo era.

Ok, quindi facciamo lo stesso ora con QueryPerformanceCounter per dimostrare che la mia nuova routine è più veloce e non 9 volte più lenta come AQTime dice che lo è. Così qui vado:

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; 

Quindi questo metterà alla prova 1.000.000 chiamate a GetTok.

La mia vecchia procedura con le chiamate Pos e PosEx ha richiesto 0,29 secondi. Il nuovo con PChars ha impiegato 2,07 secondi.

Ora sono completamente confuso! Qualcuno può dirmi perché la procedura PChar non è solo più lenta, ma è da 8 a 9 volte più lenta !?

---

Mistero risolto! Andreas ha detto nella sua risposta di cambiare il parametro Delim da una stringa a un Char. Userò sempre solo un Char, quindi almeno per la mia implementazione è molto possibile. Sono rimasto sbalordito da ciò che è successo.

Il tempo per 1 milione di chiamate è diminuito da 1,88 secondi a 0,22 secondi.

E sorprendentemente, il tempo per la mia procedura Pos/Posex originale è passato da 0,29 a 44 secondi quando ho cambiato il parametro Delim in Char.

Francamente, sono deluso dall'ottimizzatore di Delphi. Quel Delim è un parametro costante. L'ottimizzatore dovrebbe aver notato che la stessa conversione sta avvenendo all'interno del ciclo e dovrebbe averla spostata in modo che fosse eseguita una sola volta.

Doppio controllo dei parametri di generazione del codice, sì, ho Ottimizzazione True e Controllo formato stringa disattivato.

La linea di fondo è che la nuova routine PChar con la correzione di Andrea è circa il 25% più veloce del mio originale (0,22 contro 0,29).

Desidero continuare a seguire gli altri commenti qui e testarli.

---

Disattivare l'ottimizzazione e attivare la verifica del formato stringa aumenta solo il tempo da .22 a .30. Aggiunge all'incirca lo stesso all'originale.

Il vantaggio di utilizzare il codice assembler o le routine di chiamata scritte nell'assembler come Pos o PosEx è che NON sono soggette alle opzioni di generazione del codice impostate. Funzioneranno sempre allo stesso modo, in modo pre-ottimizzato e non gonfiato.

Ho riaffermato negli ultimi due giorni che il modo migliore per confrontare il codice per la microottimizzazione è quello di esaminare e confrontare il codice Assembler nella finestra della CPU. Sarebbe bello se Embarcadero potesse rendere la finestra un po 'più comoda e consentirci di copiare parti negli Appunti o di stamparne delle sezioni.

Inoltre, ingiustamente ho sbattuto AQTime in precedenza in questo post, pensando che il tempo extra aggiunto per la mia nuova routine era esclusivamente a causa della strumentazione aggiunta. Ora che torno indietro e controllo il parametro Char invece di String, il ciclo while è inferiore a .30 secondi (da 2.66) e la linea inc è inferiore a .14 secondi (da .47). Strano che anche la linea inc entrerebbe. Ma mi sto già stancando da tutti questi test.

---

Ho preso l'idea di Carl di eseguire il ciclo dei caratteri e ho riscritto quel codice con quell'idea. Fa un altro miglioramento, fino a .19 secondi da .22. Così qui è ora il migliore finora:

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; 

Ci può essere ancora alcune ottimizzazioni minori a questo, come ad esempio il confronto CurToken = Tokennum, che dovrebbe essere dello stesso tipo, Integer o byte, a seconda di quale è più veloce.

Ma diciamo, sono felice ora.

Grazie ancora alla comunità Delphi di StackOverflow.

Answer 1

tua nuova funzione (quello con PChar) deve dichiarare "Delim" come Char e non come String. Nella tua attuale implementazione il compilatore deve convertire il carattere^PLine in una stringa per confrontarlo con "Delim". E ciò accade in un ciclo stretto risultante in un enorme successo di prestazioni.

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 viene compilato con codice MOLTO efficiente; nella mia esperienza, è stato molto difficile fare meglio in assembler.

Penso che dovresti puntare un PChar (esistono ancora, non è così? Ho diviso i modi con Delphi attorno a 4.0) all'inizio della stringa e lo incremento mentre conteggio "|" s, finché non hai trovato n-1 di loro. Ho il sospetto che sarà più veloce di chiamare PosEx ripetutamente.

Prendere nota di quella posizione, quindi aumentare ulteriormente il puntatore fino a quando non si preme il tubo successivo. Estrai la tua sottostringa. Fatto.

Sto solo indovinando, ma non sarei sorpreso se questo fosse il più vicino possibile a risolvere questo problema.

MODIFICA: Ecco cosa avevo in mente. Questo codice è, purtroppo, non compilato e non testato, ma dovrebbe dimostrare cosa intendevo.

In particolare, Delim viene considerato come un singolo carattere, il che credo crei un mondo di differenza se soddisferà i requisiti e il carattere su PLine verrà testato una sola volta. Infine, non c'è più confronto con TokenNum; Credo che sia più rapido decrementare un contatore a 0 per contare i delimitatori.

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

Utilizzare l'assemblatore sarebbe una micro-ottimizzazione. Ci sono guadagni molto maggiori da ottenere ottimizzando l'algoritmo. Non fare battute di lavoro facendo il lavoro nel modo più veloce possibile, sempre.

Un esempio potrebbe essere se nel proprio programma ci sono posti in cui sono necessari più token della stessa linea. Un'altra procedura che restituisce una serie di token che è possibile quindi indicizzare dovrebbe essere più veloce di chiamare la funzione più di una volta, soprattutto se si lascia che la procedura non restituisca tutti i token, ma solo quanti ne occorrono.

Ma in generale sono d'accordo con la risposta di Carl (+1), utilizzando uno PChar per la scansione sarebbe probabilmente più veloce del codice corrente.

Answer 4

Questa è una funzione che ho avuto nella mia libreria personale per un po 'di tempo che uso estesamente. Credo che questa sia la versione più attuale. In passato ho avuto più versioni ottimizzate per svariati motivi. Questo tenta di prendere in considerazione le stringhe citate, ma se quel codice viene rimosso rende la funzione leggermente più veloce.

In realtà ho un numero di altre routine, CountSections e ParseSectionPOS che sono un paio di esempi.

Sfortunatamente questa routine è basata solo su ansi/pchar. Anche se non penso che sarebbe difficile spostarlo in unicode. Forse l'ho già fatto ... dovrò controllarlo.

Nota: questa routine è 1 basata sull'indicizzazione 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

Nel codice, penso che questa è l'unica linea che può essere ottimizzato:

Result := copy(Line, P+1, MaxInt) 

Se si calcola la nuova lunghezza lì, si potrebbe ottenere un po 'più veloce, ma non il 10% stai cercando.

L'algoritmo di tokenizzazione sembra abbastanza buono. Per ottimizzarlo, vorrei eseguirlo attraverso un profiler (come AQTime da AutomatedQA) con un sottoinsieme rappresentativo dei dati di produzione. Questo ti indicherà il punto più debole.

L'unica funzione di RTL che si avvicina è questo uno nell'unità Classi:

procedure TStrings.SetDelimitedText(const Value: string); 

E tokenizza, ma utilizza sia quotechar e delimitatore, ma si usa solo un delimitatore.

Utilizza la funzione SetString nell'unità di sistema che è un modo piuttosto veloce per impostare il contenuto di una stringa in base a un PChar/PAnsiChar/PUnicodeChar e una lunghezza.

Questo potrebbe farti un po 'di miglioramento; d'altra parte, Copia è anche molto veloce.

Answer 6

Fa una grande differenza ciò che "Delim" dovrebbe essere. Se si prevede che sia un singolo personaggio, è molto meglio passare attraverso la stringa carattere per carattere, idealmente attraverso un PChar, e testare specificamente.

Se è una stringa lunga, Boyer-Moore e ricerche simili hanno una fase di impostazione per saltare le tabelle e il modo migliore sarebbe quello di costruire le tabelle una volta e riutilizzarle per ogni ricerca successiva. Ciò significa che è necessario lo stato tra le chiamate e questa funzione sarebbe preferibile come metodo su un oggetto.

Potreste essere interessati a this answer I gave to a question some time before, about the fastest way to parse a line in Delphi. (ma vedo che è lei che ha fatto la domanda! Tuttavia, nel risolvere il tuo problema, vorrei strappare a come ho descritto l'analisi, non utilizzando PosEx come si sta utilizzando, a seconda su ciò che normalmente delim assomiglia)

---

UPDATE:. OK, ho trascorso circa 40 minuti guardando questo. Se sai che il delimitatore sarà un personaggio, stai quasi sempre meglio con la seconda versione (cioè la scansione PChar), ma devi passare Delim come personaggio. Al momento della scrittura, stai convertendo l'espressione PLine^ - di tipo Char - in una stringa per il confronto con Delim. Sarà molto lento; anche l'indicizzazione nella stringa, con Delim[1] sarà anche un po 'lento.

Tuttavia, a seconda dell'ampiezza delle linee e del numero di pezzi delimitati che si desidera estrarre, è possibile che si stia procedendo meglio con un approccio di ripristino, anziché saltare pezzi delimitati indesiderati all'interno della routine di tokenizzazione. Se chiami GetTok con indici che aumentano progressivamente, come fai attualmente nel tuo mini benchmark, finirai con il rendimento di O (n * n), dove n è il numero di sezioni delimitate. Questo può essere trasformato in O (n) se si salva lo stato della scansione e lo si ripristina per l'iterazione successiva o si comprimono tutti gli elementi estratti in una matrice.

Ecco una versione che esegue tutte le tokenizzazione una volta e restituisce un array. Deve comunque tokenize due volte, per sapere quanto è grande per fare la matrice. D'altra parte, solo la seconda tokenizzazione deve estrarre le stringhe:

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

Ecco l'approccio riassumibile. I carichi e negozi della posizione e delimitatore corrente carattere hanno un costo, però:

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.

Ecco i risultati:

*** 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 

A seconda delle caratteristiche dei dati, se il delimitatore è probabile che sia un personaggio o no, e come si lavora con esso, approcci diversi possono essere più veloci.

(ho fatto un errore nel mio programma prima, non stava misurando le stesse operazioni per ogni stile di routine. Ho aggiornato il link pastebin e risultati dei benchmark.)

Answer 7

Io non sono la persona sempre incolpando l'algoritmo, ma se guardo il primo pezzo della fonte, il problema è che per la stringa N, si fanno le POS/posexes per 1..n stringa -1 anche di nuovo.

Ciò significa che per N elementi, si sommano (n, n-1, n-2 ... 1) POS (= +/- 0,5 * N^2), mentre sono necessari solo N.

Se si memorizza semplicemente la posizione dell'ultimo risultato trovato, ad es. in un record passato dal parametro VAR, puoi guadagnare molto.

tipo
TLastPosition = registrazione elementnr: integer; // last tokennumber elementpos: intero; // indice carattere dell'ultima corrispondenza fine;

e poi qualcosa

se tokennum = (lastposition.elementnr + 1) allora iniziare newPos: = posex (delim, linea, lastposition.elementpos); fine;

Purtroppo, non ho il tempo di scrivere fuori, ma spero che l'idea