Graf Dependensi HotXLS: Mengindeks Output Array Formula

HotXLS 2.383.1, library Excel native untuk Delphi dan C++Builder, membangun edge dependensi formula lewat indeks interval output: node formula tetap terurut berdasarkan sel jangkar, dan segment tree yang menyimpan baris output terbesar (OutRow2) tiap subtree memungkinkan TXLSDepGraph.BuildEdges melewati seluruh blok formula yang tidak mungkin menjangkau range yang direferensikan. Di workbook Win32 berisi sekitar 100,000 formula, recalculation paksa turun dari 18.488 detik ke 102–109 milidetik

Tidak ada yang mem-profil graf dependensi sampai batch job yang dulu selesai dalam satu detik mulai memakan dua puluh. Graf dibangun ulang setiap kali topologi formula berubah — Recalculate pertama setelah memuat atau menghasilkan workbook, atau pass apa pun setelah graf di-invalidate — dan di trace pra-perbaikan, pass pertama itu sendiri memakan 16,074 ms. Evaluasi tidak pernah jadi masalah; menentukan siapa bergantung pada siapa itulah masalahnya

Mengapa recalculation 100,000 formula memakan 18 detik?

Edge builder lama berperilaku kuadratik terhadap jumlah formula di satu sheet. Untuk setiap range dependensi, BuildEdges melakukan binary search atas window node kandidat lalu menguji masing-masing dengan RangeIntersectsOutput, dan window itu dimulai di puncak sheet yang direferensikan. Key node berasal dari XLSDepMakeKey yang mengemas indeks sheet dari bit 34 ke atas, baris ke bit 14–33, dan kolom ke bit 0–13, sehingga lower bound (Sheet1, 0, 0) berarti "setiap formula dari baris 1 sampai dasar range yang direferensikan"

// Sebelum 2.383.1 - TXLSDepGraph.BuildEdges, untuk range dependensi r milik node d
LowerKey := XLSDepMakeKey(FRanges[r].Sheet1, 0, 0);   // puncak sheet
UpperKey := XLSDepMakeKey(FRanges[r].Sheet2, FRanges[r].Row2, 16383);
// ...dua binary search atas FNodeOrder menghasilkan window [i, Lo)...
while i < Lo do
begin
  NodeIndex := FNodeOrder[i];
  if RangeIntersectsOutput(FRanges[r], FNodes[NodeIndex]) then
  begin
    // hard edge atau edge LookupScan, dideuplikasi lewat EdgeStamp / ScanStamp
  end;
  Inc(i);
end;

Fixture performa yang membongkar ini adalah model kaskade biasa: A2:A50000 masing-masing menambah satu ke sel di atasnya, dan B1:B50000 masing-masing menduakan tetangga di kolom A. Referensi ke baris r dengan demikian menyeret sekitar 2r kandidat melewati uji persegi panjang, jadi satu kali pembangunan graf melakukan sekitar lima miliar pemeriksaan irisan — estimasi kasar di punggung amplop, tapi cocok dengan 18.5 detik di jam. Setiap pemeriksaan menjawab "tidak" kecuali satu atau dua

Mengapa edge builder tidak bisa memulai pencarian di baris yang direferensikan?

Karena array formula yang jangkarnya di atas sebuah range bisa memiliki sel di dalamnya. Setiap TXLSDepNode mendeskripsikan persegi output dari jangkarnya (Row, Col) sampai (OutRow2, OutCol2), dan array formula CSE mendapat satu node untuk seluruh persegi-nya, seperti dijelaskan artikel soal incremental recalculation dan graf dependensi. Root yang berjangkar di A1 dan mengisi A1:A10 tetap harus menerima edge dari formula yang hanya membaca A5; mulai binary search di baris 5 dan edge itu hilang diam-diam, yang berarti nilai cache basi di laporan yang sudah terkirim alih-alih laporan yang lambat. Query-nya sebenarnya dua sisi — jangkar di atau sebelum Row2, output menjangkau setidaknya Row1 — dan satu urutan sort tidak bisa menjawab kedua sisinya. Hasil multi-sel juga muncul di workbook modern, dan artikel soal dynamic array spill formulas membahas perilaku range spill di HotXLS

