Quel est le moyen le plus rapide d’analyser une ligne dans Delphi?

Question

J'ai un énorme fichier à analyser ligne par ligne. La vitesse est essentielle.

Exemple de ligne:

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

GetToken est appelé, renvoyant "Here-is-the-Next-Token". et définit CurrentPosition sur la position du dernier caractère du jeton afin qu'il soit prêt pour le prochain appel à GetToken. Les jetons sont séparés par un ou plusieurs espaces.

Supposons que le fichier est déjà dans une liste de chaînes en mémoire. Il tient facilement dans la mémoire, disons 200 Mo.

Je ne m'inquiète que du temps d'exécution de l'analyse. Quel code produira l’exécution la plus rapide absolue en Delphi (Pascal)?

Answer 1

• Utilisez PChar incrémentant pour accélérer le traitement
• Si certains jetons ne sont pas nécessaires, copiez uniquement les données de jeton à la demande
• Copier PChar dans une variable locale lors de la numérisation de caractères
• Conservez les données source dans un seul tampon, sauf si vous devez gérer ligne par ligne et même dans ce cas, envisagez de traiter le traitement de la ligne comme un jeton distinct dans le système de reconnaissance de lexer
• Pensez à traiter un tampon de tableau d'octets provenant directement du fichier, si vous connaissez le codage. si vous utilisez Delphi 2009, utilisez PAnsiChar au lieu de PChar, sauf si vous savez bien que le codage est UTF16-LE.
• Si vous savez que le seul espace sera le # 32 (espace ASCII) ou un ensemble de caractères similaire, il peut y avoir des manipulations de bits astucieuses qui peuvent vous permettre de traiter 4 octets à la fois à l'aide de l'analyse Integer. . Je ne m'attendrais pas à de grandes victoires ici, cependant, et le code sera aussi clair que de la boue.

Voici un exemple de lexer qui devrait être assez efficace, mais il suppose que toutes les données source sont dans une seule chaîne. Le retravailler pour gérer les tampons est moyennement difficile en raison de la longueur des jetons.

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

Voici une implémentation boiteuse d’un lexer très simple. Cela pourrait vous donner une idée.

Notez les limites de cet exemple: pas de mise en mémoire tampon, pas d'Unicode (extrait d'un projet Delphi 7). Vous auriez probablement besoin de ceux-ci dans une mise en œuvre sérieuse.

{ 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

J'ai fabriqué un analyseur lexical basé sur un moteur d'état (DFA). Cela fonctionne avec une table et est assez rapide. Mais il existe des options plus rapides possibles.

Cela dépend aussi de la langue. Un langage simple peut éventuellement avoir un algorithme intelligent.

La table est un tableau d’enregistrements contenant chacun 2 caractères et 1 entier. Pour chaque jeton, le lexer parcourt la table en commençant à la position 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;

C’est simple et fonctionne comme un charme.

Answer 4

Si la rapidité est essentielle, le code personnalisé est la réponse. Découvrez l'API Windows qui mappera votre fichier en mémoire. Vous pouvez ensuite simplement utiliser un pointeur sur le caractère suivant pour créer vos jetons, en passant comme vous le souhaitez.

Ceci est mon code pour faire un mapping:

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

Je pense que le plus gros goulot d’étranglement sera toujours d’obtenir le fichier en mémoire. Une fois que vous l'avez en mémoire (évidemment pas tout à la fois, mais je travaillerais avec des tampons si j'étais vous), l'analyse devrait être insignifiante.

Answer 6

Cela soulève une autre question: quelle taille? Donnez-nous un indice comme # de lignes ou # ou Mb (Go)? Ensuite, nous saurons si cela tient dans la mémoire, s'il doit être basé sur un disque, etc.

Au premier passage, j'utilisais ma liste de mots (S: String; AList: TStringlist);

alors vous pouvez accéder à chaque jeton en tant que Alist [n] ... ou les trier ou autre chose.

Answer 7

La vitesse sera toujours relative à ce que vous faites une fois analysée. Un analyseur lexical est de loin la méthode la plus rapide de conversion en jetons à partir d’un flux de texte, quelle que soit sa taille. TParser dans les classes est un excellent point de départ.

Personnellement, cela fait un moment que je n'ai pas besoin d'écrire un analyseur, mais une autre méthode plus ancienne et éprouvée consiste à utiliser LEX / YACC pour créer une grammaire, puis à la convertir en code que vous pouvez utiliser pour effectuer vos tâches. En traitement. DYacc est une version de Delphi ... ne sachant pas si elle est toujours compilée ou non, mais vaut le coup d'oeil si vous voulez faire les choses vieille école. Le livre de dragons ici serait d'une grande aide si vous pouvez en trouver un exemplaire.

Answer 8

Bien sûr, rouler vous-même est le moyen le plus rapide. Pour plus d'informations à ce sujet, vous pouvez consulter le code source de Synedit qui contient des lexeurs (appelés surligneurs dans le contexte du projet). pour à peu près n'importe quelle langue sur le marché. Je vous suggère de prendre un de ces lexers comme base et de le modifier pour votre propre usage.

Answer 9

Le moyen le plus rapide de écrire le code consisterait probablement à créer une liste TStringList et à affecter chaque ligne de votre fichier texte à la propriété CommaText. Par défaut, l'espace blanc est un délimiteur. Vous obtiendrez ainsi un élément StringList par jeton.

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

Vous obtiendrez probablement de meilleures performances en analysant chaque ligne vous-même, cependant.