LlosLabソフトウェア開発ブログPDF、Delphi、およびドキュメントソフトウェア開発者向けのエンジニアリングノート。

技術記事

DelphiにおけるXLOOKUPとXMATCHのバイナリサーチモード

HotXLS Component

Delphi・C++Builder向けのネイティブスプレッドシートコンポーネントであるHotXLSは、XLOOKUPとXMATCHを1つの共有ルックアップコアを通じて評価する。そのコアは4つのmatch mode(-1、0、1、2)と4つのsearch mode(-2、-1、1、2)を受け付け、絶対値のsearch modeが2のときは常に対数的なバイナリ降下を実行し、それ以外のすべての組み合わせは数式エラーで拒否する

あなたをここに送り込むバグレポートは「search mode」とは決して言わない。サーバー生成のワークブックが、Excelで同じファイルを開いたときと違う数字を、9000行のうち多くて4行くらいに表示している、と言うだけだ。その4行にはいつも何か共通点がある:重複したルックアップキー、隣接セルを選ばなければならなかった近似一致、あるいは先週誰かが別の列でソートしたルックアップ列。ルックアップ関数は、数式エンジンが単なる算術であることをやめて契約になる場所であり、その契約には実際のところほとんどの呼び出し側が読まない条項がある

XLOOKUPが実際に受け付けるモード番号はどれか

それぞれちょうど4つだけで、それ以外はない。HotXLSは、単一のセルに触れる前にmatch_modeを-1、0、1、2に対して、search_modeを-2、-1、1、2に対して検証し、それ以外の値は最も近い正当なモードにクランプされるのではなく#VALUE!を返す。4つのmatch modeは、完全一致には0、完全一致または直下の小さい値には-1、完全一致または直上の大きい値には1、ワイルドカードには2だ。4つのsearch modeは、前方線形スキャンには1、後方線形スキャンには-1、昇順データに対するバイナリサーチには2、降順データに対するバイナリサーチには-2だ。これらを省略するとmatch mode 0とsearch mode 1が選ばれ、これはほとんどすべての実際の数式が使う組み合わせだ。引数の個数も同様に規制されている:XLOOKUPは3から6の引数を、XMATCHは2から4の引数を取り、その範囲外はどれも評価が始まる前に#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;

その1つ前の段階に、知っておく価値のある静かなチェックがある。モード引数はワークシートの式として届くので、HotXLSはそれを数値に変換し、NaNと無限大を拒否し、その数値が自分自身の丸め値と等しいことを要求する。XLOOKUP(x, A:A, B:B, "none", 0, 1.5)は#VALUE!であり、変装したsearch mode 2ではない。これは、丸め処理の多い計算が生成したセルからモードが来る場合に重要になる。これは手書きのワークブックよりも生成されたワークブックでより一般的だ

なぜsearch_mode 2はソートされていないデータで間違った答えを出すのか

それはまさにあなたが依頼した通りのことをしているからだ。search mode 2は、ルックアップベクターがすでに昇順であることをエンジンに伝えるものであり、バイナリサーチはその使用理由を破壊してしまうようなO(n)のパスなしにはその主張を検証できない。したがってHotXLSは呼び出し側を信頼し、区間を半分にし、降下が着地した場所を何であれ返す。ソートされていない入力に対して、答えはエラーではなく黙って間違っており、これはエンジンの欠陥ではなく契約違反だ

Microsoftは、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;

2番目の数式をトレースすると、その失敗は完全に機械的だ。降下は中央のセルを探り、10を読み、10は40より小さいと判断し、40を実際に保持していた行を含む左半分を捨て、30を探り、また捨て、区間を使い果たす。Excelも同じように振る舞う——それが要点だ。間違った答えを再現することは礼儀ではなく互換性の要件だ。順序の前提はまた「数字が昇順である」よりも厳しい。比較器はまず種類によって値をランク付けするからだ。順序は数値、次にテキスト、次にブール値、次にエラー値、次に空白であり、種類の中での比較はその後にのみ行われる。テキストとして格納された3つのセルを持つ数値部品コード列は、画面上でどう見えようとその比較器の下では昇順ではなく、バイナリモードは喜んでそれを誤読する

重複キーはどこに着地するのか

