Modos de Busca Binária XLOOKUP e XMATCH em Delphi

Sobre as chaves 1, 3, 5, 5, 5, 7, 9 em A1:A7, a fórmula XMATCH(5, A1:A7, 0, 2) devolve 3. Mude apenas o último argumento para -1 e a mesma fórmula devolve 5. Aponte a primeira versão para uma coluna que alguém re-ordenou por outro campo, e um 5 claramente visível na planilha pode voltar como #N/A. As três respostas estão corretas. O último argumento do XMATCH, como o sexto do XLOOKUP, são duas coisas ao mesmo tempo: uma instrução sobre qual duplicada preferir, e uma promessa sobre como os dados estão ordenados

O relatório que leva até aqui raramente menciona search modes. Ele diz que uma pasta de trabalho gerada diverge do que alguém esperava em um punhado de linhas, e essas linhas compartilham algo: uma chave repetida, uma correspondência aproximada que precisou escolher um vizinho, ou uma coluna de busca cuja ordem mudou depois que a fórmula foi escrita. As seções abaixo passam pelas regras uma a uma, com o resultado exato que cada fórmula produz

Quais valores de match_mode e search_mode o XLOOKUP aceita?

O HotXLS, o componente de planilha nativo Delphi e C++Builder, avalia XLOOKUP e XMATCH por uma rotina de lookup compartilhada que aceita exatamente quatro match modes e quatro search modes. match_mode pode ser 0 (exato), -1 (exato ou próximo menor), 1 (exato ou próximo maior) ou 2 (curinga). search_mode pode ser 1 (varredura do primeiro ao último), -1 (varredura do último ao primeiro), 2 (busca binária sobre dados ascendentes) ou -2 (busca binária sobre dados descendentes). Qualquer outro número devolve #VALUE!; nada é encaixado à força no modo legal mais próximo. Omitir os argumentos seleciona match mode 0 e search mode 1, que é o que a maioria das fórmulas escritas à mão usa

As contagens de argumentos são checadas antes de qualquer coisa. XLOOKUP recebe de três a seis argumentos e XMATCH de dois a quatro, e uma chamada fora dessas faixas é um #VALUE! antes de a avaliação começar. Os argumentos de modo são expressões comuns de planilha, então o HotXLS converte cada um para número, devolve #VALUE! para NaN, infinito ou valor fora da faixa de inteiro de 32 bits e então trunca em direção ao zero. 1.5 vira search mode 1, -1.5 vira -1, e 2.9 vira 2. A truncagem morde quando o modo vem de uma célula computada por aritmética: um valor que exibe 2 mas é guardado como 1.9999999 seleciona uma varredura linear. Escreva o modo como literal, ou embrulhe um computado em ROUND

O programa a seguir escreve uma tabela de taxas pequena e cinco lookups que exercitam essas regras. Os comentários dão o valor que cada célula de fórmula guarda depois do Recalculate, derivado das regras acima

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;

    // Padrões: match_mode 0, search_mode 1
    Sheet.Cells[1, 4].Formula := 'XLOOKUP(30,A1:A4,B1:B4)';               // 0.15
    // Exato ou próximo menor, busca binária sobre chaves ascendentes
    Sheet.Cells[2, 4].Formula := 'XLOOKUP(35,A1:A4,B1:B4,"none",-1,2)';   // 0.15
    // 1.5 trunca para search_mode 1
    Sheet.Cells[3, 4].Formula := 'XLOOKUP(40,A1:A4,B1:B4,"none",0,1.5)';  // 0.10
    // 3 não é um search mode
    Sheet.Cells[4, 4].Formula := 'XLOOKUP(40,A1:A4,B1:B4,"none",0,3)';    // #VALUE!
    // Matching com curinga não pode rodar numa busca binária
    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;

Por que o search_mode 2 perde uma chave que está na planilha?

O search mode 2 diz ao HotXLS que o vetor de busca já está ordenado ascendente, e o motor acredita. Checar a afirmação levaria uma passada completa pela coluna, que é exatamente o custo que uma busca binária existe para evitar, então a descida divide o intervalo ao meio em cada sonda e devolve onde quer que termine. A Microsoft documenta o mesmo contrato para XLOOKUP e XMATCH: os modos binários exigem dados ordenados e dão resultados inválidos caso contrário. A ISO/IEC 29500-1 §18.17, a cláusula de fórmulas do SpreadsheetML, descreve o LOOKUP e o VLOOKUP mais antigos com o requisito próprio de ordem ascendente; XLOOKUP e XMATCH vieram depois e são guardados no arquivo como _xlfn.XLOOKUP e _xlfn.XMATCH sob o prefixo de future-function

A figura traça XLOOKUP(40, A1:A3, B1:B3, "missing", 0, 2) sobre as chaves 40, 10, 30. A primeira sonda cai na linha 2, lê 10, e como 10 está abaixo de 40 ela descarta as linhas 1 e 2, incluindo a linha que guarda o 40. A linha 3 lê 30, também abaixo de 40, e o intervalo fica vazio. A fórmula devolve "missing". Com search mode 1 a mesma chamada acha o 40 na linha 1

