رسم تبعيات HotXLS: فهرسة مخارج صيغ المصفوفات

يبني HotXLS 2.383.1، مكتبة Excel الأصلية لدلفي وC++Builder، حواف تبعيات الصيغ عبر فهرس فترات المخرجات: تبقى عقد الصيغ مرتبة بخلية الإرساء، وشجرة مقاطع تحمل أكبر صف مخرجات (OutRow2) لكل شجرة جزئية تمكّن TXLSDepGraph.BuildEdges من تخطي كتل صيغ كاملة لا تستطيع الوصول إلى نطاق مشار إليه. وعلى مصنف Win32 بحوالي 100,000 صيغة، هبطت إعادة الحساب القسرية من 18.488 ثانية إلى 102–109 ميلي ثانية

لا أحد يقيس أداء رسم التبعيات حتى يبدأ عمل دفعي كان يستغرق ثانية واحدة يستغرق عشرين. يعاد بناء الرسم كلما تغيرت طوبولوجيا الصيغ — أول Recalculate بعد تحميل مصنف أو توليده، أو أي تمريرة بعد إبطال الرسم — وفي التتبع السابق للإصلاح استغرقت تلك التمريرة الأولى وحدها 16,074 ميلي ثانية. لم يكن التقييم هو المشكلة قط؛ المشكلة كانت في تحديد من يعتمد على من

لماذا استغرقت إعادة حساب 100,000 صيغة 18 ثانية؟

كان باني الحواف القديم تربيعيًا من حيث عدد صيغ الورقة. لكل نطاق تبعية، كان BuildEdges يبحث ثنائيًا عن نافذة من العقد المرشحة ثم يختبر كل واحدة بـ RangeIntersectsOutput، وكانت تلك النافذة تبدأ من قمة الورقة المشار إليها تمامًا. مفاتيح العقد تأتي من XLSDepMakeKey التي تحزم مؤشر الورقة من البت 34 صعودًا، والصف في البتات 14–33، والعمود في البتات 0–13، فكان الحد الأدنى (Sheet1, 0, 0) يعني «كل صيغة من الصف 1 حتى قاع النطاق المشار إليه»

