技術文章

Delphi 中的 XLOOKUP 與 XMATCH 二分搜尋模式

HotXLS,這套原生的 Delphi 與 C++Builder 試算表元件,透過一個共用的查找核心來評估 XLOOKUP 與 XMATCH。這個核心接受四種比對模式(-1、0、1、2)與四種搜尋模式(-2、-1、1、2),只要搜尋模式的絕對值是 2 就跑一趟對數時間的二分下降,其他任何組合一律以公式錯誤拒絕

把你帶到這裡的錯誤回報從來不會說「搜尋模式」。它說的是伺服器產生的活頁簿顯示的數字跟在 Excel 裡打開同一份檔案不一樣,大概九千列裡有四列。那四列總有些共同點:一個重複的查找鍵,或是一個需要挑鄰居的近似比對,或是一欄上週被人按別的欄重新排序過的查找欄。查找函式正是公式引擎不再只是算術、開始變成一份合約的地方,而這份合約有大多數呼叫端從沒讀過的條款

XLOOKUP 實際上接受哪些模式數字?

各恰好四個,沒有其他。HotXLS 在碰任何一個儲存格之前,就會先把 match_mode 對照 -1、0、1、2 驗證,把 search_mode 對照 -2、-1、1、2 驗證,任何其他值都會回傳 #VALUE!,而不是被夾進最接近的合法模式。四種比對模式是 0 表示精確、-1 表示精確或次小、1 表示精確或次大、2 表示萬用字元;四種搜尋模式是 1 表示正向線性掃描、-1 表示反向線性掃描、2 表示對遞增資料做二分搜尋、-2 表示對遞減資料做二分搜尋。省略它們會選用比對模式 0 與搜尋模式 1,這是幾乎所有真實公式都在用的搭配。引數個數也是同樣把關方式:XLOOKUP 接受三到六個引數,XMATCH 接受兩到四個,超出這些範圍在求值開始之前就會回傳 #VALUE!

// Shared by XLOOKUP and XMATCH, before any cell is read
if ((RequestedMatchMode <> -1) and (RequestedMatchMode <> 0) and
    (RequestedMatchMode <> 1) and (RequestedMatchMode <> 2)) or
   ((RequestedSearchMode <> -2) and (RequestedSearchMode <> -1) and
    (RequestedSearchMode <> 1) and (RequestedSearchMode <> 2)) then
begin
  Result := lxErrorValue;          // #VALUE!
  Exit;
end;

if Abs(RequestedSearchMode) = 2 then
begin
  if RequestedMatchMode = 2 then   // wildcards cannot ride a binary descent
  begin
    Result := lxErrorValue;
    Exit;
  end;
  // ... O(log n) descent over the lookup vector
end;

再早一步,還有一個較不起眼、卻值得知道的檢查。模式引數是以工作表運算式的形式抵達的,所以 HotXLS 會把它們強制轉成數字、拒絕 NaN 與無窮大,接著要求這個數字必須等於它自己四捨五入後的值。XLOOKUP(x, A:A, B:B, "none", 0, 1.5) 是一個 #VALUE!,不是偽裝成的搜尋模式 2。當模式來自一個由四捨五入密集計算所產生的儲存格時,這一點就很要緊,這在自動產生的活頁簿裡比手寫的常見得多

為何 search_mode 2 在未排序資料上會給出錯誤答案?

因為它正在做你要求它做的事。搜尋模式 2 告訴引擎查找向量已經是遞增排序,而二分搜尋沒辦法在不做一次會摧毀使用它的意義的 O(n) 掃描的情況下驗證這個宣稱。因此 HotXLS 信任呼叫端,對半分割區間,回傳下降過程落腳的結果。在未排序輸入上,答案不是錯誤訊息,而是悄悄錯誤,這是違反合約,不是引擎的缺陷

微軟為 XLOOKUP 與 XMATCH 記載了同樣的不對稱:二分模式需要排序過的資料,否則結果無效。定義 SpreadsheetML 公式文法的 ISO 29500-1 第 18.17 條,帶著較老的 LOOKUP 與 VLOOKUP 描述及它們自己的遞增順序要求,而 XLOOKUP 與 XMATCH 出現得夠晚,以至於它們在檔案裡是以 _xlfn.XLOOKUP_xlfn.XMATCH 的形式、依循未來函式慣例傳遞。世代不同,交易一樣:呼叫端提供排序不變量,引擎提供對數複雜度

