ما هي أسرع طريقة لتحليل خط في دلفي؟
سؤال
لدي ملف ضخم يجب أن أقوم بتحليله سطراً سطراً.سرعة هو جوهر المسألة.
مثال على الخط:
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 ميغابايت.
أنا قلق فقط بشأن وقت تنفيذ التحليل.ما هو الكود الذي سينتج أسرع تنفيذ على الإطلاق في دلفي (باسكال)؟
المحلول
- استخدم زيادة 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;
نصائح أخرى
وهنا هو تطبيق الحمار عرجاء من lexer بسيط جدا. هذا قد تعطيك فكرة.
لاحظ القيود من هذا المثال - لا التخزين المؤقت المعنية، لا يونيكود (وهذا مقتطف من مشروع دلفي 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 صحيح. لكل الرمز المميز للlexer يمشي من خلال الجدول، 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;
وانها بسيطة وتعمل مثل السحر.
إذا سرعة هو جوهر المسألة، التعليمات البرمجية المخصصة هو الجواب. تحقق من API Windows الذي سيتم تعيين الملف في الذاكرة. يمكنك بعد ذلك فقط استخدام مؤشر إلى الحرف التالي للقيام علاماتك، وزحف من خلال النحو المطلوب.
وهذا هو قانون بلدي للقيام تعيين:
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;
وأعتقد أن أكبر عنق الزجاجة ودائما ما يكون الحصول على الملف في الذاكرة. بمجرد أن لديك في الذاكرة (من الواضح أن ليس كل من هو في آن واحد، ولكن أود أن العمل مع مخازن لو كنت أنت)، وينبغي أن يكون إعراب الفعلي يستهان بها.
وهذا يطرح سؤال آخر - كيف الكبيرة؟ تعطينا فكرة مثل # خطوط أو # أو ميجا بايت (GB)؟ ثم سنعرف ما اذا كان يناسب في الذاكرة، يجب أن يكون القرص على أساس الخ.
وفي مرور الأول سأستخدم قائمة الكلمات (S: سلسلة؛ AList: TStringlist)؛
وبعد ذلك يمكنك الوصول إلى كل رمز كما Alist [ن] ... أو فرزها أو أيا كان.
وسرعة ستكون دائما بالنسبة إلى ما تقومون به بمجرد توزيعه. محلل معجمي إلى حد بعيد هو أسرع طريقة لتحويل إلى الرموز من تيار النص بغض النظر عن حجمها. TParser في وحدة الصفوف هو مكان عظيم للبدء.
وشخصيا لها منذ بعض الوقت وكنت بحاجة لكتابة محلل، ولكن آخر أكثر المؤرخين وحاول بعد وأن الطريقة الحقيقية هي استخدام LEX / YACC لبناء قواعد اللغة ثم أنها قد تحويل قواعد اللغة إلى رمز يمكنك استخدامها لتنفيذ الخاص بك معالجة. DYacc هو نسخة دلفي ... لست متأكدا إذا كان لا يزال يجمع أم لا، ولكن تستحق نظرة إذا كنت تريد أن تفعل أشياء المدرسة القديمة. و هنا سيكون من مساعدة كبيرة، إذا كان يمكنك العثور على نسخة منه.
والمتداول بنفسك هي اسرع وسيلة للتأكد. لمعرفة المزيد عن هذا الموضوع، هل يمكن أن نرى شفرة المصدر Synedit والذي يحتوي على lexers (وتسمى أقلام في سياق المشروع) لعن أي لغة في السوق. أقترح عليك أن تأخذ واحدة من تلك lexers كقاعدة وتعديل للاستخدام الخاص.
أسرع طريقة ل يكتب من المحتمل أن يكون الرمز هو إنشاء TStringList وتعيين كل سطر في الملف النصي الخاص بك إلى خاصية CommaText.بشكل افتراضي، المسافة البيضاء هي محدد، لذلك سوف تحصل على عنصر StringList واحد لكل رمز مميز.
MyStringList.CommaText := s;
for i := 0 to MyStringList.Count - 1 do
begin
// process each token here
end;
ربما ستحصل على أداء أفضل من خلال تحليل كل سطر بنفسك.