10

行ごとに解析する必要がある巨大なファイルがあります。スピードが命です。

行の例:

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

GetToken が呼び出され、"Here-is-the-Next-Token" が返され、CurrentPosition がトークンの最後の文字の位置に設定されるため、GetToken の次の呼び出しに備えることができます。トークンは 1 つ以上のスペースで区切られます。

ファイルが既にメモリ内の StringList にあると仮定します。メモリに簡単に収まります。たとえば、200 MB です。

解析の実行時間だけが気になります。Delphi (Pascal) で絶対最速の実行を生成するコードはどれですか?

4

9 に答える 9

34
  • 処理速度を上げるために PChar インクリメントを使用する
  • 一部のトークンが不要な場合は、オンデマンドでトークン データのみをコピーします
  • 実際に文字をスキャンするときに PChar をローカル変数にコピーする
  • 行ごとに処理する必要がない限り、ソース データを 1 つのバッファーに保持します。その場合でも、行処理をレクサー認識エンジンで別のトークンとして処理することを検討してください。
  • エンコーディングが確実にわかっている場合は、ファイルから直接取得したバイト配列バッファーを処理することを検討してください。Delphi 2009 を使用している場合は、エンコーディングが UTF16-LE であることがわかっている場合を除き、PChar の代わりに PAnsiChar を使用してください。
  • 唯一の空白が #32 (ASCII スペース) または同様に制限された文字セットになることがわかっている場合、整数スキャンを使用して一度に 4 バイトを処理できる巧妙なビット操作ハックがあるかもしれません。ただし、ここで大きな勝利を収めることは期待できません。コードは泥のように明確になります。

これは非常に効率的なサンプル レクサーですが、すべてのソース データが 1 つの文字列にあることを前提としています。トークンが非常に長いため、バッファーを処理するためにそれを作り直すのはやや難しいです。

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;
于 2008-11-13T20:36:23.213 に答える
4

これは、非常に単純なレクサーの不完全な実装です。これはあなたにアイデアを与えるかもしれません。

この例の制限に注意してください - バッファリングがなく、Unicode がありません (これは Delphi 7 プロジェクトからの抜粋です)。本格的な実装では、おそらくそれらが必要になるでしょう。

{ 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.
于 2008-11-13T18:59:09.650 に答える
3

状態エンジン (DFA) に基づく字句解析器を作成しました。テーブルで動作し、かなり高速です。しかし、可能なより高速なオプションがあります。

また、言語にも依存します。単純な言語には、スマートなアルゴリズムが含まれている可能性があります。

テーブルは、それぞれ 2 つの文字と 1 つの整数を含むレコードの配列です。トークンごとに、レクサーは位置 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;

シンプルで魅力的に機能します。

于 2008-11-13T18:37:57.867 に答える
2

速度が重要な場合は、カスタム コードが答えです。ファイルをメモリにマップする Windows API を確認してください。次に、次の文字へのポインターを使用してトークンを実行し、必要に応じて行進できます。

これは、マッピングを行うための私のコードです:

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;
于 2008-11-14T10:59:04.783 に答える
1

最大のボトルネックは常にファイルをメモリに入れることだと思います。一度メモリに格納すると (明らかに、一度にすべてではありませんが、私があなたならバッファを使用します)、実際の解析は重要ではありません。

于 2008-11-13T18:43:13.910 に答える
1

これは別の質問をします - どのくらいの大きさですか？# of lines または # または Mb (Gb) のような手掛かりを教えてください。次に、メモリに収まるかどうか、ディスクベースにする必要があるかどうかなどがわかります。

最初のパスでは、WordList(S: String; AList: TStringlist); を使用します。

次に、各トークンに Alist[n]... としてアクセスしたり、並べ替えたりできます。

于 2008-11-13T19:45:14.580 に答える
1

速度は、解析後の実行内容に常に比例します。語彙パーサーは、サイズに関係なく、テキスト ストリームからトークンに変換する最も高速な方法です。クラス ユニットの TParser は、開始するのに最適な場所です。

個人的には、パーサーを作成する必要が生じてからしばらく経ちましたが、もう 1 つの古い方法ですが、LEX/YACC を使用して文法を構築し、その文法を処理の実行に使用できるコードに変換するという方法があります。 DYaccは Delphi バージョンです...まだコンパイルできるかどうかはわかりませんが、昔ながらのことをしたい場合は一見の価値があります。コピーを見つけることができれば、ここのドラゴンブックは大きな助けになるでしょう.

于 2008-11-13T21:12:11.380 に答える
0

コードを記述する最も速い方法は、おそらくTStringListを作成し、テキストファイルの各行をCommaTextプロパティに割り当てることです。デフォルトでは、空白は区切り文字であるため、トークンごとに1つのStringListアイテムを取得します。

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

ただし、各行を自分で解析することで、パフォーマンスが向上する可能性があります。

于 2008-11-13T18:56:09.017 に答える
0

自分でローリングするのが確実に最速の方法です。このトピックの詳細については、市場に出回っているほぼすべての言語のレクサー (プロジェクトのコンテキストではハイライターと呼ばれる) を含むSynedit のソース コードを参照してください。これらのレクサーの 1 つをベースにして、独自の使用法に合わせて変更することをお勧めします。

于 2008-11-13T18:36:55.640 に答える