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;