"Ascendente" também significa algo mais específico do que parece na tela. O caminho binário classifica os valores por tipo antes de compará-los: números primeiro, depois texto, depois booleanos, depois valores de erro, depois blanks. Uma coluna de códigos de peça numérica na qual três células guardam os códigos como texto não é ascendente sob essa regra, por mais arrumada que pareça. Texto é comparado sem diferenciar caixa, e no Windows a ordem vem da locale do usuário via CompareStringW, que trata hífens e letras acentuadas de forma diferente de uma ordenação por byte. Uma coluna de chaves ordenada por um banco com collation binária pode portanto falhar na promessa de ordenação exatamente nos códigos que contêm pontuação

Blanks classificados por último têm uma consequência desequilibrada. Uma coluna de chaves ascendente com linhas vazias abaixo dela ainda é ascendente, então apontar o search mode 2 para um range grande demais como A2:A5001 é inofensivo. Uma coluna descendente seguida de linhas vazias já não é descendente, e o search mode -2 anda direto para dentro dos blanks

var
  R: TXLSFormulaEvaluationResult;
begin
  // B1:B3 guarda 9, 7, 5; B4:B10 estão vazias
  R := Sheet.EvaluateFormulaAt(1, 4, 'XMATCH(5,B1:B10,0,-2)');
  // R.Status = xlfeOk e VarIsError(R.Value): o resultado é #N/A.
  // A primeira sonda lê a B5 vazia, blanks ficam acima de todo número,
  // então a descida segue para a direita e nunca volta

  // Apare o range para as linhas preenchidas e a mesma chamada funciona
  R := Sheet.EvaluateFormulaAt(1, 4, 'XMATCH(5,B1:B3,0,-2)');     // 3

  // Uma varredura linear pula os blanks e acha a chave onde ela estiver
  R := Sheet.EvaluateFormulaAt(1, 4, 'XMATCH(5,B1:B10,0,-1)');    // 3
end;

Onde chaves duplicadas caem?

XMATCH e XLOOKUP caem numa ponta fixa de uma sequência de duplicadas, e o search mode escolhe a ponta. Sob search mode 2 a descida binária registra cada chave igual que encontra e continua estreitando para a esquerda, então o resultado é o menor índice da sequência. Sob search mode -2, sobre dados descendentes, ele registra a posição e estreita para a direita, dando o maior índice. Os modos lineares devolvem o primeiro hit na direção da varredura: o menor índice para o search mode 1, o maior para o search mode -1

É por isso que os relatos de divergência se aglomeram em linhas específicas. Um arquivo de amostra com chaves únicas dá a mesma resposta sob os quatro search modes, então todo teste construído a partir dele passa. Assim que os dados de produção repetem um código de cliente, os modos começam a discordar precisamente nas linhas repetidas, e o código que escreveu as fórmulas não mudou em nada

// A1:A7 guarda 1, 3, 5, 5, 5, 7, 9 (ascendente, uma sequência de três)
Sheet.Cells[1, 3].Formula := 'XMATCH(5,A1:A7,0,1)';   // 3, primeiro hit para frente
Sheet.Cells[2, 3].Formula := 'XMATCH(5,A1:A7,0,-1)';  // 5, primeiro hit para trás
Sheet.Cells[3, 3].Formula := 'XMATCH(5,A1:A7,0,2)';   // 3, menor índice da sequência

// B1:B7 guarda 9, 7, 5, 5, 5, 3, 1 (descendente)
Sheet.Cells[4, 3].Formula := 'XMATCH(5,B1:B7,0,-2)';  // 5, maior índice da sequência

Como a correspondência aproximada escolhe o segundo colocado

Quando nenhuma célula é igual ao valor de busca, o match mode -1 devolve o maior valor que não é maior que o alvo e o match mode 1 devolve o menor valor que não é menor. Nos modos lineares o HotXLS varre o vetor inteiro e mantém um melhor candidato, então a correspondência aproximada funciona sobre dados não ordenados. Uma célula substitui o candidato em pé só quando é estritamente mais próxima, nunca quando apenas empata. Entre várias células guardando o mesmo valor de segundo lugar, a mantida é a primeira encontrada na ordem da varredura

Pegue as chaves 10, 30, 20, 30, 50, 40 em A1:A6. XMATCH(35, A1:A6, -1, 1) devolve 2: o primeiro 30 vira o candidato, e o segundo 30 apenas empata com ele. Inverta a varredura com XMATCH(35, A1:A6, -1, -1) e o resultado é 4, porque varrer para trás encontra o outro 30 primeiro. XMATCH(35, A1:A6, 1, 1) devolve 6, já que 40 ganha de 50 como o menor valor acima de 35. Sobre dados ordenados os modos binários chegam ao mesmo vizinho em um punhado de sondas: sobre 10, 20, 30, 40, 50, XMATCH(35, A1:A5, -1, 2) devolve 3 e XMATCH(35, A1:A5, 1, 2) devolve 4

