Tryby wyszukiwania binarnego XLOOKUP i XMATCH w Delphi

Na kluczach 1, 3, 5, 5, 5, 7, 9 w A1:A7 formuła XMATCH(5, A1:A7, 0, 2) zwraca 3. Zmień wyłącznie ostatni argument na -1 i ta sama formuła zwraca 5. Skieruj pierwszą wersję na kolumnę, którą ktoś przestawił według innego pola, i piątka widoczna gołym okiem na arkuszu może wrócić jako #N/A. Wszystkie trzy odpowiedzi są poprawne. Ostatni argument XMATCH, jak szósty argument XLOOKUP, to dwie rzeczy naraz: instrukcja, który duplikat preferować, i obietnica co do kolejności danych

Zgłoszenie, które prowadzi tutaj, rzadko wymienia tryby wyszukiwania. Mówi, że wygenerowany skoroszyt nie zgadza się z czymś, czego ktoś oczekiwał, na garstce wierszy, a te wiersze mają coś wspólnego: powtórzony klucz, dopasowanie przybliżone, które musiało wybrać sąsiada, albo kolumnę wyszukiwania, której kolejność zmieniła się po zapisaniu formuły. Sekcje poniżej przechodzą reguły jedną po drugiej, z dokładnym wynikiem, jaki każda formuła produkuje

Które wartości match_mode i search_mode przyjmuje XLOOKUP?

HotXLS — natywny komponent arkuszowy dla Delphi i C++Buildera — wylicza XLOOKUP i XMATCH przez jedną współdzieloną procedurę wyszukiwania, która przyjmuje dokładnie cztery tryby dopasowania i cztery tryby wyszukiwania. match_mode może być 0 (dokładne), -1 (dokładne albo następne mniejsze), 1 (dokładne albo następne większe) albo 2 (wieloznaczne). search_mode może być 1 (skan od pierwszego do ostatniego), -1 (skan od ostatniego do pierwszego), 2 (wyszukiwanie binarne po danych rosnących) albo -2 (wyszukiwanie binarne po danych malejących). Jakakolwiek inna liczba zwraca #VALUE!; nic nie jest zacieśniane do najbliższego legalnego trybu. Pominięcie argumentów wybiera tryb dopasowania 0 i tryb wyszukiwania 1, czyli to, czego używa większość formuł pisanych ręcznie

Liczby argumentów są sprawdzane, zanim cokolwiek z tego zacznie. XLOOKUP bierze od trzech do sześciu argumentów, a XMATCH od dwóch do czterech, i wywołanie poza tymi zakresami to #VALUE!, zanim wyliczanie się zacznie. Argumenty trybów same są zwykłymi wyrażeniami arkuszowymi, więc HotXLS konwertuje każdy na liczbę, zwraca #VALUE! dla NaN, nieskończoności albo wartości poza zakresem 32-bitowych liczb całkowitych, a potem obcina w stronę zera. 1.5 staje się trybem wyszukiwania 1, -1.5 staje się -1, a 2.9 staje się 2. Obcinanie gryzie, gdy tryb pochodzi z komórki liczonej arytmetycznie: wartość, która wyświetla się jako 2, a jest przechowywana jako 1.9999999, wybiera skan liniowy. Zapisuj tryb jako literał albo owiń liczony w ROUND

Poniższy program zapisuje małą tabelę stawek i pięć wyszukiwań, które ćwiczą te reguły. Komentarze podają wartość, jaką każda komórka formuły trzyma po Recalculate, wyprowadzoną z reguł wyżej

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;

    // Domyślne: match_mode 0, search_mode 1
    Sheet.Cells[1, 4].Formula := 'XLOOKUP(30,A1:A4,B1:B4)';               // 0.15
    // Dokładne albo następne mniejsze, wyszukiwanie binarne po rosnących kluczach
    Sheet.Cells[2, 4].Formula := 'XLOOKUP(35,A1:A4,B1:B4,"none",-1,2)';   // 0.15
    // 1.5 obcina się do search_mode 1
    Sheet.Cells[3, 4].Formula := 'XLOOKUP(40,A1:A4,B1:B4,"none",0,1.5)';  // 0.10
    // 3 nie jest trybem wyszukiwania
    Sheet.Cells[4, 4].Formula := 'XLOOKUP(40,A1:A4,B1:B4,"none",0,3)';    // #VALUE!
    // Dopasowanie wieloznaczne nie może biegać po wyszukiwaniu binarnym
    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;

Dlaczego search_mode 2 mija klucz, który jest na arkuszu?