Segment tree baris output maksimum

HotXLS mempertahankan sort jangkar untuk upper bound dan menambahkan segment tree ter-augmentasi untuk lower bound. BuildNodeIndex mengurutkan FNodeOrder berdasarkan key node seperti sebelumnya, lalu BuildMaxOutRowTree mengisi FNodeMaxOutRow2 (dialokasi empat entri per node) dengan OutRow2 terbesar yang ditemukan di bawah tiap subtree. QueryNodeTree turun hanya di dalam window key dan meninggalkan subtree mana pun yang baris output maksimumnya berada di atas FRanges[r].Row1, karena tak ada formula di dalamnya yang mampu menjangkau baris yang direferensikan. Daun yang selamat tetap melewati uji RangeIntersectsOutput penuh, sehingga rentang sheet dan kolom diperiksa persis seperti sebelumnya

// TXLSDepGraph.BuildNodeIndex / BuildEdges sejak 2.383.1 (diringkas ringan)
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
  // di luar window key, atau tak ada output di subtree ini yang menjangkau 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
      // tak berubah: supresi EdgeStamp / ScanStamp, AddDependent / AddScanDependent
    end;
    Exit;
  end;
  Split := (ALeft + ARight) shr 1;
  QueryNodeTree(ATreeIndex * 2, ALeft, Split, ALower, AUpper);           // subtree kiri dulu
  QueryNodeTree(ATreeIndex * 2 + 1, Split + 1, ARight, ALower, AUpper);  // menjaga urutan lama
end;

Rekursi kiri-dahulu-kanan bukan pilihan gaya. Daun yang selamat dikunjungi dalam urutan persis seperti kunjungan loop while lama, sehingga array Dependents dan Precedents terisi dalam sekuens yang sama dan urutan topologis tetap deterministik. Hal yang sama berlaku untuk dua jenis edge: hard edge yang tercatat lebih dulu tetap menekan edge LookupScan yang datang belakangan untuk pasangan yang sama, sementara scan edge yang tercatat sebelum hard edge mempertahankan tempatnya — pembeda yang menghentikan range lookup dari menghasilkan circular reference palsu. Per referensi, biaya turun dari ukuran window ke O((k + 1) log n), dengan k adalah jumlah formula yang outputnya benar-benar menjangkau baris yang direferensikan

Apa jaminan indeks output, dan bagaimana ia diverifikasi?

TXLSDepGraph menghasilkan edge yang sama dalam urutan yang sama seperti sebelumnya, dan properti EdgeCandidateChecks yang baru menghitung berapa persegi output yang benar-benar diuji build terakhir, sehingga klaimnya terukur, bukan sekadar retorika. Regression test EdgeBuildDeepChainsCheckOneCandidatePerDependency membangun rantai referensi titik berisi 1,024 dan 100,000 node, disisipkan dalam urutan terbalik untuk memaksa sort spasial, dan mengasertifkan tepat N − 1 pemeriksaan — 99,999 untuk rantai panjang — plus urutan precedent, dependent, dan topologis yang diharapkan untuk setiap node. Test pendamping mencakup root array yang disisipkan tak berurutan lintas rentang sheet, referensi hard dan lookup-scan duplikat (10 pemeriksaan, dengan aturan supresi di atas), dan rebuild setelah AddNode, yang menghapus flag sort sehingga BuildEdges atau NodeIndexOf berikutnya membangun ulang tree dan mereset counter alih-alih mengakumulasinya

Hasil terukur: dari 18.5 detik ke sekitar 0.1 detik

