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 поэтому доверяет вызывающему коду, делит интервал пополам и возвращает то, на что попадает спуск. На несортированном вводе ответ не является ошибкой, он молча неверен, и это нарушение контракта, а не дефект движка
Microsoft документирует ту же асимметрию для XLOOKUP и XMATCH: двоичные режимы требуют сортированных данных и иначе дают недействительные результаты. ISO 29500-1, раздел 18.17, определяющий грамматику формул SpreadsheetML, несёт более старые описания 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 отклоняет match_mode 2 в сочетании с search_mode 2 или -2 сразу же с #VALUE! вместо угадывания упорядочивания и выдачи правдоподобной бессмыслицы. Два пути также сравнивают значения по-разному, что усиливает разделение: линейное сканирование решает равенство сравнением текста без учёта регистра или сопоставлением с маской, когда включены подстановочные знаки, в то время как двоичный спуск решает равенство, спрашивая у компаратора упорядочивания ноль. Это намеренно, а не случайность наслоения, поскольку двоичный путь может использовать только то отношение, по которому он на самом деле навигирует. Если вам нужны подстановочные знаки, используйте режим поиска 1 или -1 и примите линейную стоимость — тот же компромисс, который призвано удерживать вне вашего критического пути отслеживание зависимостей за инкрементным пересчётом
Ошибки формы: двумерные диапазоны и несовпадающие возвращаемые векторы
Обеим функциям нужен подлинно одномерный диапазон поиска. Если переданный диапазон охватывает одновременно более одной строки и более одного столбца, HotXLS возвращает #VALUE! вместо выбора оси за вас, а диапазон из одной строки или одного столбца читается вдоль своей длинной оси. XLOOKUP добавляет второе правило формы: возвращаемый диапазон должен быть ровно такой же длины, как диапазон поиска вдоль совпадающей оси, так что вертикальный поиск по 500 строкам в паре с возвращаемым диапазоном на 499 строк — ошибка, а не тихо разрешённое смещение на единицу на последней строке. Когда возвращаемый диапазон шире одного столбца для вертикального поиска или выше одной строки для горизонтального, XLOOKUP возвращает весь совпавший срез как массив, и он растекается в соседние ячейки по тем же правилам, что и другие функции динамических массивов, описанные в статье о диапазонах растекания и динамических массивах. Это по-настоящему полезно для извлечения целой записи из таблицы одной формулой, и это же самый быстрый способ перезаписать столбец, который вы хотели сохранить
Выбор режима, когда никто не смотрит на экран
Серверная генерация заслуживает более строгой политики, чем интерактивное использование, потому что нет человека, который заметит, что итог выглядит неверно. Обоснованное значение по умолчанию — режим поиска 1 с режимом совпадения 0: линейный, точный, независимый от порядка и невозможный к нарушению повторной сортировкой листа. Тянитесь к режиму поиска 2 только там, где тот же путь кода произвёл и упорядочивание, в том же прогоне, по тому же столбцу, и запишите эту зависимость рядом с формулой, потому что двоичный поиск по столбцу, отсортированному по другому ключу, — самый дешёвый возможный способ вычислить уверенно неверное число. Когда поиск действительно горячий, а данные действительно отсортированы, выгода реальна: спуск читает порядка log n ячеек вместо n, и каждое из этих чтений проходит через полное разрешение ячейки книги, так что экономия больше, чем подсказывает число инструкций
Если форма задачи ближе к правилу предметной области, чем к поиску, обратный вызов в ваш собственный код на Pascal, разобранный в статье о пользовательских функциях листа, обычно превзойдёт любую хитрую комбинацию встроенных функций. Обсуждаемые здесь реализации XLOOKUP и XMATCH поставляются со стандартным компонентом электронных таблиц HotXLS для Delphi, чья страница продукта содержит полный справочник поддерживаемых функций для Delphi и C++Builder