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

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

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

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)?

Источник

9 ответов

Решение
  • Используйте 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;
Источник

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

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

Я сделал лексический анализатор на основе движка состояний (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;
Источник

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

Источник

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

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

Источник

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

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

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

Источник

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

Источник

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

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

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

Источник
Другие вопросы по тегам