Qual é a maneira mais rápida para analisar uma linha no Delphi?
Pergunta
Eu tenho um arquivo enorme que deve analisar linha por linha. A velocidade é da essência.
Exemplo de uma linha:
Token-1 Here-is-the-Next-Token Last-Token-on-Line ^ ^ Current Position Position after GetToken
GetToken é chamado, retornando "Aqui, é-o-Next-Símbolo" e define o CurrentPosition para a posição do último caractere do modo token que ele está pronto para a próxima chamada para GetToken. Tokens são separados por um ou mais espaços.
Suponha que o arquivo já está em um StringList na memória. Ele se encaixa facilmente em memória, digamos 200 MB.
Estou preocupado apenas com o tempo de execução para a análise. O código irá produzir a execução mais rápida absoluta em Delphi (Pascal)?
Solução
- Use PChar incremento de velocidade de processamento
- Se alguns símbolos não são necessários, copie apenas os dados simbólicos sob demanda
- Copiar PChar a variável local, quando na verdade a digitalização através de personagens
- dados de origem manter em um único buffer a menos que você deve lidar com linha por linha, e mesmo assim, considerar a manipulação de processamento de linha como um símbolo separado no lexer reconhecedor
- Considere o processamento de um tampão matriz de bytes que tem vindo em linha reta a partir do arquivo, se você definitivamente sabe a codificação; se estiver usando o Delphi 2009, use PAnsiChar vez de PChar, a menos que você sabe a codificação é UTF16-LE.
- Se você sabe que o único espaço em branco vai ser # 32 (espaço ASCII), ou um conjunto semelhante limitado de caracteres, pode haver alguns hacks manipulação pouco inteligentes que podem deixá-lo processar 4 bytes de cada vez usando a digitalização Integer . Eu não esperaria grandes vitórias aqui, porém, eo código será tão claro como lama.
Aqui está um lexer amostra que deve ser bastante eficiente, mas ele assume que todos os dados de origem está em uma única seqüência. Retrabalhando-lo para lidar com buffers é moderadamente complicado devido a longos tokens.
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;
Outras dicas
Aqui está uma implementação lame ass de um lexer muito simples. Isso pode lhe dar uma idéia.
Observe as limitações deste exemplo - sem buffering envolvidos, não Unicode (este é um trecho de um projeto Delphi 7). Você provavelmente precisará aqueles em uma implementação séria.
{ 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.
Eu fiz um analisador léxico baseado em um motor de Estado (DFA). Ele funciona com uma mesa e é muito rápido. Mas existem possíveis mais rápido opções.
Ele também depende do idioma. A linguagem simples pode, eventualmente, ter um algoritmo inteligente.
A mesa é uma matriz de registos, cada um contendo 2 caracteres e um número inteiro. Para cada símbolo do lexer percorre a mesa, Startting na posição 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;
É simples e funciona como um encanto.
Se a velocidade é da essência, código personalizado é a resposta. Confira a API do Windows que irá mapear o arquivo na memória. Você pode, então, basta usar um ponteiro para o próximo personagem para fazer seus tokens, marchando através conforme necessário.
Este é meu código para fazer um mapeamento:
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;
Eu acho que o maior gargalo é sempre vai estar recebendo o arquivo na memória. Depois de tê-lo na memória (obviamente não tudo de uma vez, mas eu gostaria de trabalhar com buffers se eu fosse você), a análise real deve ser insignificante.
Isso levanta outra questão - Qual o tamanho? Dê-nos uma pista como # de linhas ou # ou Mb (Gb)? Então, vamos saber se ele se encaixa na memória, precisa ser baseado em disco etc.
Na primeira passagem eu usaria meu WordList (S: String; AList: TStringList);
então você pode acessar cada token como Alist [n] ... ou classificá-los ou qualquer outra coisa.
velocidade será sempre relativa ao que você está fazendo, uma vez que é analisado. Um analisador léxico é de longe o método mais rápido de conversão para os tokens de um fluxo de texto, independentemente do tamanho. TParser na unidade de aulas é um ótimo lugar para começar.
Pessoalmente sua sido um tempo desde que eu precisava para escrever um parser, mas um outro método mais datado ainda experimentado e verdadeiro seria usar LEX / YACC para construir uma gramática em seguida, tê-lo converter a gramática em código que você pode usar para executar o seu em processamento. DYacc é uma versão Delphi ... não tenho certeza se ele ainda compila ou não, mas olhar uma pena se você quer fazer as coisas da velha escola. A dragão livro aqui seria de grande ajuda, se você pode encontrar uma cópia.
Rolling seu próprio país é a maneira mais rápida, com certeza. Para saber mais sobre este assunto, você poderia ver de SynEdit código-fonte que contém lexers (chamados marcadores no contexto do projeto) para qualquer linguagem no mercado. Eu sugiro que você dê uma daquelas lexers como uma base e modificar para seu próprio uso.
A maneira mais rápida de write o código provavelmente seria criar um TStringList e atribuir a cada linha em seu arquivo de texto para a propriedade CommaText. Por padrão, o espaço em branco é um delimitador, assim você terá um item StringList por token.
MyStringList.CommaText := s;
for i := 0 to MyStringList.Count - 1 do
begin
// process each token here
end;
Você provavelmente vai obter um melhor desempenho ao analisar cada linha mesmo, apesar de tudo.