Режимы двоичного поиска XLOOKUP и XMATCH в Delphi

На ключах 1, 3, 5, 5, 5, 7, 9 в A1:A7 формула XMATCH(5, A1:A7, 0, 2) возвращает 3. Смените только последний аргумент на -1, и та же формула вернёт 5. Наведите первую версию на колонку, которую кто-то пересортировал по другому полю, — и 5, отчётливо видимая на листе, может вернуться как #N/A. Все три ответа верны. Последний аргумент XMATCH, как шестой аргумент XLOOKUP, — две вещи разом: указание, какой дубликат предпочесть, и обещание о том, как упорядочены данные

Отчёт, приводящий сюда, редко упоминает режимы поиска. Он говорит, что сгенерированная книга расходится с чьим-то ожиданием на горстке строк, и те строки кое-что разделяют: повторяющийся ключ, приблизительное совпадение, вынужденное выбрать соседа, или колонка поиска, чей порядок изменился после написания формулы. Разделы ниже проходят правила по одному, с точным результатом каждой формулы

Какие значения match_mode и search_mode принимает XLOOKUP?

HotXLS, нативный табличный компонент Delphi и C++Builder, вычисляет XLOOKUP и XMATCH через одну общую процедуру поиска, принимающую ровно четыре режима совпадения и четыре режима поиска. match_mode может быть 0 (точное), -1 (точное или следующий меньший), 1 (точное или следующий больший) или 2 (подстановочные знаки). search_mode может быть 1 (скан от первого к последнему), -1 (скан от последнего к первому), 2 (двоичный поиск по возрастающим данным) или -2 (двоичный поиск по убывающим данным). Любое другое число возвращает #VALUE!; ничего не поджимается к ближайшему легальному режиму. Опущенные аргументы выбирают match mode 0 и search mode 1 — то, что использует большинство рукописных формул

Количество аргументов проверяется прежде всего этого. XLOOKUP берёт от трёх до шести аргументов, XMATCH — от двух до четырёх, и вызов вне этих диапазонов — #VALUE! ещё до начала вычисления. Сами аргументы режимов — обычные выражения листа, поэтому HotXLS конвертирует каждый в число, возвращает #VALUE! для NaN, бесконечности или значения вне 32-битного целочисленного диапазона, а затем усекает к нулю. 1.5 становится search mode 1, -1.5 становится -1, 2.9 становится 2. Усечение кусается, когда режим приходит из ячейки, посчитанной арифметикой: значение, отображающееся как 2, но хранимое как 1.9999999, выбирает линейный скан. Пишите режим литералом или оборачивайте вычисленный в ROUND

Программа ниже пишет маленькую таблицу ставок и пять поисков, упражняющих те правила. Комментарии дают значение, которое каждая ячейка с формулой держит после Recalculate, выведенное из правил выше

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

    // Дефолты: match_mode 0, search_mode 1
    Sheet.Cells[1, 4].Formula := 'XLOOKUP(30,A1:A4,B1:B4)';               // 0.15
    // Точное или следующий меньший, двоичный поиск по возрастающим ключам
    Sheet.Cells[2, 4].Formula := 'XLOOKUP(35,A1:A4,B1:B4,"none",-1,2)';   // 0.15
    // 1.5 усекается до search_mode 1
    Sheet.Cells[3, 4].Formula := 'XLOOKUP(40,A1:A4,B1:B4,"none",0,1.5)';  // 0.10
    // 3 — не режим поиска
    Sheet.Cells[4, 4].Formula := 'XLOOKUP(40,A1:A4,B1:B4,"none",0,3)';    // #VALUE!
    // Совпадение по подстановочным знакам не может идти на двоичном поиске
    Sheet.Cells[5, 4].Formula := 'XLOOKUP("4*",A1:A4,B1:B4,"none",2,2)';  // #VALUE!

    if Book.Recalculate = lxOk then
      Book.SaveAs('lookup-modes.xlsx');
  finally
    Book.Free;
  end;
end;

Почему search_mode 2 пропускает ключ, лежащий на листе?

