Delphiで行を解析する最速の方法は何ですか?
質問
1行ごとに解析する必要がある巨大なファイルがあります。スピードが重要です。
行の例:
Token-1 Here-is-the-Next-Token Last-Token-on-Line ^ ^ Current Position Position after GetToken
GetTokenが呼び出され、「Here-is-the-Next-Token」を返します;そして、次のGetTokenの呼び出しの準備ができるように、CurrentPositionをトークンの最後の文字の位置に設定します。トークンは1つ以上のスペースで区切られます。
ファイルが既にメモリ内のStringListにあると仮定します。メモリに簡単に収まります(200 MBなど)。
解析の実行時間のみが心配です。 Delphi(Pascal)でどのコードが絶対最速の実行を生成しますか?
解決
- PCharインクリメントを使用して処理速度を向上
- 一部のトークンが不要な場合は、必要に応じてトークンデータのみをコピーします
- 実際に文字をスキャンするときにPCharをローカル変数にコピーする
- 行ごとに処理する必要がある場合を除き、ソースデータを単一のバッファに保持し、その場合でも、レクサー認識エンジンで行処理を別のトークンとして処理することを検討してください
- エンコードが明確にわかっている場合は、ファイルから直接送信されたバイト配列バッファーの処理を検討してください。 Delphi 2009を使用している場合、エンコードがUTF16-LEであることがわかっている場合を除き、PCharではなくPAnsiCharを使用してください。
- 唯一の空白が#32(ASCIIスペース)、または同様に制限された文字セットになることがわかっている場合、整数スキャンを使用して一度に4バイトを処理できる巧妙なビット操作ハッキングが存在する可能性があります。ただし、ここで大きな勝利を期待することはできず、コードは泥のように明確になります。
これは非常に効率的なサンプルlexerですが、すべてのソースデータが単一の文字列にあることを前提としています。バッファを処理するための再作業は、トークンが非常に長いため、ややトリッキーです。
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;
他のヒント
これは非常に単純な字句解析器の不完全な実装です。これはあなたにアイデアを与えるかもしれません。
この例の制限に注意してください-バッファリングが含まれておらず、ユニコードがありません(これは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.
状態エンジン(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;
シンプルで、チャームのように機能します。
速度が重要な場合は、カスタムコードが答えです。ファイルをメモリにマップする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;
最大のボトルネックは、常にファイルをメモリに取り込むことだと思います。一度メモリに入れたら(明らかにすべてではありませんが、私があなただったらバッファを操作します)、実際の解析は重要ではありません。
これには別の質問があります-大きさは? 行数や#またはMb(Gb)などの手がかりを教えてください。 その後、メモリに収まるかどうか、ディスクベースである必要があるかどうかなどがわかります。
最初のパスでは、WordList(S:String; AList:TStringlist);
を使用しますその後、各トークンにAlist [n]としてアクセスできます... またはそれらを並べ替えます。
速度は、解析された後の動作に常に比例します。字句解析は、サイズに関係なくテキストストリームからトークンに変換する最も速い方法です。クラスユニットのTParserは、開始するのに最適な場所です。
パーサーを書く必要があったので個人的にはしばらく時間がかかりましたが、別のより古くまだ試みられた真の方法は、LEX / YACCを使用して文法を構築し、それを文法を実行に使用できるコードに変換することです処理。 DYacc はDelphiバージョンです...まだコンパイルされているかどうかはわかりませんが、昔のことをやりたいなら一見の価値があります。ここにあるドラゴンブックは、コピーを見つけることができれば大いに役立ちます。
独自のローリングは、確かに最速の方法です。このトピックの詳細については、レクサー(プロジェクトのコンテキストでは蛍光ペンと呼ばれる)を含む Syneditのソースコードを参照できます。市場のあらゆる言語について。これらの字句解析器の1つをベースとして、独自の使用法に合わせて変更することをお勧めします。
コードを書くための最速の方法は、おそらくTStringListを作成し、テキストファイルの各行をCommaTextプロパティに割り当てることです。デフォルトでは、空白は区切り文字であるため、トークンごとに1つのStringListアイテムを取得します。
MyStringList.CommaText := s;
for i := 0 to MyStringList.Count - 1 do
begin
// process each token here
end;
ただし、各行を自分で解析することにより、おそらくパフォーマンスが向上します。