¿Cuál es la forma más rápida de analizar una línea en Delphi?
https://stackoverflow.com/questions/287789
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
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, que devuelve "Aquí está el siguiente 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. Las fichas están separadas por uno o más espacios.
Suponga que el archivo ya está en una StringList en la memoria. Cabe en la memoria fácilmente, digamos 200 MB.
Solo me preocupa el tiempo de ejecución del análisis. ¿Qué código producirá la ejecución más rápida absoluta en Delphi (Pascal)?
Solución
- Use PChar increment para 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 realmente escanee caracteres
- Mantenga los datos de origen en un único 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 lexer
- Considere el procesamiento de un búfer de matriz de bytes que proviene 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á el n. ° 32 (espacio ASCII), o un conjunto de caracteres similarmente limitado, puede haber algunos trucos inteligentes de manipulación de bits que pueden permitirle procesar 4 bytes a la vez usando el escaneo Integer . Sin embargo, no esperaría grandes victorias aquí, y el código será tan claro como el barro.
Aquí hay un ejemplo de lexer que debería ser bastante eficiente, pero supone que todos los datos de origen están en una sola cadena. Volver a trabajarlo para manejar buffers es moderadamente complicado debido a los 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;
Otros consejos
Aquí hay una implementación poco convincente de un lexer muy simple. Esto podría darte una idea.
Tenga en cuenta las limitaciones de este ejemplo: sin búfer involucrado, sin Unicode (este es un extracto de un proyecto Delphi 7). Probablemente los necesite 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.
Hice un analizador léxico basado en un motor de estado (DFA). Funciona con una mesa 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 que contienen cada uno 2 caracteres y 1 entero. Para cada ficha, el lexer camina por 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 de maravilla.
Si la velocidad es esencial, la respuesta es un código personalizado. Consulte la API de Windows que asignará su archivo a la memoria. Luego puede usar 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;
Creo que el mayor cuello de botella siempre será llevar el archivo a la memoria. Una vez que lo tenga en la memoria (obviamente no todo al mismo tiempo, pero trabajaría con buffers si fuera usted), el análisis real debería ser insignificante.
Esto plantea otra pregunta: ¿Qué tan grande? Danos una pista como # de líneas o # o Mb (Gb)? Entonces sabremos si cabe en la memoria, si necesita estar basado en disco, etc.
En el primer paso, usaría mi WordList (S: String; AList: TStringlist);
entonces puedes acceder a cada token como Alist [n] ... o ordenarlos o lo que sea.
La velocidad siempre será relativa a lo que está haciendo una vez que se analiza. Un analizador léxico es, con diferencia, el método más rápido para convertir tokens desde una secuencia de texto, independientemente del tamaño. TParser en la unidad de clases es un excelente lugar para comenzar.
Personalmente ha pasado un tiempo desde que necesitaba escribir un analizador, pero otro método más anticuado pero probado y verdadero sería usar LEX / YACC para construir una gramática y luego convertir la gramática en código que puede usar para realizar su tratamiento. DYacc es una versión de Delphi ... no estoy seguro si aún se compila o no, pero Vale la pena echarle un vistazo si quieres hacer cosas de la vieja escuela. El dragon book aquí sería de gran ayuda, si puede encontrar una copia.
Rodar el tuyo es la forma más rápida con seguridad. Para obtener más información sobre este tema, puede ver código fuente de Synedit que contiene lexers (llamados marcadores en el contexto del proyecto) para casi cualquier idioma en el mercado. Le sugiero que tome uno de esos lexers como base y lo modifique para su propio uso.
La forma más rápida de escribir el código probablemente sería 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á un mejor rendimiento al analizar cada línea usted mismo.