Tryb wyszukiwania 2 mówi HotXLS, że wektor wyszukiwania jest już posortowany rosnąco, a silnik wierzy. Sprawdzenie tego twierdzenia kosztowałoby pełny przebieg po kolumnie, czyli dokładnie ten koszt, dla którego wyszukiwanie binarne istnieje, więc zejście połowi interwał przy każdym odpytaniu i zwraca tam, gdzie skończy. Microsoft dokumentuje tę samą umowę dla XLOOKUP i XMATCH: tryby binarne wymagają posortowanych danych i dają nieważne wyniki w przeciwnym razie. ISO/IEC 29500-1 §18.17, punkt formuł SpreadsheetML, opisuje starsze LOOKUP i VLOOKUP z ich własnym wymogiem kolejności rosnącej; XLOOKUP i XMATCH przyszły później i są zapisywane w pliku jako _xlfn.XLOOKUP i _xlfn.XMATCH pod prefiksem funkcji przyszłych

Rysunek śledzi XLOOKUP(40, A1:A3, B1:B3, "missing", 0, 2) po kluczach 40, 10, 30. Pierwsze odpytanie ląduje na wierszu 2, czyta 10 i skoro 10 jest poniżej 40, wyrzuca wiersze 1 i 2 — łącznie z wierszem trzymającym 40. Wiersz 3 czyta 30, też poniżej 40, i interwał jest pusty. Formuła zwraca "missing". Przy trybie wyszukiwania 1 to samo wywołanie znajduje 40 w wierszu 1

„Rosnące” znaczy też coś bardziej specificznego, niż wygląda na ekranie. Ścieżka binarna porządkuje wartości po rodzaju, zanim je porówna: najpierw liczby, potem tekst, potem wartości logiczne, potem wartości błędów, potem pustki. Kolumna numerycznych kodów części, w której trzy komórki trzymają kody jako tekst, nie jest rosnąca pod tą regułą, choćby wyglądała jak najporządniej. Tekst jest porównywany bez rozróżniania wielkości liter, a na Windows kolejność pochodzi z ustawień regionalnych użytkownika przez CompareStringW, które traktuje łączniki i litery diakrytyczne inaczej niż sortowanie po bajtach. Kolumna kluczy posortowana przez bazę danych z kolacją binarną może więc oblać obietnicę kolejności dokładnie na kodach z interpunkcją

Rankowanie pustek na końcu ma jednostronną konsekwencję. Rosnąca kolumna kluczy z pustymi wierszami pod spodem jest nadal rosnąca, więc skierowanie trybu wyszukiwania 2 na przesadny zakres taki jak A2:A5001 jest nieszkodliwe. Malejąca kolumna zakończona pustymi wierszami już nie jest malejąca, a tryb wyszukiwania -2 wchodzi prosto w pustki

var
  R: TXLSFormulaEvaluationResult;
begin
  // B1:B3 trzyma 9, 7, 5; B4:B10 są puste
  R := Sheet.EvaluateFormulaAt(1, 4, 'XMATCH(5,B1:B10,0,-2)');
  // R.Status = xlfeOk i VarIsError(R.Value): wynik to #N/A.
  // Pierwsze odpytanie czyta pustą B5, pustki rankują ponad każdą liczbę,
  // więc zejście przesuwa się w prawo i nie wraca

  // Przytnij zakres do wypełnionych wierszy i to samo wywołanie działa
  R := Sheet.EvaluateFormulaAt(1, 4, 'XMATCH(5,B1:B3,0,-2)');     // 3

  // Skan liniowy przeskakuje pustki i znajduje klucz, gdziekolwiek leży
  R := Sheet.EvaluateFormulaAt(1, 4, 'XMATCH(5,B1:B10,0,-1)');    // 3
end;

Gdzie lądują zduplikowane klucze?

XMATCH i XLOOKUP lądują na ustalonym końcu przebiegu duplikatów, a tryb wyszukiwania wybiera ten koniec. Pod trybem wyszukiwania 2 zejście binarne zapisuje każdy równy klucz, jaki spotka, i zwęża dalej w lewo, więc wynikiem jest najniższy indeks przebiegu. Pod trybem wyszukiwania -2, po danych malejących, zapisuje pozycję i zwęża w prawo, dając najwyższy indeks. Tryby liniowe zwracają pierwsze trafienie w kierunku skanu: najniższy indeks dla trybu wyszukiwania 1, najwyższy dla trybu wyszukiwania -1