Trace Win32 pra-perbaikan, yang disimpan di baseline performa proyek untuk versi 2.383.0, mencatat dua recalculation paksa sebesar 18,488 ms dan 19,578 ms. Setelah pengindeksan, tiga run fokus serial per arsitektur terukur 102.332–109.429 ms di Win32 dan 116.990–133.995 ms di Win64, kira-kira 170 sampai 180 kali lebih cepat di Win32; baseline Win64 pra-perbaikan tidak direkam, jadi tidak ada klaim percepatan Win64. Run yang sama lolos gate yang sudah ada yang menjaga audit recalculation read-only tetap dalam 1.35 kali recalculation paksa. Angka absolut bergantung pada mesin dan bebannya, jadi replikasi workload-nya di perangkat keras Anda sendiri sebelum mengutipnya

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                     // rantai 49,999 tautan di kolom A
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // 50,000 dependent di kolom B
      Sh.Cells[I, 2].Formula := '=A' + IntToStr(I) + '*2';

    Watch := TStopwatch.StartNew;
    Failed := Wb.Recalculate;                  // panggilan pertama membangun graf
    Watch.Stop;
    Writeln(Format('%d formulas not evaluated, %.1f ms',
      [Failed, Watch.Elapsed.TotalMilliseconds]));
  finally
    Wb.Free;
  end;
end;

Di mana indeks output berhenti membantu?

Tree-nya hanya melakukan pruning pada baris, dan itu menyisakan beberapa batas jujur yang layak diketahui sebelum Anda merancang model sangat besar di atasnya

• Meleset kolom tetap dibayar di daun: 2,626 formula yang mengisi A100:Z200 semuanya menjangkau baris 100, jadi referensi ke AA100:AA200 menguji masing-masing sebelum menolaknya
• Referensi lebar seperti range satu kolom penuh memang punya banyak precedent; indeks membuang pemeriksaan yang sia-sia, bukan edge yang nyata, dan membangun edge-edge itu tetap proporsional terhadap jumlahnya
• Untuk referensi yang membentang beberapa sheet, maksimum tersimpan mengabaikan sheet, sehingga formula di sheet antara dengan output dalam tetap sampai ke uji daun; hasilnya tetap benar, hanya pruning-nya lebih lemah
• Tree memakan empat integer per node formula, sekitar 1.6 MB untuk 100,000 node, dan AddNode apa pun meng-invalidate-nya, sehingga perubahan topologi membayar re-sort O(n log n) penuh plus pembangunan tree O(n) pada edge build berikutnya

Bentuk kuadratik yang sama di kloning nama report-band

Versi 2.383.2 memperbaiki masalah saudara di TXLSXDefinedNames.UniqueCloneName: setiap defined name yang dikloning memulai ulang pencarian sufiksnya di _2, sehingga kloning report-band yang berulang tumbuh kuadratik dalam lookup nama. Indeks nama ter-scope kini menyimpan hint sufiks per nama dasar, per scope, dan memeriksa ulang kandidat terakhir yang dikembalikan, karena caller bisa saja tidak benar-benar menambahkannya; menghapus, mengganti nama, atau mengganti scope sebuah nama meng-invalidate indeks, yang memulihkan penamaan ketersediaan-pertama. Di regression suite, 1,024 klon berurutan butuh 5,088 lookup kandidat dan empat nama dasar bergantian butuh 5,039, sementara minimum benchmark laporan turun dari sekitar 240 ms ke 18–20 ms. Gate timing report-band sendiri masih belum stabil — tiga dari enam run melampaui rasio 1.05-nya di percobaan pertama pasca-perbaikan — dan riwayat performa menyimpan kegagalan itu sebagai catatan alih-alih menyetel ulang ambangnya sampai lolos

Kalau aplikasi Delphi atau C++Builder Anda menghasilkan atau menghitung ulang workbook Excel berukuran besar, komponen Excel HotXLS untuk Delphi dan C++Builder menyertakan graf dependensi terindeks ini di engine recalculation untuk kedua kelas workbook klasik dan XLSX-nya