tecnica - ¿Cuál es la forma más rápida de analizar una línea en Delphi?

tecnica delphi pmbok

Question

Tengo un archivo enorme que debo analizar línea por línea. La velocidad es esencial.

Ejemplo de una línea:

Token-1   Here-is-the-Next-Token      Last-Token-on-Line
      ^                        ^
   Current                 Position
   Position              after GetToken

Se llama a GetToken, devolviendo "Here-is-the-Next-Token" y establece CurrentPosition en la posición del último carácter del token para que esté listo para la próxima llamada a GetToken. Los tokens están separados por uno o más espacios.

Suponga que el archivo ya está en StringList en la memoria. Se adapta fácilmente a la memoria, digamos 200 MB.

Solo me preocupa el tiempo de ejecución para el análisis sintáctico. ¿Qué código producirá la ejecución más rápida absoluta en Delphi (Pascal)?

Answer 1

Aquí hay una implementación coja de un lexer muy simple. Esto podría darte una idea.

Tenga en cuenta las limitaciones de este ejemplo: no hay memoria intermedia involucrada, no hay Unicode (esto es un extracto de un proyecto Delphi 7). Probablemente necesites aquellos en una implementación seria.

{ 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 2

Creo que el cuello de botella más grande siempre será tener el archivo en la memoria. Una vez que lo tenga en la memoria (obviamente, no todo al mismo tiempo, pero trabajaría con búferes si fuera usted), el análisis real debería ser insignificante.

Answer 3

Esto genera otra pregunta: ¿qué tan grande? Danos una pista como # de líneas o # o Mb (Gb)? Entonces sabremos si cabe en la memoria, necesita estar basado en disco, etc.

En el primer paso usaría mi WordList (S: String; AList: TStringlist);

luego puedes acceder a cada token como Alist [n] ... u ordenarlos o lo que sea.

Answer 4

Hice un analizador léxico basado en un motor de estado (DFA). Funciona con una tabla y es bastante rápido. Pero hay posibles opciones más rápidas.

También depende del idioma. Un lenguaje simple puede tener un algoritmo inteligente.

La tabla es una matriz de registros, cada uno con 2 caracteres y 1 entero. Para cada token, el lexer camina a través de la mesa, comenzando en la posición 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;

Es simple y funciona como un encanto.

Answer 5

La forma más rápida de escribir el código probablemente sea crear una TStringList y asignar cada línea en su archivo de texto a la propiedad CommaText. De forma predeterminada, el espacio en blanco es un delimitador, por lo que obtendrá un elemento StringList por token.

MyStringList.CommaText := s;
for i := 0 to MyStringList.Count - 1 do
begin
  // process each token here
end;

Sin embargo, probablemente obtendrás un mejor rendimiento al analizar cada línea.

Answer 6

La velocidad siempre será relativa a lo que está haciendo una vez que se analiza. Un analizador léxico por lejos es el método más rápido de conversión a tokens desde una secuencia de texto, independientemente del tamaño. TParser en la unidad de clases es un gran lugar para comenzar.

Personalmente ha pasado un tiempo desde que necesité escribir un analizador sintáctico, pero otro método más anticuado pero probado sería usar LEX / YACC para construir una gramática y luego convertirla en un código que pueda usar para realizar su procesamiento. DYacc es una versión de Delphi ... no estoy seguro de si todavía compila o no, pero vale la pena mirar si quieres hacer cosas de la vieja escuela. El libro de dragones aquí sería de gran ayuda, si puedes encontrar una copia.

Answer 7

Rodar uno mismo es la forma más rápida de seguro. Para obtener más información sobre este tema, puede ver el código fuente de Synedit que contiene lexers (llamados resaltadores en el contexto del proyecto) para cualquier idioma en el mercado. Te sugiero que tomes uno de esos lexers como base y lo modifiques para tu propio uso.

Answer 8

• Use PChar incrementando la velocidad de procesamiento
• Si no se necesitan algunos tokens, solo copie los datos del token a pedido
• Copie PChar a la variable local cuando en realidad escanee caracteres
• Mantenga los datos de origen en un solo búfer a menos que deba manejar línea por línea, e incluso entonces, considere manejar el procesamiento de línea como un token separado en el reconocedor de lexer
• Considere procesar un búfer de matriz de bytes que viene directamente del archivo, si definitivamente conoce la codificación; si usa Delphi 2009, use PAnsiChar en lugar de PChar, a menos que, por supuesto, sepa que la codificación es UTF16-LE.
• Si sabe que el único espacio en blanco será # 32 (espacio ASCII) o un conjunto de caracteres similarmente limitado, puede haber algunos ataques de manipulación inteligente de bits que pueden permitirle procesar 4 bytes a la vez usando el barrido de enteros. Sin embargo, no esperaría grandes ganancias aquí, y el código será tan claro como el barro.

Aquí hay un lexer de muestra que debería ser bastante eficiente, pero supone que todos los datos fuente están en una sola cadena. Volver a trabajar para manejar los búferes es moderadamente difícil debido a tokens muy largos.

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 9

Si la velocidad es esencial, el código personalizado es la respuesta. Consulte la API de Windows que mapeará su archivo en la memoria. A continuación, puede utilizar un puntero al siguiente personaje para hacer sus tokens, marchando según sea necesario.

Este es mi código para hacer un mapeo:

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;