XLOOKUP és XMATCH bináris keresési módok Delphiben

A HotXLS, a natív Delphi és C++Builder táblázatkezelő komponens, egyetlen közös keresőmagon keresztül értékeli ki az XLOOKUP-ot és az XMATCH-et. Ez a mag négy egyeztetési módot (-1, 0, 1, 2) és négy keresési módot (-2, -1, 1, 2) fogad el, logaritmikus bináris leszállást futtat, amikor az abszolút keresési mód 2, és minden más kombinációt formulahibával utasít el

A hibajegy, amely idevezet, soha nem mondja azt, hogy "keresési mód". Azt mondja, hogy a szerveren generált munkafüzet más számot mutat, mint ugyanaz a fájl Excelben megnyitva, talán négy sornál kilencezerből. Ennek a négy sornak mindig van valami közös vonása: egy duplikált keresőkulcs, vagy egy közelítő egyezés, amelynek szomszédot kellett választania, vagy egy keresőoszlop, amelyet valaki egy másik oszlop szerint rendezett a múlt héten. A keresőfüggvények azok, ahol egy formulamotor abbahagyja az aritmetikát, és szerződéssé válik, és ennek a szerződésnek olyan kikötései vannak, amelyeket a legtöbb hívó soha nem olvas el

Mely módszámokat fogadja el valójában az XLOOKUP?

Pontosan négyet mindegyikből, semmi mást. A HotXLS a match_mode-ot -1, 0, 1 és 2 ellen ellenőrzi, a search_mode-ot pedig -2, -1, 1 és 2 ellen, mielőtt egyetlen cellához is hozzáérne, és bármilyen más érték #VALUE!-t ad vissza, ahelyett hogy a legközelebbi legális módra korlátozná. A négy egyeztetési mód a 0 pontosra, a -1 pontosra vagy a következő kisebbre, az 1 pontosra vagy a következő nagyobbra, a 2 pedig helyettesítő karakterre. A négy keresési mód az 1 előrefelé lineáris pásztázásra, a -1 hátrafelé lineáris pásztázásra, a 2 bináris keresésre növekvő sorrendű adatokon, a -2 pedig bináris keresésre csökkenő sorrendű adatokon. Ha kihagyjuk őket, a 0 egyeztetési mód és az 1 keresési mód kerül kiválasztásra, ez a párosítás, amelyet szinte minden valós formula használ. Az argumentumszámokat ugyanígy felügyeljük: az XLOOKUP három-hat argumentumot vesz fel, az XMATCH pedig kettő-négyet, és minden, ami ezeken a tartományokon kívül esik, #VALUE!, mielőtt a kiértékelés egyáltalán elkezdődne

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

Egy lépéssel korábban van egy csendesebb ellenőrzés, amelyet érdemes ismerni. A módargumentumok munkalap-kifejezésként érkeznek, így a HotXLS számmá alakítja őket, elutasítja a NaN-t és a végtelent, majd megköveteli, hogy a szám egyenlő legyen a saját lekerekített értékével. Az XLOOKUP(x, A:A, B:B, "none", 0, 1.5) egy #VALUE!, nem egy elrejtett 2-es keresési mód. Ez akkor számít, amikor a mód egy olyan cellából származik, amelyet egy kerekítésigényes számítás állított elő, ami gyakoribb generált munkafüzetekben, mint kézzel írtakban

Miért ad rossz választ a search_mode 2 rendezetlen adatokon?

Mert pontosan azt teszi, amit kértünk. A 2-es keresési mód azt közli a motorral, hogy a keresővektor már növekvő sorrendben van, és egy bináris keresés nem tudja ellenőrizni ezt az állítást olyan O(n) bejárás nélkül, amely megsemmisítené a használatának okát. A HotXLS ezért bízik a hívóban, felezi az intervallumot, és visszaadja, amire a leszállás landol. Rendezetlen bemeneten a válasz nem hiba, hanem csendben hibás, és ez inkább szerződésszegés, mint a motor hibája

A Microsoft ugyanezt az aszimmetriát dokumentálja az XLOOKUP-hoz és az XMATCH-hez: a bináris módok rendezett adatokat igényelnek, és egyébként érvénytelen eredményeket produkálnak. Az ISO 29500-1 18.17 szakasza, amely a SpreadsheetML formulanyelvtant definiálja, hordozza a régebbi LOOKUP és VLOOKUP leírásokat a saját növekvő sorrendi követelményükkel, és az XLOOKUP és az XMATCH elég régen jött ez után a szöveg után ahhoz, hogy _xlfn.XLOOKUP és _xlfn.XMATCH formában utazzon a fájlban a jövőbeli-függvény konvenció alatt. Más generáció, ugyanaz az alku: a hívó szolgáltatja a rendezési invariánst, a motor szolgáltatja a logaritmust

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;

