HotXLS 相依圖的輸出區間索引與線段樹

HotXLS 2.383.1 這套 Delphi 與 C++Builder 的原生 Excel 函式庫，改用輸出區間索引來建立公式相依邊：公式節點維持按錨定儲存格排序，而一棵保存每棵子樹最大輸出列（OutRow2）的線段樹，讓 TXLSDepGraph.BuildEdges 能整段跳過碰不到參照範圍的公式。在一本約 100,000 條公式的 Win32 活頁簿上，強制重新計算從 18.488 秒降到 102–109 毫秒

沒人會去 profile 相依圖，直到某個原本一秒跑完的批次工作開始要二十秒。圖會在公式拓撲變動時重建——載入或產生活頁簿之後的第一次 Recalculate，或圖被失效後的任何一遍——而在修正前的追蹤記錄裡，光是那第一遍就花了 16,074 ms。求值從來不是問題；判斷誰相依於誰才是

重新計算 100,000 條公式為什麼要 18 秒？

舊的邊建立器對工作表上的公式數量是平方級的。對每個相依範圍，BuildEdges 會二分搜尋出一個候選節點視窗，再用 RangeIntersectsOutput 逐一測試，而這個視窗的起點就在被參照工作表的最頂端。節點鍵值來自 XLSDepMakeKey，它把工作表索引從第 34 位元以上打包、列放進第 14–33 位元、欄放進第 0–13 位元，所以下界 (Sheet1, 0, 0) 意味著「從第 1 列一路到被參照範圍底部的每一條公式」

// 2.383.1 之前——TXLSDepGraph.BuildEdges，處理節點 d 的相依範圍 r
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——單一排序無法同時回答兩半。多儲存格結果在現代活頁簿裡也會出現，動態陣列 spill 公式一文涵蓋 spill 範圍在 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 邊，而先於硬邊記錄的掃描邊保住自己的位置——正是這個區別讓 lookup 範圍不會產生誤判的循環參照。每個參照的成本從視窗大小降到 O((k + 1) log n)，k 是輸出真的抵達被參照列的公式數

輸出索引保證了什麼，又怎麼驗證？

TXLSDepGraph 產出與以前相同順序的相同邊，而新的 EdgeCandidateChecks 屬性會數最近一次建圖實際測試了多少個輸出矩形，所以這個主張可以量測、不是空話。迴歸測試 EdgeBuildDeepChainsCheckOneCandidatePerDependency 建立 1,024 與 100,000 節點的點參照鏈，以逆序插入逼出空間排序，並斷言恰好 N − 1 次檢查——長鏈是 99,999 次——外加每個節點預期的前驅、後繼與拓撲順序。配套測試涵蓋跨工作表跨度亂序插入的陣列根、重複的硬與 lookup 掃描參照（10 次檢查，套用上述抑制規則），以及 AddNode 之後的重建——它會清掉排序旗標，讓下一次 BuildEdges 或 NodeIndexOf 重建樹並把計數器歸零而不是累加

實測結果：從 18.5 秒到約 0.1 秒

修正前留存在 2.383.0 專案效能基準裡的 Win32 追蹤記錄，記下了 18,488 ms 與 19,578 ms 兩次強制重新計算。加入索引之後，每個架構跑三輪序列的焦點測量，Win32 是 102.332–109.429 ms、Win64 是 116.990–133.995 ms，Win32 大約快了 170 到 180 倍；修正前沒有留下 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                     // A 欄的 49,999 節鏈
      Sh.Cells[I, 1].Formula := '=A' + IntToStr(I - 1) + '+1';
    for I := 1 to 50000 do                     // B 欄的 50,000 個相依者
      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;

輸出索引在哪裡幫不上忙？

這棵樹只對列做剪枝，這留下了幾個老實的限制，在圍繞它設計超大模型之前值得知道

• 欄位失配仍然在葉子上付帳：填滿 A100:Z200 的 2,626 條公式全都抵達第 100 列，所以對 AA100:AA200 的參照會逐一測試它們之後才拒絕
• 整欄範圍這類寬參照是真的有很多前驅；索引移除的是浪費的檢查，不是真實的邊，而建立那些邊仍然與其數量成正比
• 跨多個工作表的參照，儲存的最大值無視工作表，所以中間工作表上輸出很深的公式會抵達葉子測試；結果保持正確，只是剪枝變弱
• 這棵樹每個公式節點花四個整數，100,000 個節點約 1.6 MB，而任何 AddNode 都會使它失效，所以拓撲變動要在下一次建邊時付一次完整的 O(n log n) 重排序加 O(n) 的建樹

報表帶名稱複製裡同樣的平方級形狀

2.383.2 版修掉了 TXLSXDefinedNames.UniqueCloneName 裡的一個兄弟問題：每個複製出來的定義名稱都從 _2 重新開始找後綴，所以反覆複製報表帶會讓名稱查找平方級成長。限定範圍的名稱索引現在為每個基底名稱、每個範圍保存後綴提示，並重新檢查上一次回傳的候選，因為呼叫端可能根本沒把它加進去；刪除、改名或改範圍會讓索引失效，回到先到先得的命名。在迴歸套件裡，1,024 個連續複製需要 5,088 次候選查找、四個交替基底名稱需要 5,039 次，而報表基準測試的最小值從約 240 ms 降到 18–20 ms。報表帶的計時關卡本身仍然不穩定——修正後第一次嘗試就有六輪中的三輪超出它的 1.05 比例——效能歷史把那些失敗留在記錄上，而不是把門檻調到通過為止

如果您的 Delphi 或 C++Builder 應用程式會產生或重新計算大型 Excel 活頁簿，適用 Delphi 與 C++Builder 的 HotXLS Excel 元件已在重新計算引擎裡為 Classic 與 XLSX 兩種活頁簿類別搭載這套索引化的相依圖