Dlatego raporty rozjazdów skupiają się na konkretnych wierszach. Przykładowy plik z unikatowymi kluczami daje tę samą odpowiedź pod wszystkimi czterema trybami wyszukiwania, więc każdy z niego zbudowany test przechodzi. Skoro dane produkcyjne powtórzą kod klienta, tryby zaczynają się nie zgadzać dokładnie na powtórzonych wierszach, a kod, który zapisał formuły, nie zmienił się wcale

// A1:A7 trzyma 1, 3, 5, 5, 5, 7, 9 (rosnąco, przebieg trzech)
Sheet.Cells[1, 3].Formula := 'XMATCH(5,A1:A7,0,1)';   // 3, pierwsze trafienie w przód
Sheet.Cells[2, 3].Formula := 'XMATCH(5,A1:A7,0,-1)';  // 5, pierwsze trafienie w tył
Sheet.Cells[3, 3].Formula := 'XMATCH(5,A1:A7,0,2)';   // 3, najniższy indeks przebiegu

// B1:B7 trzyma 9, 7, 5, 5, 5, 3, 1 (malejąco)
Sheet.Cells[4, 3].Formula := 'XMATCH(5,B1:B7,0,-2)';  // 5, najwyższy indeks przebiegu

Jak dopasowanie przybliżone wybiera drugiego w kolejce

Gdy żadna komórka nie równa się wartości wyszukiwania, tryb dopasowania -1 zwraca największą wartość, która nie jest większa od celu, a tryb dopasowania 1 najmniejszą wartość, która nie jest mniejsza. W trybach liniowych HotXLS skanuje cały wektor i trzyma najlepszego kandydata, więc dopasowanie przybliżone działa też na danych nieposortowanych. Komórka zastępuje stojącego kandydata tylko, gdy jest ściśle bliżej, nigdy, gdy jedynie remisuje. Spośród kilku komórek trzymających tę samą wartość drugiego w kolejce zachowywana jest ta pierwsza napotkana w kolejności skanu

Weź klucze 10, 30, 20, 30, 50, 40 w A1:A6. XMATCH(35, A1:A6, -1, 1) zwraca 2: pierwsze 30 staje się kandydatem, a drugie 30 tylko z nim remisuje. Odwróć skan przez XMATCH(35, A1:A6, -1, -1) i wynik to 4, bo skan w tył najpierw spotyka tamto 30. XMATCH(35, A1:A6, 1, 1) zwraca 6, skoro 40 bije 50 jako najmniejsza wartość powyżej 35. Na posortowanych danych tryby binarne docierają do tego samego sąsiada w garstce odpytań: po 10, 20, 30, 40, 50, XMATCH(35, A1:A5, -1, 2) zwraca 3, a XMATCH(35, A1:A5, 1, 2) zwraca 4

Jeśli ani dokładne trafienie, ani akceptowalny sąsiad się nie trafią, XLOOKUP zwraca swój argument if_not_found, gdy został podany, i #N/A, gdy nie został. XMATCH nie ma argumentu zastępczego i zawsze zwraca #N/A

Dlaczego wieloznaczniki i wyszukiwanie binarne nie mogą współistnieć

Wzorzec wieloznaczny nie ma pozycji w porządku sortowania. Tryb dopasowania 2 pyta, czy komórka pasuje do maski — pytanie tak albo nie — podczas gdy zejście binarne potrzebuje odpowiedzi trójdrożnej, mówiącej którą połowę zachować. Nie ma obronialnego sposobu, by powiedzieć, czy ACME-* leży na lewo czy na prawo od danej komórki, więc HotXLS zwraca #VALUE! dla trybu dopasowania 2 połączonego z trybem wyszukiwania 2 albo -2 i nie zgaduje. Przy wieloznacznych używaj trybu wyszukiwania 1 albo -1 i zaakceptuj koszt liniowy

Tryb dopasowania 2 zawsze nanosi reguły wieloznaczne: * znaczy dowolny ciąg znaków, ? jeden znak, a ~ czyni następny znak literalnym. XLOOKUP("PN~*", ...) znajduje więc tekst PN* sam w sobie, co ma znaczenie, gdy kody produktów naprawdę zawierają gwiazdki. W trybie dopasowania 0 skan liniowy porównuje tekst bez rozróżniania wielkości liter, a ścieżka binarna traktuje dwie wartości jako równe, gdy jej porównanie porządkujące zgłasza remis. To porównanie też nie rozróżnia wielkości liter, ale jest tą samą kolejnością wrażliwą na ustawienia regionalne, opisaną wyżej — jedyną relacją, jakiej wyszukiwanie binarne może legalnie używać. Arkusze ciężkie w wyszukiwania kształtują też to, co śledzenie zależności za przeliczaniem przyrostowym musi przeliczyć ponownie po edycji