Se nem um hit exato nem um vizinho aceitável aparecem, o XLOOKUP devolve o argumento if_not_found dele quando um foi fornecido e #N/A quando não. O XMATCH não tem argumento de fallback e sempre devolve #N/A

Por que curingas e busca binária não podem coexistir

Um padrão com curinga não tem posição numa ordem de classificação. O match mode 2 pergunta se uma célula encaixa numa máscara, o que é uma pergunta de sim ou não, enquanto uma descida binária precisa de uma resposta de três vias que diga qual metade manter. Não há jeito defensável de dizer se ACME-* está à esquerda ou à direita de uma célula dada, então o HotXLS devolve #VALUE! para match mode 2 combinado com search mode 2 ou -2 e não chuta. Use search mode 1 ou -1 com curingas e aceite o custo linear

O match mode 2 sempre aplica as regras de curinga: * representa qualquer sequência de caracteres, ? um caractere, e ~ torna o próximo caractere literal. XLOOKUP("PN~*", ...) portanto acha o texto PN* em si, o que importa quando códigos de produto realmente contêm asteriscos. No match mode 0 a varredura linear compara texto sem diferenciar caixa, e o caminho binário trata dois valores como iguais quando a comparação de ordenação dele reporta empate. Essa comparação também ignora caixa, mas é a mesma ordenação consciente de locale descrita acima, que é a única relação que uma busca binária pode legitimamente usar. Planilhas pesadas em lookup também moldam o que o dependency tracking por trás do recálculo incremental precisa reavaliar depois de uma edição

Erros de forma e fatias de retorno com spill

Ambas as funções precisam de um range de busca unidimensional. Um range que atravessa mais de uma linha e mais de uma coluna ao mesmo tempo devolve #VALUE!; o HotXLS não escolhe um eixo no seu lugar. O XLOOKUP acrescenta uma segunda regra: o range de retorno precisa ter o mesmo comprimento que o range de busca ao longo do eixo da correspondência. Uma busca vertical sobre 500 linhas emparelhada com um range de retorno de 499 linhas é um erro, e a última linha nunca é descartada em silêncio. Quando o range de busca é uma célula única, a forma do range de retorno decide se a busca conta como vertical ou horizontal

Um range de retorno mais largo que uma coluna, para uma busca vertical, faz o XLOOKUP devolver a linha inteira casada como um array. Ele sofre spill para as células vizinhas sob as mesmas regras das outras funções de dynamic array, cobertas no artigo sobre spill ranges e dynamic arrays. Células vazias dentro de uma fatia com spill voltam como 0. Puxar um registro completo de uma tabela com uma fórmula é conveniente, e também é o jeito mais rápido de sobrescrever uma coluna que por acaso sentava à direita da fórmula

Escolhendo um modo para pastas de trabalho que ninguém vigia

Geração no lado do servidor merece uma política mais estrita que o uso interativo, porque nenhuma pessoa olha o resultado antes de ele embarcar. Deixe match mode 0 com search mode 1 no lugar ali: a correspondência é exata, a varredura ignora a ordem das linhas, e re-ordenar a planilha não pode mudar a resposta. O search mode 2 pertence apenas onde o mesmo código produziu a ordenação, na mesma execução, sobre a mesma coluna. Uma busca binária sobre uma coluna ordenada por uma chave diferente é o jeito mais barato de computar um número errado com confiança

Quando você de fato mudar um lookup para modo binário, cheque a ordenação você mesmo no ponto em que emite a fórmula. A função abaixo não faz parte do HotXLS; é uma guarda para acrescentar ao seu próprio código. Para muitos lookups exatos contra uma mesma tabela, a propriedade RecalcLookupCache da pasta de trabalho deixa o Recalculate reutilizar a primeira varredura de um range para lookups posteriores contra ele. O cache se desliga sozinho quando o passe contém OFFSET, INDIRECT, referências circulares ou tabelas de dados What-If, e os resultados são os mesmos de qualquer forma

// Sua própria guarda, não é API do HotXLS: confirme que uma coluna de
// chaves numérica é ascendente antes de emitir uma fórmula search_mode 2 que dependa dela
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;  // texto, vazio ou fora de ordem
    Prev := Cur;
  end;
  Result := True;
end;

// Planilha Rates: chaves em A2:A5001, taxas em 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]);

A guarda é deliberadamente conservadora: uma única célula vazia ou de texto manda a coluna inteira de volta para o caminho linear. Numa coluna ordenada e quente o ganho do modo binário é real, cerca de log₂ n leituras por lookup em vez de até n, o que para 5.000 chaves significa 13 sondas no máximo

Quando um lookup é na verdade uma regra de negócio disfarçada, como uma taxa escalonada com exceções, um callback para o seu próprio código Pascal costuma ser mais claro que qualquer arranjo de funções embutidas; o artigo sobre funções de planilha personalizadas mostra como registrar uma. XLOOKUP, XMATCH e o resto do motor de fórmulas descrito aqui fazem parte do componente de planilha HotXLS para Delphi, e a página de produto dele lista as funções de planilha suportadas para Delphi e C++Builder