Esiste un GetToken routine veloce per Delphi?
https://stackoverflow.com/questions/1694001
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Nel mio programma, ho elaborare milioni di stringhe che hanno un carattere speciale, ad esempio, "|" per separare i token all'interno di ogni 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 quando ero con Delphi 4. Si chiama la routine PosEx molto efficiente che è stato originariamente sviluppato da FASTCODE ed è ora incluso nella libreria StrUtils di Delfi.
Recentemente ho aggiornato a Delphi 2009 e le mie corde sono tutti Unicode. Questa funzione GetTok funziona ancora e funziona ancora bene.
Ho passato con le nuove librerie di Delphi 2009 e ci sono molte nuove funzioni e aggiunte ad esso.
Ma non ho visto una funzione GetToken come ho bisogno in una qualsiasi delle nuove librerie Delphi, nei vari progetti FASTCODE, e non riesco a trovare nulla con una ricerca su Google diverso da di Zarko Gajic:. Funzioni Delphi Split / Tokenizer , che non è così ottimizzato come quello che ho già
Qualsiasi miglioramento, anche il 10% sarebbe evidente nel mio programma. So che un'alternativa è StringLists e per mantenere sempre i gettoni separano, ma questo ha un grande sovraccarico della memoria-saggio e non sono sicuro se ho fatto tutto quel lavoro per convertire se sarebbe più veloce.
Accidenti. Così, dopo tutto questo parlare a lungo senza fiato, la mia domanda è in realtà:
Sapete di eventuali implementazioni molto rapide di una routine GetToken? Una versione ottimizzata assemblatore sarebbe l'ideale?
In caso contrario, ci sono ottimizzazioni che si può vedere nel mio codice di cui sopra che potrebbe rendere un miglioramento?
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 ancora pensato a mia routine GetTok che non è stato utilizzato per il letto o che l'analisi. E 'solo ora che ho visto la testa della mia routine GetTok che mi ha portato a questa domanda. Fino a quando Carl Smotricz e le risposte di Barry, non avevo mai pensato di collegare i due. Così ovvio, ma semplicemente non registrati. Grazie per la segnalazione.
Sì, il mio delim è un singolo carattere, quindi ovviamente ho qualche importante di ottimizzazione 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 pezzetti 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. Poi vi posterò i risultati.
Confusione:. Okay, 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 messo entrambe le routine per il compito e utilizzato AQTime per vedere cosa sta succedendo. La corsa mi aveva incluso 1,108,514 chiamate a GetTok.
AQTime cronometrato la routine originale a 0.40 secondi. Il milione di chiamate al Pos completa in 0.10 secondi. Un mezzo milione di copie TokenNum = 1 0.10 secondi. Il 600.000 PosEx chiamate preso solo 0,03 secondi.
Poi ho cronometrato la mia nuova routine con AQTime per lo stesso periodo e esattamente le stesse chiamate. AQTime riferisce che la mia nuova routine "veloce" ha preso 3,65 secondi, che è 9 volte più a lungo. Il colpevole in base alla AQTime è stato il primo ciclo:
while (PLine^ <> #0) and (PLine^ <> Delim) do
inc(PLine);
La linea po ', che è stato eseguito 18 milioni di volte, è stata riportata a 2.66 secondi. La linea inc, eseguito 16 milioni di volte, è stato detto di prendere 0,47 secondi.
Ora credevo di sapere cosa stava succedendo qui. Ho avuto un problema simile con AQTime in una domanda che ho posto l'anno scorso: Perché CharInSet più veloce di istruzione Case?
Ancora una volta è stato Barry Kelly che mi risparmiandoci in. In sostanza, un profiler strumentazione come AQTime dOES non necessariamente fare il lavoro per microoptimization. Si aggiunge un sovraccarico per ogni linea che possono sommergere i risultati quali è illustrato chiaramente in questi numeri. I 34 milioni di linee eseguiti nel mio nuovo "codice ottimizzato" sopraffare i diversi milioni di righe di codice originale il mio, a quanto pare con poca o nessuna testa dalla routine Pos e PosEx.
Barry mi ha dato un esempio di codice utilizzando QueryPerformanceCounter per controllare che aveva ragione, e in quel caso era.
Va bene, quindi cerchiamo di fare lo stesso ora con QueryPerformanceCounter per dimostrare che la mia nuova routine è più veloce e non 9 volte più lento in quanto AQTime dice che è. 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 al GetTok.
La mia vecchia procedura con le chiamate Pos e PosEx ha preso 0,29 secondi. La nuova con PChars ha preso 2,07 secondi.
Ora sono completamente confuso! Qualcuno può dirmi il motivo per cui la procedura PChar non è solo più lento, ma è da 8 a 9 volte più lento!?
Mistero risolto! Andreas ha detto nella sua risposta a modificare il parametro delim da una stringa a un Char. Sarò sempre utilizzando solo un Char, così almeno per la mia implementazione questo è molto possibile. Sono rimasto stupefatto quello che è successo.
Il tempo per il 1 milione di chiamate è sceso da 1,88 secondi a .22 secondi.
E sorprendentemente, il tempo per la mia routine originale Pos / PosEx è passato da 0,29 a 0,44 secondi quando ho cambiato è il parametro delim ad un Char.
Francamente, sono deluso da ottimizzatore di Delphi. Che delim è un parametro costante. L'ottimizzatore dovrebbe aver notato che la stessa conversione sta accadendo all'interno del ciclo e avrebbe dovuto spostato in modo che sarebbe stato fatto solo una volta.
Doppia controllare i miei parametri di generazione di codice, sì, devo Ottimizzazione formato Vero e String controllando fuori.
La linea di fondo è che la nuova routine PChar con la correzione di Andrea è di circa il 25% più veloce rispetto al mio originale (0,22 contro 0,29).
ho ancora voglia di follow-up sugli altri commenti qui e testare.
Disattivare l'ottimizzazione e l'accensione formato stringa controllando solo aumenta il tempo di 0,22-0,30. Si aggiunge circa lo stesso a quello originale.
Il vantaggio di utilizzare codice assembler, o chiamando routine scritte in assembler come Pos o PosEx è che essi non sono soggetti a quale codice opzioni di generazione è stata impostata. Saranno sempre eseguito nello stesso modo, un modo pre-ottimizzato e non gonfio.
Ho ribadito negli ultimi due giorni, che il modo migliore per confrontare il codice per microoptimization è quello di esaminare e confrontare il codice Assembler nella finestra di CPU. Sarebbe bello se Embarcadero potrebbe fare quella finestra un po 'più comodo, e ci permettono di copiare parti negli appunti o per stampare le sezioni di esso.
Inoltre, ho ingiustamente sbattuto AQTime precedenza in questo post, pensando che il tempo in più aggiunto per la mia nuova routine è stato solo a causa della strumentazione ha aggiunto. Ora che torno a controllare con il parametro Char invece di stringa, il ciclo while è giù per .30 secondi (da 2.66) e la linea inc è giù per .14 secondi (da 0,47). Strano che la linea inc andrebbe giù pure. Ma sto sta logorato da tutto questo test già.
Ho preso l'idea di Carlo di looping da personaggi, e riscritto che il codice con questa idea. Si fa un altro miglioramento, fino a .19 secondi da 0,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;
Non 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 che, sono felice ora.
Grazie ancora per la comunità StackOverflow Delphi.
Soluzione
La vostra nuova funzione (quello con PChar) dovrebbe dichiarare "delim", come Char e non come Stringa . Nell'implementazione corrente il compilatore deve convertire il PLinea ^ char in una stringa per confrontarlo con il "delim". E ciò accade in un loop stretto risultante è un enorme calo 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 }
Altri suggerimenti
Si fa una grande differenza che cosa "delim" dovrebbe essere. Se si è aspettato di essere un singolo carattere, sei molto meglio fare un passo attraverso il personaggio stringa di caratteri, idealmente attraverso un PChar, e test specifico.
Se si tratta di una lunga serie, Boyer-Moore e ricerche simili hanno una fase di set-up per le tabelle di salto, e il modo migliore sarebbe quello di costruire le tabelle, una volta, e riutilizzarli per ogni ritrovamento successiva. Questo significa che è necessario lo stato tra le chiamate, e questa funzione sarebbe meglio come un metodo su un oggetto, invece.
Potreste essere interessati a questa risposta che ho dato a una domanda un po 'di tempo prima, circa il modo più veloce per analizzare una linea in Delphi. (ma vedo che è lei che ha fatto la domanda! Tuttavia, nel risolvere il tuo problema, lo farei strappare a come ho descritto parsing, non utilizzando PosEx come si sta utilizzando, a seconda di ciò delim appare normalmente come.)
Aggiorna : OK, ho trascorso circa 40 minuti guardando questo. Se si conosce il delimitatore sta per essere un personaggio, sei praticamente sempre meglio con la seconda versione (la scansione cioè PChar), ma si deve passare Delim come personaggio. Al momento della scrittura, si sta convertendo l'espressione PLine^ - di tipo Char - in una stringa per il confronto con delim. Che sarà molto lenta; anche indicizzazione nella stringa, con Delim[1] sarà anche un po 'lento.
Tuttavia, a seconda di come grande le linee sono, e quanti pezzi delimitato si vuole tirare fuori, si potrebbe essere meglio con un approccio resumable, piuttosto che saltare pezzi delimitati indesiderate all'interno della routine di creazione di token. Se si chiama GetTok con gli indici in successione crescente, come si sta facendo nel vostro mini punto di riferimento, ci si ritroverà con la O (n * n) le prestazioni, dove n è il numero di sezioni delimitate. Che può essere trasformato in O (n) se si salva lo stato della scansione e ripristinare per l'iterazione successiva, o imballare tutti gli elementi estratti in un array.
Ecco una versione che fa tutto tokenizzazione una volta, e restituisce un array. Ha bisogno di tokenize due volte, però, al fine di sapere come grande per fare la matrice. D'altra parte, solo il secondo 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 resumable. 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;
Ecco il programma completo che ho usato per il 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, diversi approcci possono essere più veloce.
(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.)
Delphi viene compilato in codice molto efficiente; nella mia esperienza, è stato molto difficile fare di meglio in assembler.
Credo che si dovrebbe semplicemente indicare un PChar (esistono ancora, non è vero mi separai modi con Delphi intorno 4.0?) All'inizio della stringa e incrementarlo, mentre il conteggio "|" s, fino a quando hai trovato n-1 di loro. Ho il sospetto che sarà più veloce di chiamare ripetutamente PosEx.
Prendere nota di tale posizione, quindi incrementare il puntatore ancora un po 'fino a colpire il tubo successivo. Tirare fuori la tua stringa. Fatto.
Sono solo indovinando, ma non sarei sorpreso se questo era vicino il più veloce questo problema può essere risolto.
Modifica Ecco quello che avevo in mente. Questo codice è, ahimè, non compilato e non testato, ma dovrebbe dare prova di quello che volevo dire.
In particolare, delim viene trattato come un singolo carattere, che a mio avviso fa un mondo di differenza, se in grado di soddisfare i requisiti, e il carattere PLinea è testato solo una volta. Infine, non c'è più confronto con TokenNum; Credo che sia più veloce per decrementare un contatore a 0 per il conteggio 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;
Utilizzando assemblatore sarebbe un micro-ottimizzazione. Ci sono molto maggiori guadagni per essere avuto ottimizzando l'algoritmo. Non fare battute di lavoro facendo un lavoro nel modo più veloce possibile, ogni volta.
Un esempio potrebbe essere se si dispone di posti nel programma in cui è necessario diversi gettoni della stessa linea. Un'altra procedura che restituisce un array di token che è quindi possibile indicizzare dovrebbe essere più veloce di chiamare la funzione più di una volta, soprattutto se si lascia che la procedura non restituisce tutti i token, ma solo come di cui hai bisogno.
Ma in generale sono d'accordo con la risposta di Carl (+1), utilizzando un PChar per la scansione sarebbe probabilmente più veloce del codice corrente.
Questa è una funzione che ho avuto nella mia biblioteca personale per un bel po 'di tempo che uso ampiamente. Credo che questa è la versione più recente di esso. Ho avuto più versioni in passato di essere ottimizzati per una serie di ragioni diverse. Questo si cerca di tener conto Citato stringhe, ma se questo codice viene rimosso rende la funzione di un leggero po 'più veloce.
Io in realtà sono un certo numero di altre routine, CountSections e ParseSectionPOS che sono un paio di esempi.
Unfortuately questa routine è ANSI / PChar solo in base. Anche se io non credo che sarebbe difficile spostarlo in unicode. Forse ho già fatto ... dovrò controllare questo.
. Nota: Questa routine si basa 1 nell'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 }
Nel codice, penso che questa è l'unica linea che può essere ottimizzata:
Result := copy(Line, P+1, MaxInt)
Se si calcola la nuova lunghezza lì, si potrebbe ottenere un po 'più veloce, ma non il 10% che si sta cercando.
Il tuo algoritmo di creazione di token sembra abbastanza OK. Per ottimizzare, avrei gestito attraverso un profiler (come AQTime da AutomatedQA) con sottoinsieme rappresentativo dei dati di produzione. Che vi puntare al punto più debole.
L'unica funzione RTL che si avvicina è presente uno nell'unità classi:
procedure TStrings.SetDelimitedText(const Value: string);
E 'tokenizza, ma utilizza entrambe le quotechar e delimitatore , ma si usa solo un delimitatore.
Si utilizza il SetString funzione nell'unità di sistema che è un modo molto veloce per impostare il contenuto di una stringa basata su un PChar / PAnsiChar / PUnicodeChar lunghezza.
Questo potrebbe ottenere qualche miglioramento pure; d'altra parte, Copia è veramente veloce troppo.
Io non sono la persona accusando sempre l'algoritmo, ma se guardo il primo pezzo della fonte, il problema è che per la stringa N, si fanno le POS / posexes per la stringa 1..n-1 ancora una volta troppo.
Questo significa per N elementi, si fa sum (n, n-1, n-2 ... 1) pone (= + / - 0.5 * N ^ 2)., Mentre solo N sono necessari
Se semplicemente in cache la posizione dell'ultimo risultato trovato, ad esempio, in un record che viene passato dal parametro VAR, è possibile ottenere un sacco.
digitare
TLastPosition = record di
elementnr: integer; // ultima tokennumber
elementpos: integer; // indice di carattere di ultimo match
fine;
e poi qualcosa
se tokennum = (lastposition.elementnr + 1) allora inizio newPos: = posex (DELIM, linea, lastposition.elementpos); fine;
Purtroppo, non ho il tempo di scrivere fuori, ma spero che l'idea