Kövessük nyomon a második formulát, és a hiba teljesen mechanikus. A leszállás megvizsgálja a középső cellát, 10-et olvas, eldönti, hogy a 10 kisebb, mint a 40, elveti a bal felet, beleértve azt a sort, amely valójában a 40-et tartalmazta, megvizsgálja a 30-at, ismét elvet, és kifogy az intervallumból. Az Excel ugyanígy viselkedik, és ez a lényeg: a hibás válasz reprodukálása kompatibilitási követelmény, nem udvariasság. A rendezési előfeltevés szigorúbb is, mint a "számok növekvő sorrendben", mert az összehasonlító a fajtaszerinti rangsorolást teszi elsőnek, a számok, majd a szöveg, majd a boolean értékek, majd a hibaértékek, majd az üres cellák sorrendjében, és csak azután hasonlít össze egy fajtán belül. Egy numerikus cikkszámoszlop, amelyben három cella szöveget tartalmaz szám helyett, ez alatt az összehasonlító alatt nem növekvő, akárhogy is néz ki a képernyőn, és a bináris módok boldogan félreolvassák

Hova kerülnek a duplikált kulcsok?

A duplikátumsorozat egy determinisztikus végére, és hogy melyik vég, az a keresési módtól függ, nem a szerencsétől. Amikor a bináris leszállás egyenlő kulcsba ütközik a 2-es keresési mód alatt, rögzíti a pozíciót, majd tovább szűkít balra, így az eredmény a sorozat legalacsonyabb indexe; a -2-es keresési mód alatt, csökkenő adatokon, rögzíti a pozíciót, és jobbra szűkít, így az eredmény a legmagasabb index. A lineáris módok egyszerűbbek: az 1-es keresési mód az első előrefelé talált egyezést adja vissza, a -1-es az első hátrafelé találtat. Ez az a részlet, amely a bevezető bekezdésből ismert négysoros eltérést előidézi, mert egy olyan munkafüzet, amelynek kulcsai egyediek, azonos válaszokat ad mind a négy keresési mód alatt, és elrejti a különbséget minden teszten keresztül, amelyet egy tiszta mintafájlból írtunk. Adjunk hozzá egyetlen duplikált ügyfélkódot a termelési adatokhoz, és a módok pontosan azoknál a soroknál kezdenek eltérni, ahol duplikáltak: semmi nem változott a motorban, a bemenet csupán megszűnt halmaz lenni, és multihalmazzá vált

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

Hogyan választja ki a közelítő egyeztetés a másodikat?

Azzal, hogy a pontos egyeztetéses kereséssel párhuzamosan egy legjobb jelöltet is nyilvántart, és csak akkor adja vissza, ha nem jelenik meg pontos találat. A HotXLS a match_mode -1-et úgy kezeli, mint "a legnagyobb érték, amely nem nagyobb a célnál", a match_mode 1-et pedig úgy, mint "a legkisebb érték, amely nem kisebb", és mindkettő a teljes pásztázott terület fölött oldódik fel, nem az első elfogadható szomszédnál való megállással. A bináris útvonalon ugyanez az ötlet ingyen adódik a leszállásból: minden lépés, amely túllő vagy alullő, frissíti a jelöltet, így a végleges jelölt az a határelem, amely a pozíció mellett áll, ahová a kulcsot beszúrták volna

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

Olvassuk el figyelmesen a belső feltételt, mert ott lakik a döntetlen eldöntése. Egy új cella csak akkor váltja fel az álló jelöltet, ha szigorúan jobb, soha nem akkor, ha csupán egyenlő vele, így több, ugyanazt a második helyi értéket hordozó cella közül a megtartott az, amelyet a pásztázási sorrendben elsőként találunk: a legalacsonyabb index előrefelé pásztázásnál, a legmagasabb hátrafelé pásztázásnál. Ha az XLOOKUP és az XMATCH sem pontos találatot, sem elfogadható szomszédot nem talál, az XLOOKUP visszaesik a saját if_not_found argumentumára, ha azt megadtuk, és #N/A-ra, ha nem, míg az XMATCH mindig #N/A-t ad

Miért nem élhet együtt a helyettesítő karakter és a bináris keresés