Błędy kształtu i rozlewające się wycinki zwracane

Obie funkcje potrzebują jednowymiarowego zakresu wyszukiwania. Zakres obejmujący zarazem więcej niż jeden wiersz i więcej niż jedną kolumnę zwraca #VALUE!; HotXLS nie wybiera osi za ciebie. XLOOKUP dokłada drugą regułę: zakres zwracany musi mieć tę samą długość co zakres wyszukiwania wzdłuż osi dopasowania. Pionowe wyszukiwanie po 500 wierszach sparowane z zwracanym zakresem 499 wierszy jest błędem, a ostatni wiersz nigdy nie jest po cichu ucinany. Gdy zakres wyszukiwania to pojedyncza komórka, kształt zakresu zwracanego rozstrzyga, czy wyszukiwanie liczy się jako pionowe czy poziome

Zakres zwracany szerszy niż jedna kolumna, przy pionowym wyszukiwaniu, każe XLOOKUP oddać cały dopasowany wiersz jako tablicę. Rozlewa się do sąsiednich komórek pod tymi samymi regułami co pozostałe funkcje tablic dynamicznych — pokrywa je artykuł o zakresach rozlewania i tablicach dynamicznych. Puste komórki wewnątrz rozlanego wycinka wracają jako 0. Wyciągnięcie pełnego rekordu z tabeli jedną formułą jest wygodne i jest też najszybszym sposobem na nadpisanie kolumny, która akurat siedziała na prawo od formuły

Wybór trybu dla skoroszytów, których nikt nie ogląda

Generowanie po stronie serwera zasługuje na ostrzejszą politykę niż użycie interaktywne, bo żaden człowiek nie patrzy na wynik, zanim wypłynie. Zostaw tam match mode 0 z search mode 1: dopasowanie jest dokładne, skan ignoruje kolejność wierszy, a przestawienie arkusza nie potrafi zmienić odpowiedzi. Tryb wyszukiwania 2 należy wyłącznie tam, gdzie ten sam kod wyprodukował kolejność, w tym samym przebiegu, po tej samej kolumnie. Wyszukiwanie binarne po kolumnie posortowanej według innego klucza to najtańszy sposób wyliczenia pewnej siebie złej liczby

Gdy już przełączysz wyszukiwanie na tryb binarny, sprawdź kolejność sam w miejscu, gdzie emitujesz formułę. Funkcja poniżej nie jest częścią HotXLS; to strażnik do doklejenia do twojego własnego kodu. Dla wielu wyszukiwań dokładnych względem jednej tabeli właściwość skoroszytu RecalcLookupCache pozwala Recalculate ponownie użyć pierwszego skanu zakresu dla dalszych wyszukiwań względem niego. Cache wyłącza się sam, gdy przebieg zawiera OFFSET, INDIRECT, odwołania cykliczne albo tabele danych What-If, a wyniki są takie same i tak i tak

// Twój własny strażnik, nie API HotXLS: potwierdź, że numeryczna kolumna
// kluczy jest rosnąca, zanim emitujesz formułę search_mode 2, która na niej polega
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;  // tekst, pustka albo rozjechana kolejność
    Prev := Cur;
  end;
  Result := True;
end;

// Arkusz Rates: klucze w A2:A5001, stawki w 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]);

Strażnik jest celowo konserwatywny: pojedyncza pusta albo tekstowa komórka odsyła całą kolumnę na ścieżkę liniową. Na posortowanej, gorącej kolumnie payoff trybu binarnego jest realny — około log₂ n odczytów na wyszukiwanie zamiast do n, co dla 5 000 kluczy znaczy najwyżej 13 odpytań

Gdy wyszukiwanie jest naprawdę regułą biznesową w przebraniu, jak stawka progowa z wyjątkami, callback do twojego własnego kodu Pascala jest zwykle jaśniejszy niż jakiekolwiek układy funkcji wbudowanych; artykuł o własnych funkcjach arkuszowych pokazuje, jak jedną zarejestrować. XLOOKUP, XMATCH i reszta silnika formuł opisanego tutaj są częścią komponentu arkuszowego HotXLS dla Delphi, a jego strona produktu wypisuje wspierane funkcje arkuszowe dla Delphi i C++Buildera