var
  Book: TXLSXWorkbook;
  Sheet: TXLSXWorksheet;
begin
  Book := TXLSXWorkbook.Create;
  try
    Sheet := Book.Sheets.Add('Rates');
    Sheet.Cells[1, 1].Value := 40;  Sheet.Cells[1, 2].Value := 0.10;
    Sheet.Cells[2, 1].Value := 10;  Sheet.Cells[2, 2].Value := 0.25;
    Sheet.Cells[3, 1].Value := 30;  Sheet.Cells[3, 2].Value := 0.15;

    // Forward linear scan: finds key 40 wherever it sits
    Sheet.Cells[5, 1].Formula := 'XLOOKUP(40,A1:A3,B1:B3,"missing",0,1)';
    // Binary ascending: the promise was broken, the key is never visited
    Sheet.Cells[6, 1].Formula := 'XLOOKUP(40,A1:A3,B1:B3,"missing",0,2)';

    Book.SaveAs('lookup-modes.xlsx');
  finally
    Book.Free;
  end;
end;

追蹤第二條公式,失敗就完全是機械性的。下降過程探測中間儲存格,讀到 10,判定 10 比 40 小,捨棄左半邊,包括那一列其實放著 40 的地方,探測 30,再次捨棄,區間耗盡。Excel 的行為一模一樣,這正是重點所在:重現這個錯誤答案是一項相容性需求,不是一種禮貌。排序前提也比「數字遞增」更嚴格,因為比較器先按種類排名,順序是數字、然後文字、然後布林值、然後錯誤值、然後空白,只有在同一種類內才會比較。一欄數值零件編號,若混進三個儲存格存的是文字而非數字,就不算是這個比較器眼中的遞增,無論在螢幕上看起來多整齊,二分模式都會欣然誤讀它

重複鍵會落在哪裡?

落在重複區段一個確定的一端,而是哪一端取決於搜尋模式,不是靠運氣。當二分下降在搜尋模式 2 之下命中一個相等的鍵時,它會記下位置,然後繼續往左收窄,所以結果是這段區間裡最小的索引;在搜尋模式 -2 之下,對遞減資料而言,它記下位置後往右收窄,所以結果是最大的索引。線性模式比較簡單:搜尋模式 1 回傳正向遇到的第一個命中,搜尋模式 -1 回傳反向遇到的第一個命中。這正是開頭那個四列差異的成因,因為一份鍵值全部唯一的活頁簿,在全部四種搜尋模式下給出的答案完全一樣,會在你從一份乾淨的樣本檔寫的每項測試裡把差異藏起來。生產資料裡只要多一個重複的客戶代碼,各模式就會開始在正好重複的那幾列上意見不合:引擎裡什麼都沒變,只是輸入不再是一個集合,而變成了一個多重集合

// A1:A7 holds 1, 3, 5, 5, 5, 7, 9 - ascending, with a run of three
Sheet.Cells[1, 3].Formula := 'XMATCH(5,A1:A7,0,1)';   // 3, first forward hit
Sheet.Cells[2, 3].Formula := 'XMATCH(5,A1:A7,0,-1)';  // 5, first reverse hit
Sheet.Cells[3, 3].Formula := 'XMATCH(5,A1:A7,0,2)';   // 3, lowest index of the run

// B1:B7 holds 9, 7, 5, 5, 5, 3, 1 - descending
Sheet.Cells[4, 3].Formula := 'XMATCH(5,B1:B7,0,-2)';  // 5, highest index of the run

近似比對如何選出候補?

做法是在精確比對搜尋的同時保留一個最佳候選,只有在沒有精確命中時才回傳它。HotXLS 把 match_mode -1 當成「不大於目標的最大值」,把 match_mode 1 當成「不小於目標的最小值」,兩者都是在整個被掃描的區域上求解,而不是在遇到第一個可接受的鄰居時就停下。在二分路徑裡,同樣的概念從下降過程裡自然浮現:每一步只要超調或低估,就更新候選,所以最終候選是緊鄰鍵值本該插入位置旁的邊界元素

