Qual è il modo più veloce per analizzare una linea in Delphi?
https://stackoverflow.com/questions/287789
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho un file enorme che devo analizzare riga per riga. La velocità è essenziale.
Esempio di linea:
Token-1 Here-is-the-Next-Token Last-Token-on-Line ^ ^ Current Position Position after GetToken
Viene chiamato GetToken, che restituisce " Here-is-the-Next-Token " e imposta CurrentPosition sulla posizione dell'ultimo carattere del token in modo che sia pronto per la chiamata successiva a GetToken. I token sono separati da uno o più spazi.
Supponiamo che il file sia già in una StringList in memoria. Si adatta facilmente alla memoria, diciamo 200 MB.
Sono preoccupato solo per i tempi di esecuzione dell'analisi. Quale codice produrrà l'esecuzione più veloce in assoluto in Delphi (Pascal)?
Soluzione
- Utilizza l'incremento PChar per la velocità di elaborazione
- Se alcuni token non sono necessari, copia solo i dati dei token su richiesta
- Copia PChar nella variabile locale durante la scansione dei caratteri
- Conserva i dati di origine in un singolo buffer a meno che tu non debba gestire riga per riga e anche in questo caso, considera la gestione dell'elaborazione della riga come token separato nel riconoscitore lexer
- Prendi in considerazione l'elaborazione di un buffer di array di byte proveniente direttamente dal file, se conosci sicuramente la codifica; se si utilizza Delphi 2009, utilizzare PAnsiChar anziché PChar, a meno che, naturalmente, non si sappia che la codifica è UTF16-LE.
- Se sai che l'unico spazio bianco sarà # 32 (spazio ASCII) o un insieme di caratteri similmente limitato, potrebbero esserci alcuni hack di manipolazione dei bit intelligenti che possono permetterti di elaborare 4 byte alla volta usando la scansione Integer . Non mi aspetterei grandi vittorie qui, e il codice sarà chiaro come il fango.
Ecco un lexer di esempio che dovrebbe essere piuttosto efficiente, ma presuppone che tutti i dati di origine siano in una singola stringa. Rielaborarlo per gestire i buffer è moderatamente complicato a causa di token molto lunghi.
type
TLexer = class
private
FData: string;
FTokenStart: PChar;
FCurrPos: PChar;
function GetCurrentToken: string;
public
constructor Create(const AData: string);
function GetNextToken: Boolean;
property CurrentToken: string read GetCurrentToken;
end;
{ TLexer }
constructor TLexer.Create(const AData: string);
begin
FData := AData;
FCurrPos := PChar(FData);
end;
function TLexer.GetCurrentToken: string;
begin
SetString(Result, FTokenStart, FCurrPos - FTokenStart);
end;
function TLexer.GetNextToken: Boolean;
var
cp: PChar;
begin
cp := FCurrPos; // copy to local to permit register allocation
// skip whitespace; this test could be converted to an unsigned int
// subtraction and compare for only a single branch
while (cp^ > #0) and (cp^ <= #32) do
Inc(cp);
// using null terminater for end of file
Result := cp^ <> #0;
if Result then
begin
FTokenStart := cp;
Inc(cp);
while cp^ > #32 do
Inc(cp);
end;
FCurrPos := cp;
end;
Altri suggerimenti
Ecco un'implementazione assurda di un lexer molto semplice. Questo potrebbe darti un'idea.
Nota le limitazioni di questo esempio: nessun buffering, nessun Unicode (questo è un estratto da un progetto Delphi 7). Probabilmente avresti bisogno di quelli in una seria implementazione.
{ Implements a simpe lexer class. }
unit Simplelexer;
interface
uses Classes, Sysutils, Types, dialogs;
type
ESimpleLexerFinished = class(Exception) end;
TProcTableProc = procedure of object;
// A very simple lexer that can handle numbers, words, symbols - no comment handling
TSimpleLexer = class(TObject)
private
FLineNo: Integer;
Run: Integer;
fOffset: Integer;
fRunOffset: Integer; // helper for fOffset
fTokenPos: Integer;
pSource: PChar;
fProcTable: array[#0..#255] of TProcTableProc;
fUseSimpleStrings: Boolean;
fIgnoreSpaces: Boolean;
procedure MakeMethodTables;
procedure IdentProc;
procedure NewLineProc;
procedure NullProc;
procedure NumberProc;
procedure SpaceProc;
procedure SymbolProc;
procedure UnknownProc;
public
constructor Create;
destructor Destroy; override;
procedure Feed(const S: string);
procedure Next;
function GetToken: string;
function GetLineNo: Integer;
function GetOffset: Integer;
property IgnoreSpaces: boolean read fIgnoreSpaces write fIgnoreSpaces;
property UseSimpleStrings: boolean read fUseSimpleStrings write fUseSimpleStrings;
end;
implementation
{ TSimpleLexer }
constructor TSimpleLexer.Create;
begin
makeMethodTables;
fUseSimpleStrings := false;
fIgnoreSpaces := false;
end;
destructor TSimpleLexer.Destroy;
begin
inherited;
end;
procedure TSimpleLexer.Feed(const S: string);
begin
Run := 0;
FLineNo := 1;
FOffset := 1;
pSource := PChar(S);
end;
procedure TSimpleLexer.Next;
begin
fTokenPos := Run;
foffset := Run - frunOffset + 1;
fProcTable[pSource[Run]];
end;
function TSimpleLexer.GetToken: string;
begin
SetString(Result, (pSource + fTokenPos), Run - fTokenPos);
end;
function TSimpleLexer.GetLineNo: Integer;
begin
Result := FLineNo;
end;
function TSimpleLexer.GetOffset: Integer;
begin
Result := foffset;
end;
procedure TSimpleLexer.MakeMethodTables;
var
I: Char;
begin
for I := #0 to #255 do
case I of
'@', '&', '}', '{', ':', ',', ']', '[', '*',
'^', ')', '(', ';', '/', '=', '-', '+', '#', '>', '<', ',
'.', '"', #39:
fProcTable[I] := SymbolProc;
#13, #10: fProcTable[I] := NewLineProc;
'A'..'Z', 'a'..'z', '_': fProcTable[I] := IdentProc;
#0: fProcTable[I] := NullProc;
'0'..'9': fProcTable[I] := NumberProc;
#1..#9, #11, #12, #14..#32: fProcTable[I] := SpaceProc;
else
fProcTable[I] := UnknownProc;
end;
end;
procedure TSimpleLexer.UnknownProc;
begin
inc(run);
end;
procedure TSimpleLexer.SymbolProc;
begin
if fUseSimpleStrings then
begin
if pSource[run] = '"' then
begin
Inc(run);
while pSource[run] <> '"' do
begin
Inc(run);
if pSource[run] = #0 then
begin
NullProc;
end;
end;
end;
Inc(run);
end
else
inc(run);
end;
procedure TSimpleLexer.IdentProc;
begin
while pSource[Run] in ['_', 'A'..'Z', 'a'..'z', '0'..'9'] do
Inc(run);
end;
procedure TSimpleLexer.NumberProc;
begin
while pSource[run] in ['0'..'9'] do
inc(run);
end;
procedure TSimpleLexer.SpaceProc;
begin
while pSource[run] in [#1..#9, #11, #12, #14..#32] do
inc(run);
if fIgnoreSpaces then Next;
end;
procedure TSimpleLexer.NewLineProc;
begin
inc(FLineNo);
inc(run);
case pSource[run - 1] of
#13:
if pSource[run] = #10 then inc(run);
end;
foffset := 1;
fRunOffset := run;
end;
procedure TSimpleLexer.NullProc;
begin
raise ESimpleLexerFinished.Create('');
end;
end.
Ho creato un analizzatore lessicale basato su un motore statale (DFA). Funziona con un tavolo ed è piuttosto veloce. Ma ci sono opzioni più veloci possibili.
Dipende anche dalla lingua. Un linguaggio semplice può possibilmente avere un algoritmo intelligente.
La tabella è un array di record contenenti ciascuno 2 caratteri e 1 intero. Per ogni token il lexer cammina attraverso il tavolo, iniziando dalla posizione 0:
state := 0;
result := tkNoToken;
while (result = tkNoToken) do begin
if table[state].c1 > table[state].c2 then
result := table[state].value
else if (table[state].c1 <= c) and (c <= table[state].c2) then begin
c := GetNextChar();
state := table[state].value;
end else
Inc(state);
end;
È semplice e funziona come un fascino.
Se la velocità è essenziale, il codice personalizzato è la risposta. Controlla l'API di Windows che mapperà il tuo file in memoria. Puoi quindi usare solo un puntatore al personaggio successivo per eseguire i tuoi token, sfogliando come richiesto.
Questo è il mio codice per fare una mappatura:
procedure TMyReader.InitialiseMapping(szFilename : string);
var
// nError : DWORD;
bGood : boolean;
begin
bGood := False;
m_hFile := CreateFile(PChar(szFilename), GENERIC_READ, 0, nil, OPEN_EXISTING, 0, 0);
if m_hFile <> INVALID_HANDLE_VALUE then
begin
m_hMap := CreateFileMapping(m_hFile, nil, PAGE_READONLY, 0, 0, nil);
if m_hMap <> 0 then
begin
m_pMemory := MapViewOfFile(m_hMap, FILE_MAP_READ, 0, 0, 0);
if m_pMemory <> nil then
begin
htlArray := Pointer(Integer(m_pMemory) + m_dwDataPosition);
bGood := True;
end
else
begin
// nError := GetLastError;
end;
end;
end;
if not bGood then
raise Exception.Create('Unable to map token file into memory');
end;
Penso che il più grande collo di bottiglia sarà sempre quello di salvare il file in memoria. Una volta che lo hai in memoria (ovviamente non tutto in una volta, ma lavorerei con i buffer se fossi in te), l'analisi effettiva dovrebbe essere insignificante.
Questo pone un'altra domanda: quanto è grande? Dacci un indizio come # di linee o # o Mb (Gb)? Quindi sapremo se si adatta alla memoria, deve essere basato su disco ecc.
Al primo passaggio userei il mio WordList (S: String; AList: TStringlist);
quindi puoi accedere a ciascun token come Alist [n] ... o ordinarli o altro.
La velocità sarà sempre relativa a ciò che stai facendo una volta analizzata. Un parser lessicale è di gran lunga il metodo più veloce per la conversione in token da un flusso di testo indipendentemente dalle dimensioni. TParser nell'unità di classe è un ottimo punto di partenza.
Personalmente è passato un po 'di tempo da quando avevo bisogno di scrivere un parser, ma un altro metodo più datato ma provato e vero sarebbe quello di usare LEX / YACC per costruire una grammatica e poi convertirla in codice che puoi usare per eseguire il tuo in lavorazione. DYacc è una versione di Delphi ... non sono sicuro che si compili ancora o no, ma vale la pena dare un'occhiata se vuoi fare cose vecchia scuola. Il libro del drago qui sarebbe di grande aiuto, se ne trovi una copia.
Far rotolare il tuo è sicuramente il modo più veloce. Per ulteriori informazioni su questo argomento, potresti vedere il codice sorgente di Synedit che contiene lexer (chiamati evidenziatori nel contesto del progetto) per circa qualsiasi lingua sul mercato. Ti suggerisco di prendere uno di quei lexer come base e modificarlo per il tuo uso personale.
Il modo più veloce per scrivere il codice sarebbe probabilmente quello di creare un TStringList e assegnare ogni riga nel tuo file di testo alla proprietà CommaText. Per impostazione predefinita, lo spazio bianco è un delimitatore, quindi otterrai un oggetto StringList per token.
MyStringList.CommaText := s;
for i := 0 to MyStringList.Count - 1 do
begin
// process each token here
end;
Probabilmente otterrai prestazioni migliori analizzando da solo ogni riga.
