Was ist der schnellste Weg, um eine Linie in Delphi zu analysieren?

StackOverflow https://stackoverflow.com/questions/287789

  •  08-07-2019
  •  | 
  •  

Frage

Ich habe eine große Datei, die ich Zeile für Zeile analysiert werden muß. Die Geschwindigkeit ist von fundamentaler Bedeutung.

Beispiel einer Zeile: 

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

GetToken genannt wird: „Hier-ist-die-Next-Token“ und setzt die Currentposition auf die Position des letzten Zeichens des Tokens zurückkehrt, so dass es für den nächsten Anruf zu GetToken bereit ist. Tokens sind getrennt durch ein oder mehrere Leerzeichen.

Angenommen, die Datei bereits in einem String im Speicher. Sie paßt leicht in Erinnerung, sagen 200 MB.

Ich bin nur über die Ausführungszeit für das Parsing besorgt. Welcher Code wird die absolute schnellste Ausführung in Delphi (Pascal) produzieren?

War es hilfreich?

Lösung

  • Verwenden Sie PChar für die Geschwindigkeit der Verarbeitung erhöht wird
  • Wenn einige Token nicht benötigt werden, nur Token-Daten bei Bedarf zu kopieren
  • Kopieren PChar auf lokale Variable, wenn tatsächlich durch Zeichen Scannen
  • Halten Sie Quelldaten in einem einzigen Puffer, wenn Sie Zeile für Zeile umgehen müssen, und selbst dann, betrachten line-Verarbeitung als separate Token in der Lexer Erkennungs Handhabung
  • Betrachten wir ein Byte-Array-Puffer verarbeitet, die direkt aus der Datei gekommen ist, wenn Sie auf jeden Fall die Codierung wissen; wenn mit Delphi 2009 verwenden PAnsiChar statt PChar, es sei denn natürlich wissen Sie die Codierung ist UTF16-LE.
  • Wenn Sie wissen, dass das nur Leerzeichen # 32 (ASCII Raum) oder eine ähnlich begrenzte Menge von Zeichen sein wird, kann es einige clevere Bit-Manipulations Hacks, die Sie verarbeiten 4 Byte zu einem Zeitpunkt unter Verwendung von Integer-Scanning lassen kann . Ich würde nicht große Gewinne hier allerdings erwarten, und der Code wird so klar wie Schlamm.

Hier ist ein Beispiel Lexer, die ziemlich effizient sein sollten, aber es wird davon ausgegangen, dass alle Quelldaten in einer einzigen Zeichenfolge ist. Nacharbeiten es Puffer zu handhaben ist mäßig heikel wegen der sehr langen Token. 

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;

Andere Tipps

Hier ist eine lame ass Implementierung eines sehr einfachen Lexer. Dies könnte Ihnen eine Idee geben.

Hinweis

die Grenzen dieses Beispiels - keine Pufferung beteiligt ist, keine Unicode (dies ist ein Auszug aus einem Delphi-7-Projekt). Sie würden wahrscheinlich diejenigen, die in einer ernsthaften Umsetzung benötigen. 

{ 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.

Ich habe eine lexikalische Analyse basierend auf einem Zustand Motor (EDA). Es arbeitet mit einem Tisch und ist ziemlich schnell. Aber es gibt eine schnellere Optionen.

Es hängt auch von der Sprache. Eine einfache Sprache kann möglicherweise einen intelligenten Algorithmus hat.

Die Tabelle ist ein Array von Datensätzen mit jeweils 2 Zeichen und 1 ganze Zahl ist. Für jedes Token geht die Lexer durch den Tisch, an Position startting 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 ist einfach und funktioniert wie ein Charme.

Wenn die Geschwindigkeit des Wesens ist, ist benutzerdefinierter Code die Antwort. Überprüfen Sie die Windows-API, die Ihre Datei in den Speicher abbildet. Sie können dann nur einen Zeiger auf das nächste Zeichen benutzen, um Ihre Token zu tun, durch Marsch nach Bedarf.

Dies ist mein Code, um eine Zuordnung zu tun: 

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;

Ich denke, der größte Engpass immer bekommen die Datei in den Speicher werden wird. Sobald Sie es in Erinnerung haben (natürlich nicht alle davon auf einmal, aber ich würde mit Puffern arbeiten, wenn ich Sie wäre), sollte das tatsächliche Parsing unbedeutend sein.

Es stellt sich eine andere Frage - Wie groß? Geben Sie uns einen Hinweis, wie Anzahl der Zeilen oder # oder Mb (Gb)? Dann werden wir wissen, ob es in den Speicher passt, muss Platte sein basierend etc.

Auf dem ersten Pass würde ich meine Wordlist verwenden (S: String; AList: TStringList);

dann können Sie jedes Token als Alist [n] zugreifen ... oder sortieren sie oder was auch immer.

Geschwindigkeit wird immer relativ zu dem, was Sie tun, wenn es analysiert wird. Ein lexikalischer Parser ist bei weitem die schnellste Methode aus einem Textstrom Zeichen der Umwandlung unabhängig von ihrer Größe. TParser in der Klassen-Einheit ist ein großartiger Ort zu starten.

seine persönlich eine Weile her, seit ich brauchte einen Parser zu schreiben, aber eine andere, datiert noch bewährte Methode wäre LEX / YACC zu verwenden, um eine Grammatik zu bauen, dann haben es die Grammatik in Code umwandeln können Sie ausführen verwenden, um Ihre wird bearbeitet. DYacc ist eine Delphi-Version ... nicht sicher, ob es noch oder nicht kompiliert, aber einen Blick wert, wenn man die Dinge der alten Schule tun wollen. Die Drachen Buch hier von großer Hilfe sein würde, wenn Sie eine Kopie finden können.

Roll Ihr eigenes ist der schnellste Weg, sicher. Weitere Informationen zu diesem Thema können Sie unter SynEdit Quellcode die Lexer (genannt highlighters im Projektkontext) enthält für jede Sprache auf dem Markt. Ich schlage vor, Sie einen jener lexers als Basis nehmen und für die eigene Nutzung ändern.

Der schnellste Weg zu write der Code wäre wahrscheinlich einen TStringList erstellen und jede Zeile in Ihrer Textdatei auf die CommaText Eigenschaft zuweisen. Standardmäßig ist Leerraum ein Trennzeichen, so dass Sie einen String Artikel pro Token erhalten. 

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

Sie werden wahrscheinlich eine bessere Leistung erhalten, indem jede Zeile selbst Parsen, though.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top