// قبل 2.383.1 - TXLSDepGraph.BuildEdges، لنطاق التبعية r من العقدة d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // قمة الورقة
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...عمليا بحث ثنائي فوق FNodeOrder يعطيان النافذة [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // حافة صلبة أو حافة LookupScan، تنزع التكرار عبر EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

وحده الاختبار المعياري الذي فضح هذا نموذج متتالٍ عادي: كل خلية في A2:A50000 تضيف واحدًا إلى الخلية فوقها، وكل خلية في B1:B50000 تضاعف جارها في العمود A. فالإشارة إلى الصف r كانت تجرف نحو 2r مرشح عبر اختبار المستطيل، فأدى بناء رسم واحد إلى ما يقرب من خمسة مليارات فحص تقاطع — تقدير سريع على ظهر مظروف، لكنه يتطابق مع 18.5 ثانية على الساعة. وكل فحص قال «لا» باستثناء واحد أو اثنين

لماذا لا يستطيع باني الحواف بدء البحث من الصف المشار إليه؟

لأن صيغة مصفوفة مرساة فوق نطاق قد تملك خلايا داخله. تصف كل TXLSDepNode مستطيل مخرجات من مرساها (Row، Col) إلى (OutRow2، OutCol2)، وتحصل صيغة مصفوفة CSE على عقدة واحدة لمستطيلها كله، كما يشرح مقال إعادة الحساب التزايدي ورسم التبعيات. والجذر المرسى عند A1 الذي يملأ A1:A10 يجب أن يتلقى حافة من صيغة تقرأ A5 فقط؛ ابدأ البحث الثنائي من الصف 5 وتختفي تلك الحافة بصمت، أي قيمة مخزنة قديمة في تقرير مشحون بدل تقرير بطيء. والاستعلام في الحقيقة من جهتين — إرساء عند Row2 أو قبله، ومخرجات تبلغ Row1 على الأقل — وترتيب فرز واحد لا يستطيع الإجابة عن النصفين. النتائج متعددة الخلايا تظهر في المصنفات الحديثة أيضًا، ويغطي مقال صيغ انسكاب المصفوفات الديناميكية كيف تتصرف النطاقات المنسكبة في HotXLS

شجرة مقاطع لأكبر صفوف المخرجات

يحتفظ HotXLS بفرز الإرساء للحد الأعلى ويضيف شجرة مقاطع معززة للحد الأدنى. يرتب BuildNodeIndex المصفوفة FNodeOrder بمفتاح العقدة كما كان، ثم يملأ BuildMaxOutRowTree المصفوفة FNodeMaxOutRow2 (المخصصة بأربعة مداخيل لكل عقدة) بأكبر OutRow2 موجود تحت كل شجرة جزئية. وينزل QueryNodeTree داخل نافذة المفاتيح فقط ويتخلى عن أي شجرة جزئية يقع صف مخرجاتها الأقصى فوق FRanges[r].Row1، لأنه لا توجد فيها صيغة تصل إلى الصفوف المشار إليها. والأوراق الناجية تمر بكل اختبار RangeIntersectsOutput كاملًا، فتفحص امتدادات الأوراق والأعمدة تمامًا كما قبل

// TXLSDepGraph.BuildNodeIndex / BuildEdges منذ 2.383.1 (مختصرة قليلًا)
procedure BuildMaxOutRowTree(ATreeIndex, ALeft, ARight: Integer);
var
  Mid: Integer;
begin
  if ALeft = ARight then
  begin
    FNodeMaxOutRow2[ATreeIndex] := FNodes[FNodeOrder[ALeft]].OutRow2;
    Exit;
  end;
  Mid := (ALeft + ARight) shr 1;
  BuildMaxOutRowTree(ATreeIndex * 2, ALeft, Mid);
  BuildMaxOutRowTree(ATreeIndex * 2 + 1, Mid + 1, ARight);
  FNodeMaxOutRow2[ATreeIndex] := Max(FNodeMaxOutRow2[ATreeIndex * 2],
    FNodeMaxOutRow2[ATreeIndex * 2 + 1]);
end;

procedure QueryNodeTree(ATreeIndex, ALeft, ARight, ALower, AUpper: Integer);
var
  Split: Integer;
begin
  // خارج نافذة المفاتيح، أو لا مخرجات في هذه الشجرة الجزئية تصل إلى Row1
  if (ARight < ALower) or (ALeft >= AUpper) or
     (FNodeMaxOutRow2[ATreeIndex] < FRanges[r].Row1) then
    Exit;
  if ALeft = ARight then
  begin
    Inc(FEdgeCandidateChecks);
    if RangeIntersectsOutput(FRanges[r], FNodes[FNodeOrder[ALeft]]) then
    begin
      // بلا تغيير: كبت EdgeStamp / ScanStamp، وAddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // الشجرة اليسرى أولًا
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // يحفظ الترتيب القديم
end;

التكرار اليسار-قبل-اليمين ليس اختيار أسلوب. تزار الأوراق الناجية بالترتيب نفسه الذي زارت به حلقة while القديمة إياها، فتمتلئ مصفوفتا Dependents وPrecedents بالمتتالية نفسها ويبقى الترتيب الطوبولوجي حتميًا. والشيء نفسه ينطبق على نوعي الحواف: الحافة الصلبة المسجلة أولًا ما تزال تكبت حافة LookupScan لاحقة للزوج نفسه، بينما تحتفظ حافة المسح المسجلة قبل صلبة بمكانها — وهو التمييز الذي يمنع نطاقات البحث من إنتاج مراجع دائرية كاذبة. ولكل إشارة، يهبط الكلف من حجم النافذة إلى O((k + 1) log n)، حيث k عدد الصيغ التي تصل مخرجاتها فعلًا إلى الصفوف المشار إليها

ماذا يضمن فهرس المخرجات، وكيف يتحقق منه؟

ينتج TXLSDepGraph الحواف نفسها بالترتيب نفسه كما قبل، والخاصية الجديدة EdgeCandidateChecks تحسب كم مستطيل مخرجات اختبره البناء الأخير فعلًا، فالادعاء قابل للقياس لا للخطابة. يبني اختبار الانحدار EdgeBuildDeepChainsCheckOneCandidatePerDependency سلاسل إشارات نقطية من 1,024 و100,000 عقدة، تدرج بترتيب معكوس لفرض الفرز المكاني، ويؤكد بالضبط N − 1 فحصًا — أي 99,999 للسلسلة الطويلة — زائد الترتيب المتوقع للسوابق والتابعات والترتيب الطوبولوجي لكل عقدة. واختبارات مرافقة تغطي جذور مصفوفات مدرجة خارج الترتيب عبر امتدادات أوراق، وإشارات صلبة وبحث مسح مكررة (10 فحوص، بقواعد الكبت أعلاه)، وإعادة بناء بعد AddNode التي تمسح علم الفرز فتبني استدعاء BuildEdges أو NodeIndexOf التالي الشجرة من جديد ويصفر العداد بدل تراكمه

نتائج مقاسة: من 18.5 ثانية إلى نحو 0.1 ثانية

سجل تتبع Win32 السابق للإصلاح، المحفوظ في خط الأساس لأداء المشروع للإصدار 2.383.0، دوّن إعادتي حساب قسريتين بزمن 18,488 و19,578 ميلي ثانية. بعد الفهرسة، قاست ثلاث تشغيلات مركزة متسلسلة لكل معمارية 102.332–109.429 ميلي ثانية على Win32 و116.990–133.995 ميلي ثانية على Win64، أي أسرع بنحو 170 إلى 180 مرة على Win32؛ لم يسجل خط أساس Win64 سابق للإصلاح فلا يدعى تسريع على Win64. واجتازت التشغيلات نفسها البوابة القائمة التي تبقي تدقيق إعادة الحساب للقراءة فقط داخل 1.35 مرة من إعادة الحساب القسرية. الأرقام المطلقة تعتمد على الجهاز وحمله، فأعد إنتاج حمل العمل على عتادك قبل الاقتباس منها

uses
  System.SysUtils, System.Diagnostics, lxHandle;

procedure TimeChainRecalc;
var
  Wb: TXLSWorkbook;
  Sh: TXLSWorksheet;
  I, Failed: Integer;
  Watch: TStopwatch;
begin
  Wb := TXLSWorkbook.Create;
  try
    Sh := Wb.Sheets.Add;
    Sh.Cells[1, 1].Value := 1;
    for I := 2 to 50000 do                     // سلسلة من 49,999 حلقة في العمود A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50,000 تابع في العمود B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // الاستدعاء الأول يبني الرسم
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

أين يتوقف فهرس المخرجات عن الإفادة؟

تقلم الشجرة على الصفوف فقط، ويترك ذلك بضعة حدود صريحة يستحق معرفتها قبل أن تصمم حولها نموذجًا بالغ الضخامة

• إخفاقات الأعمدة ما تزال تدفع عند الأوراق: الصيغ البالغ عددها 2,626 التي تملأ A100:Z200 تصل كلها إلى الصف 100، فإشارة إلى AA100:AA200 تختبر كلًا منها قبل رفضها
• الإشارات العريضة كنطاقات العمود كامل لها سوابق كثيرة حقًا؛ الفهرس يزيل الفحوص المهدورة لا الحواف الحقيقية، وبناء تلك الحواف ما يزال متناسبًا مع عددها
• للإشارات الممتدة عبر عدة أوراق، يتجاهل الأقصى المخزن الورقة، فصيغ الأوراق الوسيطة ذات المخرجات العميقة تبلغ اختبار الورقة؛ تبقى النتائج صحيحة، والتقليم فقط أضعف
• تكلف الشجرة أربعة أعداد صحيحة لكل عقدة صيغة، نحو 1.6 ميغابايت لـ 100,000 عقدة، وأي AddNode يبطلها، فتدفع تغيرات الطوبولوجيا فرزًا كاملًا بـ O(n log n) زائد بناء شجرة بـ O(n) عند بناء الحواف التالي

الشكل التربيعي نفسه في استنساخ أسماء نطاقات التقارير

أصلح الإصدار 2.383.2 مشكلة شقيقة في TXLSXDefinedNames.UniqueCloneName: كل اسم معرف منسوخ كان يعيد بحث اللاحقة من _2، فنمت نسخ نطاقات التقارير المتكررة تربيعيًا في عمليات البحث عن الأسماء. يحفظ فهرس الأسماء المحدودة النطاق الآن تلميح لاحقة لكل اسم أساس وكل نطاق، ويعيد فحص آخر مرشح معاد، لأن المستدعي قد لا يضيفه فعلًا؛ وحذف اسم أو إعادة تسميته أو تغيير نطاقه يبطل الفهرس، فيعود التسمية لأول اسم متاح. في جناح الانحدار، تحتاج 1,024 نسخة متتالية إلى 5,088 بحثًا عن مرشح، وأربعة أسماء أساس متبادلة تحتاج 5,039، بينما هبطت حدود معيار التقرير من نحو 240 ميلي ثانية إلى 18–20 ميلي ثانية. وبوابة توقيت نطاقات التقارير نفسها ما تزال غير مستقرة — ثلاث من ست تشغيلات تجاوزت نسبتها البالغة 1.05 في المحاولة الأولى بعد الإصلاح — ويحتفظ سجل الأداء بتلك الإخفاقات موثقة بدل ضبط العتبة حتى تجتاز

إن كان تطبيقك في Delphi أو C++Builder يولد مصنفات Excel كبيرة أو يعيد حسابها، فإن مكوّن HotXLS Excel لدلفي وC++Builder يأتي بهذا الرسم التبعيات المفهرس في محرك إعادة الحساب لكلا صنفي مصنفاته الكلاسيكي وXLSX