Režimy binárního vyhledávání XLOOKUP a XMATCH v Delphi

HotXLS, nativní komponenta pro tabulkové procesory pro Delphi a C++Builder, vyhodnocuje XLOOKUP a XMATCH přes jedno sdílené vyhledávací jádro. Toto jádro přijímá čtyři režimy shody (-1, 0, 1, 2) a čtyři režimy vyhledávání (-2, -1, 1, 2), spouští logaritmický binární sestup vždy, když je absolutní hodnota režimu vyhledávání 2, a odmítá jakoukoli jinou kombinaci chybou vzorce

Hlášení chyby, které vás sem přivede, nikdy neřekne „režim vyhledávání". Řekne, že sešit vygenerovaný na serveru ukazuje jiné číslo než tentýž soubor otevřený v Excelu, možná na čtyřech řádcích z devíti tisíc. Tyto čtyři řádky mají vždy něco společného: duplicitní vyhledávací klíč, přibližnou shodu, která musela vybrat souseda, nebo vyhledávací sloupec, který někdo minulý týden seřadil podle jiného sloupce. Vyhledávací funkce jsou místem, kde formulový engine přestává být aritmetikou a začíná být smlouvou, a tato smlouva má klauzule, které většina volajících nikdy nečte

Jaká čísla režimů XLOOKUP skutečně přijímá?

Přesně čtyři z každého, a nic jiného. HotXLS validuje match_mode proti -1, 0, 1 a 2 a search_mode proti -2, -1, 1 a 2 ještě předtím, než se dotkne jediné buňky, a jakákoli jiná hodnota vrátí #VALUE! místo toho, aby byla přiskřípnuta na nejbližší platný režim. Čtyři režimy shody jsou 0 pro přesnou shodu, -1 pro přesnou shodu nebo nejbližší menší, 1 pro přesnou shodu nebo nejbližší větší a 2 pro zástupné znaky; čtyři režimy vyhledávání jsou 1 pro lineární prohledávání vpřed, -1 pro lineární prohledávání vzad, 2 pro binární vyhledávání nad vzestupnými daty a -2 pro binární vyhledávání nad sestupnými daty. Vynechání voleb vybere režim shody 0 a režim vyhledávání 1, kombinaci, kterou používá téměř každý skutečný vzorec. Počty argumentů se hlídají stejným způsobem: XLOOKUP bere tři až šest argumentů a XMATCH dva až čtyři, a cokoli mimo tyto rozsahy je #VALUE! ještě před začátkem vyhodnocení

// 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;

O krok dřív je tišší kontrola, o které stojí za to vědět. Argumenty režimu přicházejí jako výrazy listu, takže HotXLS je převede na číslo, odmítne NaN a nekonečno, a poté vyžaduje, aby se číslo rovnalo své vlastní zaokrouhlené hodnotě. XLOOKUP(x, A:A, B:B, "none", 0, 1.5) je #VALUE!, ne skrytý režim vyhledávání 2. To má význam, když režim pochází z buňky, kterou vyprodukoval výpočet náchylný k zaokrouhlování, což je v generovaných sešitech běžnější než v ručně psaných

Proč search_mode 2 dá špatnou odpověď na neseřazených datech?

Protože dělá přesně to, o co jste požádali. Režim vyhledávání 2 říká enginu, že vyhledávací vektor je už seřazen vzestupně, a binární vyhledávání toto tvrzení nemůže ověřit bez průchodu O(n), který by zničil důvod, proč jej používat. HotXLS proto volajícímu důvěřuje, půlí interval a vrátí, cokoli sestup nakonec najde. Na neseřazeném vstupu odpověď není chyba, je tiše chybná, a to je porušení smlouvy, ne vada enginu

Microsoft dokumentuje stejnou asymetrii pro XLOOKUP a XMATCH: binární režimy vyžadují seřazená data a jinak produkují neplatné výsledky. ISO 29500-1 klauzule 18.17, která definuje gramatiku vzorců SpreadsheetML, nese starší popisy LOOKUP a VLOOKUP s vlastním požadavkem na vzestupné pořadí, a XLOOKUP a XMATCH vznikly dost pozdě po tomto textu na to, aby se v souboru přenášely jako _xlfn.XLOOKUP a _xlfn.XMATCH podle konvence budoucích funkcí. Jiná generace, stejná dohoda: volající dodává invariant pořadí, engine dodává logaritmus

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;