Mert egy helyettesítő karakteres minta nem egy pozíció egy sorrendben. A 2-es egyeztetési mód azt kérdezi, hogy egy cella illeszkedik-e egy maszkra, és a maszkillesztés igennel vagy nemmel válaszol; egy bináris leszállásnak háromutas válaszra van szüksége, amely megmondja, melyik felet tartsa meg. Nincs védhető módja annak megkérdezésére, hogy az ACME-* egy adott cella bal vagy jobb oldalán fekszik-e, így a HotXLS elutasítja a match_mode 2-t search_mode 2-vel vagy -2-vel kombinálva, előre, #VALUE!-vel, ahelyett hogy kitalálná a sorrendet, és hihetőnek tűnő badarságot állítana elő. A két útvonal az egyenlőséget is másképp hasonlítja össze, ami megerősíti a szétválást: a lineáris pásztázás kis- és nagybetűt nem megkülönböztető szövegösszehasonlítással dönti el az egyenlőséget, vagy maszkillesztéssel, amikor a helyettesítő karakterek be vannak kapcsolva, míg a bináris leszállás az egyenlőséget úgy dönti el, hogy nullát kér a rendezési összehasonlítótól. Ez szándékos, nem a rétegződés véletlene, mivel a bináris útvonal csak azt a relációt használhatja, amely mentén ténylegesen navigál. Ha helyettesítő karakterekre van szükségünk, használjunk 1-es vagy -1-es keresési módot, és fogadjuk el a lineáris költséget, ami ugyanaz a kompromisszum, amelyet az inkrementális újraszámítás mögötti függőségkövetés a kritikus útvonalunkról igyekszik távol tartani

Alakhibák: kétdimenziós tartományok és nem egyező visszatérési vektorok

Mindkét függvény valódi egydimenziós keresőtartományt igényel. Ha a megadott tartomány egyszerre több sort és több oszlopot is átfog, a HotXLS #VALUE!-t ad vissza, ahelyett hogy helyettünk választana egy tengelyt, egy egysoros vagy egyoszlopos tartomány pedig a hosszú tengelye mentén kerül beolvasásra. Az XLOOKUP hozzáad egy második alakszabályt: a visszatérési tartománynak pontosan olyan hosszúnak kell lennie, mint a keresőtartomány az egyeztetési tengely mentén, így egy 500 soros függőleges keresés egy 499 soros visszatérési tartománnyal párosítva hiba, nem pedig egy csendben az utolsó sornál feloldott eltolási hiba. Amikor a visszatérési tartomány egy függőleges keresésnél egy oszlopnál szélesebb, vagy egy vízszintesnél egy sornál magasabb, az XLOOKUP a teljes egyeztetett szeletet tömbként adja vissza, és az a szomszédos cellákba ömlik, ugyanazok a szabályok szerint, mint a többi dinamikus tömbfüggvény, amelyet a ömlési tartományokról és dinamikus tömbökről szóló cikk ír le. Ez valóban hasznos egy teljes rekord kihúzásához egy táblából egyetlen formulával, és ez a leggyorsabb módja is annak, hogy felülírjunk egy oszlopot, amelyet meg akartunk tartani

Mód kiválasztása, amikor senki nem figyeli a képernyőt

A szerveroldali generálás szigorúbb szabályzatot érdemel, mint az interaktív használat, mert nincs ember, aki észrevenné, hogy egy összeg rosszul néz ki. A védhető alapértelmezés az 1-es keresési mód a 0-s egyeztetési móddal: lineáris, pontos, sorrendfüggetlen, és lehetetlen érvényteleníteni egy lap újrarendezésével. A 2-es keresési módhoz csak akkor nyúljunk, ha ugyanaz a kódútvonal állította elő a rendezést is, ugyanabban a futásban, ugyanazon az oszlopon, és ezt a függőséget írjuk le a formula mellett, mert egy bináris keresés egy másik kulcs szerint rendezett oszlopon a lehető legolcsóbb módja egy magabiztos rossz szám kiszámításának. Amikor a keresés valóban gyakori, és az adat valóban rendezett, a hozadék valódi: a leszállás nagyságrendileg log n cellát olvas n helyett, és ezen olvasások mindegyike egy teljes munkafüzet-cellafeloldáson megy keresztül, így a megtakarítás nagyobb, mint amennyit az utasításszám sugall

Ha a probléma alakja közelebb áll egy tartományi szabályhoz, mint egy kereséshez, egy visszahívás a saját Pascal kódunkba, ahogy azt az egyedi munkalapfüggvényekről szóló cikk tárgyalja, általában felülmúlja a beépítettek bármilyen ügyes elrendezését. Az itt tárgyalt XLOOKUP és XMATCH megvalósítások a standard HotXLS Delphi spreadsheet component részeként érhetők el, amelynek termékoldala hordozza a teljes támogatott-függvény referenciát Delphihez és C++Builderhez