Qual é a maneira mais rápida para analisar uma linha no Delphi?

Question

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)?

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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;

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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.