Какой самый быстрый способ разобрать строку в Delphi?

Question

У меня есть огромный файл, который я должен анализировать построчно. Скорость имеет значение.

Пример строки:

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

Вызывается GetToken, возвращая «Here-is-the-Next-Token» и устанавливает CurrentPosition в положение последнего символа токена, чтобы он был готов к следующему вызову GetToken. Токены разделены одним или несколькими пробелами.

Предположим, что файл уже находится в StringList в памяти. Он легко помещается в памяти, скажем, 200 МБ.

Меня беспокоит только время выполнения анализа. Какой код будет производить абсолютно быстрое выполнение в 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

Вот реализация хромой задницы очень простого лексера. Это может дать вам представление.

Обратите внимание на ограничения этого примера - без буферизации, без Юникода (это отрывок из проекта 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 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

Если скорость имеет существенное значение, пользовательский код является ответом. Проверьте 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;

Answer 5

Скорость всегда будет зависеть от того, что вы делаете, когда она будет проанализирована. Лексический синтаксический анализатор на сегодняшний день является самым быстрым методом преобразования токенов из текстового потока независимо от его размера. TParser в модуле классов - отличное место для начала.

Лично это было давно, так как мне нужно было написать парсер, но другой более устаревший, но проверенный и верный метод - использовать LEX / YACC для построения грамматики, а затем преобразовать грамматику в код, который можно использовать для обработка. DYacc - это версия Delphi ... не уверен, что она все еще компилируется или нет, но стоит посмотреть, если вы хотите заняться чем-то старым. книга драконов очень помогла бы, если бы вы смогли найти копию.

Answer 6

Напрашивается другой вопрос - насколько велик? Дайте нам подсказку, как # строк или # или Мб (Гб)? Тогда мы узнаем, умещается ли он в памяти, должен ли он быть основан на диске и т. Д.

При первом проходе я бы использовал свой WordList (S: String; AList: TStringlist);

тогда вы можете получить доступ к каждому токену как Alist [n] ... или сортировать их или что-то еще.

Answer 7

Я думаю, что самым большим узким местом всегда будет попадание файла в память. Если у вас есть это в памяти (очевидно, не все сразу, но я бы работал с буферами на вашем месте), фактический анализ должен быть незначительным.

Answer 8

Самый быстрый способ написать код, вероятно, будет создать TStringList и назначить каждую строку в вашем текстовом файле свойству CommaText. По умолчанию пробел является разделителем, поэтому вы получите один элемент StringList на каждый токен.

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

Вероятно, вы получите лучшую производительность, если разберете каждую строку самостоятельно.

Answer 9

Прокатись самостоятельно - это самый быстрый способ. Для получения дополнительной информации по этой теме вы можете увидеть Исходный код Synedit , который содержит лексеры (называемые маркерами в контексте проекта) для любого языка на рынке. Я предлагаю вам взять за основу один из этих лексеров и изменить его для собственного использования.