Vysledujte druhý vzorec a selhání je zcela mechanické. Sestup sonduje prostřední buňku, přečte 10, rozhodne, že 10 je menší než 40, zahodí levou polovinu včetně řádku, který skutečně nesl 40, sonduje 30, znovu zahodí a dojde mu interval. Excel se chová stejně, a to je celý smysl: reprodukce chybné odpovědi je požadavkem kompatibility, ne zdvořilostí. Předpoklad pořadí je také přísnější než „čísla vzestupně", protože komparátor řadí hodnoty nejprve podle druhu, v pořadí čísla, pak text, pak booleovské hodnoty, pak chybové hodnoty, pak prázdné, a teprve poté porovnává v rámci druhu. Sloupec číselných kódů dílů, který má tři buňky ukládající text místo toho, není podle tohoto komparátoru vzestupný bez ohledu na to, jak vypadá na obrazovce, a binární režimy jej ochotně přečtou špatně

Kam dopadnou duplicitní klíče?

Na deterministický konec série duplicit, a který konec záleží na režimu vyhledávání, ne na štěstí. Když binární sestup narazí na shodný klíč v režimu vyhledávání 2, zaznamená pozici a poté pokračuje ve zužování doleva, takže výsledkem je nejnižší index série; v režimu vyhledávání -2, nad sestupnými daty, zaznamená pozici a zužuje doprava, takže výsledkem je nejvyšší index. Lineární režimy jsou jednodušší: režim vyhledávání 1 vrací první zásah při procházení vpřed, režim vyhledávání -1 první zásah při procházení vzad. Toto je detail, který vytváří rozpor na čtyřech řádcích z úvodního odstavce, protože sešit, jehož klíče jsou jedinečné, dává identické odpovědi ve všech čtyřech režimech vyhledávání a skryje rozdíl v každém testu, který jste napsali z čistého vzorového souboru. Přidejte do produkčních dat jeden duplicitní kód zákazníka a režimy se začnou rozcházet přesně na řádcích, které se zdvojily: v enginu se nic nezměnilo, vstup jen přestal být množinou a stal se multimnožinou

// 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

Jak přibližná shoda vybere náhradníka?

Tím, že si vedle hledání přesné shody drží nejlepšího kandidáta a vrátí ho pouze tehdy, pokud se neobjeví žádný přesný zásah. HotXLS chápe match_mode -1 jako „největší hodnotu, která není větší než cíl" a match_mode 1 jako „nejmenší hodnotu, která není menší", a oba se řeší nad celou prohledávanou oblastí místo zastavení u prvního přijatelného souseda. V binární cestě stejná myšlenka vypadne ze sestupu zadarmo: každý krok, který přestřelí nebo nedosáhne, aktualizuje kandidáta, takže konečný kandidát je hraniční prvek vedle pozice, kam by byl klíč vložen

// 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;

Prostudujte vnitřní podmínku pozorně, protože právě tam žije rozhodnutí o remíze. Nová buňka nahradí stávajícího kandidáta pouze tehdy, je-li striktně lepší, nikdy pokud se mu jen rovná, takže mezi několika buňkami nesoucími stejnou hodnotu náhradníka zůstane ta první potkaná v pořadí procházení: nejnižší index při prohledávání vpřed, nejvyšší při prohledávání vzad. Nenajdou-li XLOOKUP a XMATCH ani přesný zásah, ani přijatelného souseda, XLOOKUP se vrátí ke svému argumentu if_not_found, byl-li dodán, a k #N/A, když nebyl, zatímco XMATCH vrací vždy #N/A

Proč zástupné znaky a binární vyhledávání nemohou koexistovat