重複の連続における決定論的な端に着地し、どちらの端になるかは運ではなくsearch modeに依存する。バイナリ降下が等しいキーに当たると、search mode 2の下ではその位置を記録し左に狭め続けるので、結果はその連続の最低インデックスになる。降順データに対するsearch mode -2では、位置を記録し右に狭めるので、結果は最高インデックスになる。線形モードはより単純だ:search mode 1は前方への最初のヒットを返し、search mode -1は後方への最初のヒットを返す。これが冒頭の段落の4行の不一致を生む細部であり、キーが一意であるワークブックはすべての4つのsearch modeの下で同一の答えを出し、あなたがクリーンなサンプルファイルから書いたすべてのテストを通じてその違いを隠してしまう。本番データに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を返す

なぜワイルドカードとバイナリサーチは共存できないのか

ワイルドカードパターンは順序の中の位置ではないからだ。match mode 2はセルがマスクに一致するかどうかを尋ね、マスクマッチングはイエスかノーで答える。バイナリ降下は、どちらの半分を残すべきかを教えてくれる三択の答えを必要とする。ACME-*がある特定のセルの左にあるか右にあるかを尋ねる筋の通った方法はないので、HotXLSはmatch_mode 2とsearch_mode 2または-2の組み合わせを、順序を推測してもっともらしいナンセンスを生成する代わりに、最初から#VALUE!で拒否する。この2つのパスはまた値の比較も異なる方法で行っており、それがこの分割を強めている:線形スキャンは大文字小文字を区別しないテキスト比較で、あるいはワイルドカードが有効ならマスクマッチングで等価性を決定するが、バイナリ降下は順序比較器にゼロを尋ねることで等価性を決定する。これは意図的なものであり、階層化の偶然ではない。バイナリパスは、実際に自分がナビゲートしている関係だけを使うことができるからだ。ワイルドカードが必要なら、search mode 1か-1を使い、線形コストを受け入れよう。それはインクリメンタル再計算の背後にある依存関係トラッキングが、あなたのクリティカルパスから遠ざけるよう設計されているのと同じトレードオフだ

形状エラー:二次元範囲と一致しない戻り値ベクター

両方の関数は本物の一次元ルックアップ範囲を要求する。供給された範囲が同時に複数の行と複数の列にまたがっている場合、HotXLSは軸をあなたの代わりに選ぶのではなく#VALUE!を返し、単一行または単一列の範囲はその長い軸に沿って読まれる。XLOOKUPには2つ目の形状ルールがある:戻り値の範囲は、一致する軸に沿ってルックアップ範囲と正確に同じ長さでなければならない。したがって500行にわたる垂直ルックアップと499行の戻り値範囲のペアはエラーであり、最終行で黙って解決されるオフバイワンではない。戻り値の範囲が垂直ルックアップに対して1列より広い、あるいは水平ルックアップに対して1行より高い場合、XLOOKUPは一致したスライス全体を配列として返し、それは他の動的配列関数と同じルールの下で隣接セルにスピルする。これはスピル範囲と動的配列の記事で説明されている。これは1つの数式でテーブルから1件のレコード全体を引き出すのに本当に便利であり、同時に保持しておくつもりだった列を上書きしてしまう最も手っ取り早い方法でもある

誰も画面を見ていないときにモードを選ぶ

サーバーサイドの生成は、対話的な使用よりも厳格なポリシーに値する。合計がおかしく見えることに気づく人間がいないからだ。無難なデフォルトはmatch mode 0を伴うsearch mode 1だ:線形で、完全一致で、順序に依存せず、シートを再ソートしても無効にならない。search mode 2に手を伸ばすのは、同じコードパスが同じ実行内で、同じ列にわたって、その順序も生成した場合だけにし、その依存関係を数式の隣に書き留めておこう。異なるキーでソートされた列に対するバイナリサーチは、自信ありげな間違った数字を計算する最も安上がりな方法だからだ。ルックアップが本当にホットで、データが本当にソートされている場合、見返りは本物だ:降下はn個ではなくおおよそlog n個のセルを読み、その各読み取りはワークブックのセル解決をフルに経由するので、節約は命令数が示唆するよりも大きい

問題の形が、ルックアップよりもドメインルールに近い場合、カスタムワークシート関数の記事で扱っている、自分自身のPascalコードへのコールバックが、組み込み関数のどんな巧妙な配置よりも通常は勝つだろう。ここで論じたXLOOKUPとXMATCHの実装は、標準のHotXLS Delphiスプレッドシートコンポーネントに付属しており、その製品ページにはDelphiとC++Builder向けのサポートされている関数の完全なリファレンスがある