Search mode 2 сообщает HotXLS, что вектор поиска уже отсортирован по возрастанию, и движок верит. Проверить утверждение значило бы пройти всю колонку — ровно та цена, ради избежания которой двоичный поиск существует, — поэтому спуск делит интервал пополам на каждом щупе и возвращается туда, где кончил. Microsoft документирует тот же контракт для XLOOKUP и XMATCH: двоичные режимы требуют отсортированных данных и дают неверные результаты в противном случае. ISO/IEC 29500-1 §18.17, формульная статья SpreadsheetML, описывает старые LOOKUP и VLOOKUP с их собственным требованием возрастания; XLOOKUP и XMATCH появились позже и хранятся в файле как _xlfn.XLOOKUP и _xlfn.XMATCH под префиксом future-function

Рисунок трассирует XLOOKUP(40, A1:A3, B1:B3, "missing", 0, 2) по ключам 40, 10, 30. Первый щуп садится на строку 2, читает 10, и поскольку 10 ниже 40, он отбрасывает строки 1 и 2 — включая строку, держащую 40. Строка 3 читает 30, тоже ниже 40, и интервал пуст. Формула возвращает "missing". С search mode 1 тот же вызов находит 40 в строке 1

«По возрастанию» означает и нечто более специфичное, чем видно на экране. Двоичный путь ранжирует значения по виду прежде, чем сравнивать: сначала числа, затем текст, затем булевы, затем значения ошибок, затем пустые. Колонка числовых кодов деталей, в которой три ячейки держат коды как текст, не является возрастающей по тому правилу, как бы опрятно она ни выглядела. Текст сравнивается без учёта регистра, а на Windows порядок приходит из локали пользователя через CompareStringW, обращающуюся с дефисами и буквами с диакритикой иначе, чем сортировка по байтам. Ключевая колонка, отсортированная базой данных с binary collation, поэтому может провалить обещание порядка ровно на кодах с пунктуацией

Ранжирование пустых последними имеет перекошенное следствие. Возрастающая ключевая колонка с пустыми строками внизу всё ещё возрастающая, так что направить search mode 2 на раздутый диапазон вроде A2:A5001 безвредно. Убывающая колонка, за которой следуют пустые строки, убывающей больше не является, и search mode -2 шагает прямиком в пустоты

var
  R: TXLSFormulaEvaluationResult;
begin
  // B1:B3 держит 9, 7, 5; B4:B10 пусты
  R := Sheet.EvaluateFormulaAt(1, 4, 'XMATCH(5,B1:B10,0,-2)');
  // R.Status = xlfeOk и VarIsError(R.Value): результат — #N/A.
  // Первый щуп читает пустую B5, пустые ранжируются выше любого числа,
  // поэтому спуск продолжает двигаться вправо и не возвращается

  // Обрежьте диапазон до заполненных строк, и тот же вызов работает
  R := Sheet.EvaluateFormulaAt(1, 4, 'XMATCH(5,B1:B3,0,-2)');     // 3

  // Линейный скан пропускает пустые и находит ключ, где бы он ни был
  R := Sheet.EvaluateFormulaAt(1, 4, 'XMATCH(5,B1:B10,0,-1)');    // 3
end;

Куда попадают дублирующиеся ключи?

XMATCH и XLOOKUP приземляются на фиксированный конец серии дубликатов, и режим поиска выбирает конец. Под search mode 2 двоичный спуск запоминает каждый встреченный равный ключ и продолжает сужаться влево, так что результат — наименьший индекс серии. Под search mode -2, по убывающим данным, он запоминает позицию и сужается вправо, выдавая наибольший индекс. Линейные режимы возвращают первое попадание по направлению скана: наименьший индекс для search mode 1, наибольший для search mode -1

Вот почему отчёты о расхождениях кучкуются на конкретных строках. Примерный файл с уникальными ключами даёт одинаковый ответ под всеми четырьмя режимами поиска, так что каждый построенный на нём тест проходит. Стоит производственным данным повторить код клиента — режимы начинают расходиться ровно на повторяющихся строках, а код, писавший формулы, не изменился ни на что

