ما هي أسرع طريقة لتحليل خط في دلفي؟

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 ميغابايت.

أنا قلق فقط بشأن وقت تنفيذ التحليل.ما هو الكود الذي سينتج أسرع تنفيذ على الإطلاق في دلفي (باسكال)؟

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

وهنا هو تطبيق الحمار عرجاء من 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.

Answer 3

ولقد تقدمت محلل المفردات على أساس مشغل حالة (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;

وانها بسيطة وتعمل مثل السحر.

Answer 4

إذا سرعة هو جوهر المسألة، التعليمات البرمجية المخصصة هو الجواب. تحقق من 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;

Answer 5

وأعتقد أن أكبر عنق الزجاجة ودائما ما يكون الحصول على الملف في الذاكرة. بمجرد أن لديك في الذاكرة (من الواضح أن ليس كل من هو في آن واحد، ولكن أود أن العمل مع مخازن لو كنت أنت)، وينبغي أن يكون إعراب الفعلي يستهان بها.

Answer 6

وهذا يطرح سؤال آخر - كيف الكبيرة؟ تعطينا فكرة مثل # خطوط أو # أو ميجا بايت (GB)؟ ثم سنعرف ما اذا كان يناسب في الذاكرة، يجب أن يكون القرص على أساس الخ.

وفي مرور الأول سأستخدم قائمة الكلمات (S: سلسلة؛ AList: TStringlist)؛

وبعد ذلك يمكنك الوصول إلى كل رمز كما Alist [ن] ... أو فرزها أو أيا كان.

Answer 7

وسرعة ستكون دائما بالنسبة إلى ما تقومون به بمجرد توزيعه. محلل معجمي إلى حد بعيد هو أسرع طريقة لتحويل إلى الرموز من تيار النص بغض النظر عن حجمها. TParser في وحدة الصفوف هو مكان عظيم للبدء.

وشخصيا لها منذ بعض الوقت وكنت بحاجة لكتابة محلل، ولكن آخر أكثر المؤرخين وحاول بعد وأن الطريقة الحقيقية هي استخدام LEX / YACC لبناء قواعد اللغة ثم أنها قد تحويل قواعد اللغة إلى رمز يمكنك استخدامها لتنفيذ الخاص بك معالجة. DYacc هو نسخة دلفي ... لست متأكدا إذا كان لا يزال يجمع أم لا، ولكن تستحق نظرة إذا كنت تريد أن تفعل أشياء المدرسة القديمة. و هنا سيكون من مساعدة كبيرة، إذا كان يمكنك العثور على نسخة منه.

Answer 8

والمتداول بنفسك هي اسرع وسيلة للتأكد. لمعرفة المزيد عن هذا الموضوع، هل يمكن أن نرى شفرة المصدر Synedit والذي يحتوي على lexers (وتسمى أقلام في سياق المشروع) لعن أي لغة في السوق. أقترح عليك أن تأخذ واحدة من تلك lexers كقاعدة وتعديل للاستخدام الخاص.

Answer 9

أسرع طريقة ل يكتب من المحتمل أن يكون الرمز هو إنشاء TStringList وتعيين كل سطر في الملف النصي الخاص بك إلى خاصية CommaText.بشكل افتراضي، المسافة البيضاء هي محدد، لذلك سوف تحصل على عنصر StringList واحد لكل رمز مميز.

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

ربما ستحصل على أداء أفضل من خلال تحليل كل سطر بنفسك.