Protože vzor se zástupnými znaky není pozicí v pořadí. Režim shody 2 se ptá, zda buňka odpovídá masce, a shoda s maskou odpovídá ano nebo ne; binární sestup potřebuje trojstavovou odpověď, která mu řekne, kterou polovinu si ponechat. Neexistuje obhajitelný způsob, jak se zeptat, zda ACME-* leží nalevo, nebo napravo od dané buňky, takže HotXLS rovnou odmítá match_mode 2 v kombinaci s search_mode 2 nebo -2 chybou #VALUE! místo hádání pořadí a vytváření věrohodně vypadajícího nesmyslu. Obě cesty také porovnávají hodnoty odlišně, což toto rozdělení posiluje: lineární prohledávání rozhoduje o rovnosti porovnáním textu bez ohledu na velikost písmen, nebo shodou s maskou, jsou-li zapnuté zástupné znaky, zatímco binární sestup rozhoduje o rovnosti tím, že se zeptá komparátoru pořadí na nulu. To je záměr, ne náhoda vrstvení, protože binární cesta smí použít pouze vztah, podle kterého skutečně navigujete. Potřebujete-li zástupné znaky, použijte režim vyhledávání 1 nebo -1 a přijměte lineární náklady, což je stejný kompromis, který má sledování závislostí za přírůstkovým přepočtem za úkol udržet mimo vaši kritickou cestu

Chyby tvaru: dvourozměrné rozsahy a neshodné návratové vektory

Obě funkce vyžadují skutečně jednorozměrný vyhledávací rozsah. Pokrývá-li dodaný rozsah více než jeden řádek a více než jeden sloupec zároveň, HotXLS vrátí #VALUE! místo toho, aby za vás vybral osu, a rozsah jednoho řádku nebo jednoho sloupce se čte podél své delší osy. XLOOKUP přidává druhé pravidlo tvaru: návratový rozsah musí být podél odpovídající osy přesně tak dlouhý jako vyhledávací rozsah, takže vertikální vyhledávání přes 500 řádků spárované s návratovým rozsahem o 499 řádcích je chyba, ne posun o jedna tiše vyřešený na posledním řádku. Je-li návratový rozsah širší než jeden sloupec u vertikálního vyhledávání, nebo vyšší než jeden řádek u horizontálního, XLOOKUP vrátí celý nalezený výřez jako pole a to se přeleje do sousedních buněk podle stejných pravidel jako ostatní funkce dynamických polí, popsaných v článku o přelévajících se rozsazích a dynamických polích. To je opravdu užitečné pro vytažení celého záznamu z tabulky jedním vzorcem, a je to zároveň nejrychlejší způsob, jak přepsat sloupec, který jste chtěli zachovat

Volba režimu, když se na obrazovku nikdo nedívá

Generování na straně serveru si zaslouží přísnější zásadu než interaktivní použití, protože není žádný člověk, kdo by si všiml, že součet vypadá špatně. Obhajitelná výchozí volba je režim vyhledávání 1 s režimem shody 0: lineární, přesný, nezávislý na pořadí a nemožný znehodnotit přeřazením listu. Po režim vyhledávání 2 sahejte pouze tam, kde stejná cesta kódu vyprodukovala i pořadí, ve stejném běhu, nad stejným sloupcem, a tuto závislost si zapište vedle vzorce, protože binární vyhledávání nad sloupcem seřazeným podle jiného klíče je nejlevnějším možným způsobem, jak spočítat sebejisté chybné číslo. Je-li vyhledávání skutečně vytížené a data skutečně seřazená, přínos je skutečný: sestup čte řádově log n buněk místo n, a každé z těchto čtení prochází plným vyhodnocením buňky sešitu, takže úspora je větší, než by naznačoval počet instrukcí

Je-li tvar problému blíže doménovému pravidlu než vyhledávání, callback do vlastního kódu v Pascalu, popsaný v článku o vlastních funkcích listu, obvykle porazí jakékoli chytré uspořádání vestavěných funkcí. Zde popsané implementace XLOOKUP a XMATCH jsou součástí standardní komponenty HotXLS pro Delphi, jejíž stránka produktu nese kompletní referenci podporovaných funkcí pro Delphi a C++Builder