// A1:A7 держит 1, 3, 5, 5, 5, 7, 9 (по возрастанию, серия из трёх)
Sheet.Cells[1, 3].Formula := 'XMATCH(5,A1:A7,0,1)';   // 3, первое попадание вперёд
Sheet.Cells[2, 3].Formula := 'XMATCH(5,A1:A7,0,-1)';  // 5, первое попадание назад
Sheet.Cells[3, 3].Formula := 'XMATCH(5,A1:A7,0,2)';   // 3, наименьший индекс серии

// B1:B7 держит 9, 7, 5, 5, 5, 3, 1 (по убыванию)
Sheet.Cells[4, 3].Formula := 'XMATCH(5,B1:B7,0,-2)';  // 5, наибольший индекс серии

Как приблизительное совпадение выбирает второго призёра

Когда ни одна ячейка не равна искомому значению, match mode -1 возвращает наибольшее значение, не превосходящее цель, а match mode 1 — наименьшее значение, не меньшее её. В линейных режимах HotXLS сканирует весь вектор и держит лучшего кандидата, так что приблизительное совпадение работает на неотсортированных данных. Ячейка сменяет стоящего кандидата, только когда строго ближе, — никогда по простой ничьей. Среди нескольких ячеек с одинаковым значением второго призёра сохраняется первая встреченная по порядку скана

Возьмите ключи 10, 30, 20, 30, 50, 40 в A1:A6. XMATCH(35, A1:A6, -1, 1) возвращает 2: первая 30 становится кандидатом, а вторая 30 лишь сравнивается с ним. Разверните скан через XMATCH(35, A1:A6, -1, -1) — результат 4, потому что скан назад первым встречает другую 30. XMATCH(35, A1:A6, 1, 1) возвращает 6, поскольку 40 бьёт 50 как наименьшее значение выше 35. На отсортированных данных двоичные режимы добираются до того же соседа горсткой щупов: по 10, 20, 30, 40, 50 XMATCH(35, A1:A5, -1, 2) возвращает 3, а XMATCH(35, A1:A5, 1, 2) — 4

Если ни точного попадания, ни приемлемого соседа не нашлось, XLOOKUP возвращает свой аргумент if_not_found, когда он был подан, и #N/A, когда не был. У XMATCH запасного аргумента нет — всегда #N/A

Почему подстановочные знаки и двоичный поиск не могут сосуществовать

У шаблона с подстановочными знаками нет места в порядке сортировки. Match mode 2 спрашивает, подходит ли ячейка под маску, — вопрос да-нет, — тогда как двоичному спуску нужен трёхвариантный ответ, говорящий, какую половину сохранить. Защищённого способа сказать, лежит ли ACME-* левее или правее данной ячейки, нет, поэтому HotXLS возвращает #VALUE! для match mode 2 в комбинации с search mode 2 или -2 и не угадывает. С подстановочными знаками используйте search mode 1 или -1 и принимайте линейную цену

Match mode 2 всегда применяет правила подстановочных знаков: * — любая последовательность символов, ? — один символ, а ~ делает следующий символ литеральным. Поэтому XLOOKUP("PN~*", ...) находит сам текст PN* — важно, когда коды продуктов действительно содержат звёздочки. В match mode 0 линейный скан сравнивает текст без учёта регистра, а двоичный путь считает два значения равными, когда его порядковое сравнение докладывает ничью. То сравнение тоже без учёта регистра, но это тот же учитывающий локаль порядок, описанный выше, — единственное отношение, которым двоичный поиск вправе пользоваться. Сильно нагруженные поиском листы вдобавок формируют то, что трекинг зависимостей за инкрементальным пересчётом обязан переоценить после правки

Ошибки формы и разливающиеся возвращаемые срезы

Обеим функциям нужен одномерный диапазон поиска. Диапазон, простирающийся больше чем на одну строку и больше чем на одну колонку одновременно, возвращает #VALUE!; HotXLS не выбирает ось за вас. XLOOKUP добавляет второе правило: возвращаемый диапазон обязан иметь ту же длину, что диапазон поиска вдоль оси совпадения. Вертикальный поиск по 500 строкам с возвращаемым диапазоном в 499 строк — ошибка, и последняя строка никогда не отбрасывается тихо. Когда диапазон поиска — одна ячейка, форму возвращаемого диапазона решает, считается ли поиск вертикальным или горизонтальным