// Linear path: refine the candidate only on a strict improvement
if (RequestedMatchMode = -1) or (RequestedMatchMode = 1) then
begin
  CompareResult := CompareDynamicValues(CurrentValue, RequestedValue);
  if ((RequestedMatchMode = -1) and (CompareResult <= 0) and
      ((CandidateIndex < 0) or
       (CompareDynamicValues(CurrentValue, CandidateValue) > 0))) or
     ((RequestedMatchMode = 1) and (CompareResult >= 0) and
      ((CandidateIndex < 0) or
       (CompareDynamicValues(CurrentValue, CandidateValue) < 0))) then
  begin
    CandidateIndex := ScanIndex;
    CandidateValue := CurrentValue;
  end;
end;

仔細看內層條件,決勝點就在那裡。一個新的儲存格只有在嚴格更好時才會取代現有候選,永遠不會在僅僅相等時取代,所以在幾個持有相同候補值的儲存格中,被保留的是掃描順序裡先遇到的那一個:正向掃描下是最小索引,反向掃描下是最大索引。如果 XLOOKUP 與 XMATCH 既找不到精確命中,也找不到可接受的鄰居,XLOOKUP 在提供了 if_not_found 引數時會退回它,沒提供則回傳 #N/A,而 XMATCH 永遠回傳 #N/A

為何萬用字元與二分搜尋無法共存?

因為一個萬用字元模式不是順序中的一個位置。比對模式 2 問的是某個儲存格是否符合一個遮罩,遮罩比對回答的是是或否;而二分下降需要的是一個三向答案,告訴它該保留哪一半。沒有站得住腳的方式能回答 ACME-* 位於某個給定儲存格的左邊還是右邊,所以 HotXLS 一律以 #VALUE! 直接拒絕 match_mode 2 搭配 search_mode 2 或 -2 的組合,而不是猜一個順序、產出貌似合理的胡說。這兩條路徑比較值的方式也不同,這進一步強化了這個分隔:線性掃描用不分大小寫的文字比較來判定相等,萬用字元開啟時則用遮罩比對,而二分下降則是靠向排序比較器詢問是否為零來判定相等。這是刻意的設計,不是分層時的意外,因為二分路徑只能使用它實際依循導航的那個關係。如果你需要萬用字元,就用搜尋模式 1 或 -1,接受線性成本,這與增量重新計算背後的依賴追蹤設計,把成本擋在你的關鍵路徑之外,是同一套取捨

形狀錯誤:二維範圍與不匹配的回傳向量

兩個函式都要求查找範圍是名副其實的一維。如果提供的範圍同時橫跨超過一列與超過一欄,HotXLS 會回傳 #VALUE!,而不是替你挑一個軸,單列或單欄的範圍則沿著它的長軸讀取。XLOOKUP 多加了一條形狀規則:回傳範圍沿著比對軸的長度必須與查找範圍完全一致,所以一個 500 列的垂直查找搭配一個 499 列的回傳範圍是一個錯誤,而不是在最後一列被悄悄地按差一修正。當回傳範圍在垂直查找時寬過一欄,或在水平查找時高過一列,XLOOKUP 會把整個比對到的切片以陣列形式回傳,並依循與其他動態陣列函式相同的規則溢出到相鄰儲存格,說明於溢出範圍與動態陣列一文。這對用一個公式從表格裡拉出整筆紀錄確實非常有用,也是不小心覆蓋掉你本想保留的欄最快的方式

沒人盯著螢幕時如何選擇模式

伺服器端產生應該採用比互動使用更嚴格的政策,因為沒有人能察覺總計看起來不對。站得住腳的預設是搜尋模式 1 搭配比對模式 0:線性、精確、與順序無關,也不會因為重新排序一張表而失效。只有在同一條程式路徑也產生了那個順序、在同一次執行、同一欄上時,才該伸手用搜尋模式 2,並把這個依賴關係寫在公式旁邊,因為對一欄被別的鍵排序過的資料做二分搜尋,是計算出一個看似可信、實則錯誤數字最便宜的方式。當查找真正是熱點、資料也真正排序過時,回報是真實的:下降過程讀取大約 log n 個儲存格而不是 n 個,而其中每一次讀取都要走一次完整的工作簿儲存格解析,所以節省下來的比指令數字所暗示的還要多

如果問題的形狀更接近一條領域規則,而不是一次查找,回呼你自己的 Pascal 程式碼,如自訂工作表函式一文所述,通常會勝過任何巧妙安排內建函式的方式。這裡討論的 XLOOKUP 與 XMATCH 實作,隨標準版 HotXLS Delphi 試算表元件一併出貨,其產品頁面收錄 Delphi 與 C++Builder 的完整支援函式參考