Каков самый быстрый способ разобрать строку в Delphi?
https://stackoverflow.com/questions/287789
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня есть огромный файл, который я должен проанализировать построчно.Скорость имеет решающее значение.
Пример строки:
Token-1 Here-is-the-Next-Token Last-Token-on-Line ^ ^ Current Position Position after GetToken
Вызывается GetToken, который возвращает «Вот-следующий-токен» и устанавливает CurrentPosition в положение последнего символа токена, чтобы он был готов к следующему вызову GetToken.Токены разделяются одним или несколькими пробелами.
Предположим, что файл уже находится в StringList в памяти.Он легко помещается в памяти, скажем 200 МБ.
Меня беспокоит только время выполнения синтаксического анализа.Какой код обеспечит самое быстрое выполнение в Delphi (Pascal)?
Решение
- Используйте увеличение 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;
Я думаю, что самым большим узким местом всегда будет попадание файла в память. Если у вас есть это в памяти (очевидно, не все сразу, но я бы работал с буферами на вашем месте), фактический синтаксический анализ должен быть незначительным.
Напрашивается еще один вопрос - насколько большой? Дайте нам подсказку, как # строк или # или Мб (Гб)? Тогда мы узнаем, помещается ли он в память, должен ли он быть основан на диске и т. Д.
На первом этапе я бы использовал свой WordList (S: String; AList: TStringlist);
тогда вы можете получить доступ к каждому токену как Alist [n] ... или сортировать их или что-то еще.
Скорость всегда будет зависеть от того, что вы делаете, после ее анализа. Лексический синтаксический анализатор на сегодняшний день является самым быстрым методом преобразования токенов из текстового потока независимо от его размера. TParser в модуле классов - отличное место для начала.
Лично это было давно, так как мне нужно было написать парсер, но другой более устаревший, но проверенный и верный метод - использовать LEX / YACC для построения грамматики, а затем преобразовать грамматику в код, который вы можете использовать для выполнения своих действий. обработка. DYacc является версией Delphi ... не уверен, компилируется она или нет, но Стоит посмотреть, если вы хотите делать вещи старой школы. книга драконов будет очень полезна, если вы сможете найти ее копию.
Прокатить свой собственный - это самый быстрый способ. Подробнее об этой теме вы можете прочитать в исходном коде Synedit , который содержит лексеры (называемые маркерами в контексте проекта) о любом языке на рынке. Я предлагаю вам взять один из этих лексеров за основу и модифицировать его для собственного использования.
Самый быстрый способ записи кода, вероятно, состоит в создании TStringList и назначении каждой строки в вашем текстовом файле свойству CommaText. По умолчанию пробел является разделителем, поэтому вы получите один элемент StringList на каждый токен.
MyStringList.CommaText := s;
for i := 0 to MyStringList.Count - 1 do
begin
// process each token here
end;
Вы, вероятно, получите лучшую производительность, если разберете каждую строку самостоятельно.