Возвращаемый диапазон шире одной колонки, при вертикальном поиске, заставляет XLOOKUP вернуть всю совпавшую строку как массив. Он разливается в соседние ячейки по тем же правилам, что остальные функции динамических массивов, — об этом статья о диапазонах разлива и динамических массивах. Пустые ячейки внутри разлившегося среза возвращаются как 0. Вытащить целую запись из таблицы одной формулой удобно — и это же самый быстрый способ перезаписать колонку, оказавшуюся справа от формулы

Выбор режима для книг, за которыми никто не следит

Серверная генерация заслуживает более строгой политики, чем интерактивное использование: до отгрузки никто не глядит на результат. Оставьте там match mode 0 с search mode 1: совпадение точное, скан игнорирует порядок строк, и пересортировка листа не может сменить ответ. Search mode 2 принадлежит только там, где тот же код произвёл упорядочение, в том же прогоне, по той же колонке. Двоичный поиск по колонке, отсортированной по другому ключу, — дешёвый способ вычислить уверенно неверное число

Переводя поиск в двоичный режим, проверьте упорядочение сами, в точке, где вы выпускаете формулу. Функция ниже — не часть HotXLS; это страховка, которую стоит добавить в собственный код. Для многих точных поисков по одной таблице свойство книги RecalcLookupCache позволяет Recalculate переиспользовать первый скан диапазона для последующих поисков по нему. Кэш выключает себя сам, когда проход содержит OFFSET, INDIRECT, циклические ссылки или таблицы данных What-If, а результаты в обоих случаях одинаковы

// Ваша собственная страховка, не API HotXLS: подтвердите, что ключевая
// колонка возрастает, прежде чем выпускать формулу search_mode 2
function KeysAscending(Sheet: TXLSXWorksheet; Col, FirstRow,
  LastRow: Integer): Boolean;
var
  Row: Integer;
  Prev, Cur: Variant;
begin
  Result := False;
  Prev := Sheet.Cells[FirstRow, Col].Value;
  if not VarIsNumeric(Prev) then Exit;
  for Row := FirstRow + 1 to LastRow do
  begin
    Cur := Sheet.Cells[Row, Col].Value;
    if (not VarIsNumeric(Cur)) or (Cur < Prev) then Exit;  // текст, пустая или вне порядка
    Prev := Cur;
  end;
  Result := True;
end;

// Лист Rates: ключи в A2:A5001, ставки в B2:B5001
UseBinary := KeysAscending(Rates, 1, 2, 5001);
Book.RecalcLookupCache := True;
for Row := 2 to OrderCount + 1 do
  if UseBinary then
    Orders.Cells[Row, 5].Formula := Format(
      'XLOOKUP(B%d,Rates!$A$2:$A$5001,Rates!$B$2:$B$5001,0,-1,2)', [Row])
  else
    Orders.Cells[Row, 5].Formula := Format(
      'XLOOKUP(B%d,Rates!$A$2:$A$5001,Rates!$B$2:$B$5001,"missing")', [Row]);

Страховка нарочно консервативна: одна пустая или текстовая ячейка возвращает всю колонку на линейный путь. На отсортированной горячей колонке выигрыш двоичного режима реален — около log₂ n чтений на поиск вместо n, что для 5 000 ключей означает 13 щупов максимум

Когда поиск — на самом деле замаскированное бизнес-правило, вроде многоуровневой ставки с исключениями, колбэк в собственный Pascal-код обычно яснее любой комбинации встроенных функций; как зарегистрировать один, показывает статья о пользовательских функциях листа. XLOOKUP, XMATCH и остальной движок формул, описанный здесь, — часть HotXLS Delphi spreadsheet component, а его страница продукта перечисляет поддерживаемые функции листа для Delphi и C++Builder