在Delphi中解析一行最快的方法是什麼？

Question

我有一個巨大的文件，我必須逐行解析。速度是至關重要的。一行的

實施例：

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

爲gettoken被調用時，返回「在這裏-是最下一頁令牌」，並設置CurrentPosition到令牌的最後一個字符的位置以便爲下一次調用GetToken做好準備。令牌由一個或多個空格分隔。

假設文件已經在內存中的StringList中。它很容易適應內存，比如說200 MB。

我只擔心解析的執行時間。什麼代碼會在Delphi（Pascal）中產生絕對最快的執行？

Answer 1

• 使用PChar類型遞增處理
• 的速度。如果不需要一些標記，僅在需要
• 複製PChar類型複製令牌數據到本地變量時，實際上是通過文字掃描
• 保留源數據中除非您必須逐行處理，並且即使如此，也應考慮將行處理作爲詞法分析識別器中的單獨標記進行處理。
• 如果您確實知道編碼，請考慮處理直接來自文件的字節數組緩衝區;如果使用Delphi 2009，請使用PAnsiChar代替PChar，除非您知道編碼是UTF16-LE。
• 如果您知道唯一的空格將是＃32（ASCII空間）或類似的有限字符集，可能會有一些巧妙的位操作入侵，可以讓您一次處理4個字節使用整數掃描。儘管如此，我不希望大勝，而且代碼將像泥巴一樣清晰。

下面是一個樣例詞法分析器，它應該非常高效，但它假定所有源數據都在單個字符串中。由於非常長的令牌，重新處理它以處理緩衝區是非常棘手的。

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

滾動你自己是確保最快的方法。有關此主題的更多信息，您可以看到Synedit's source code，其中包含市場上任何語言的詞法分析器（稱爲項目上下文中的熒光筆）。我建議你以這些詞法分析器中的一個作爲基礎，並根據自己的用法進行修改。

Answer 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; 

它很簡單，像魅力一樣工作。

Answer 4

我認爲最大的瓶頸總是將文件存入內存。一旦你把它放在內存中（顯然不是全部，但如果我是你，我會用緩衝區），實際的解析應該是微不足道的。

Answer 5

最快的方法寫代碼可能會創建一個TStringList並將您的文本文件中的每一行分配給CommaText屬性。默認情況下，空格是一個分隔符，因此每個標記將獲得一個StringList項目。

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

不過，您可能會通過自己解析每一行來獲得更好的性能。

Answer 6

這是一個非常簡單的詞法分析器的蹩腳屁股實現。這可能會給你一個想法。

請注意此示例的侷限性 - 不涉及緩衝區，無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. 

Answer 7

這引出了另一個問題 - 有多大？ 給我們一些線索，如＃行或＃或Mb（Gb）？然後我們會知道它是否適合內存，需要基於磁盤等。

第一遍我會用我的WordList（S：String; AList：TStringlist）;

然後你可以訪問每個令牌作爲Alist [n] ... 或排序他們或任何。

Answer 8

速度總是與您在解析之後所做的相關。到目前爲止，詞法分析器是從文本流轉換爲令牌的最快方法，無論大小如何。班級中的TParser是一個很好的開始。

就我個人而言，我需要編寫一個解析器，但另一個更爲過時的嘗試和真正的方法是使用LEX/YACC構建語法，然後將語法轉換爲可用於執行的代碼你的處理。 DYacc是一個德爾福版本...不知道它是否仍然編譯，但值得一看，如果你想做舊事的東西。如果你能找到一份副本，這裏的dragon book會有很大的幫助。

Answer 9

如果速度至關重要，自定義代碼就是答案。查看將您的文件映射到內存的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;