Inkrementálny prepočet vzorcov v HotXLS pre Delphi

HotXLS, natívna Excel knižnica pre Delphi a C++Builder, robí inkrementálny prepočet vzorcov cez TXLSXWorkbook.Recalculate. Prvé volanie postaví graf závislostí vzorcov a vyhodnotí každú formulovú bunku; každé ďalšie volanie prepočíta iba bunky zasiahnuté zápismi hodnôt od posledného prechodu, a to v topologickom poradí a v jedinom prechode, ktorého náklad je úmerný počtu špinavých buniek, nie veľkosti zošita

Práve toto jedno návrhové rozhodnutie je rozdielom medzi finančným modelom, ktorý na upravený predpoklad odpovie v milisekundách, a modelom, ktorý sa zasekne na sekundy. Ak generujete reporty, kde hŕstka vstupných buniek napája tisíce nadväzujúcich vzorcov, zvyšok tohto článku vysvetľuje, čo graf robí, ktoré funkcie sa z inkrementálnosti vyväzujú a ako sa cyklické odkazy hlásia namiesto nekonečného cyklenia

Prečo zmena jednej bunky prepočíta stotisíc vzorcov?

Naivný engine na vzorce si nepamätá, kto od koho závisí, takže jeho jediným bezpečným ťahom po akejkoľvek úprave je vyhodnotiť všetko znova. Horšie je, že klasická rekurzívna stratégia — keď vzorec A odkazuje na vzorec B, vyhodnoť B na mieste — prepočítava odkazované bunky bezpodmienečne a ignoruje akúkoľvek hodnotu v cache. Reťaz n vzorcov, z ktorých každý odkazuje na predchádzajúci, stojí O(n²) vyhodnotení na jeden plný prechod a cyklický odkaz pošle rekurziu z útesu. Každý vývojár tabuliek, ktorý napojil kaskádový model na rekurzívny evaluátor, sledoval oba spôsoby zlyhania

Excel to sám vyriešil pred desaťročiami svojou výpočtovou reťazou: usporiadaním formulových buniek udržiavaným tak, aby úprava označila malú množinu buniek za špinavé a engine prešiel len zasiahnutý chvost reťaze. HotXLS uplatňuje tú istú myšlienku ako explicitný graf závislostí, postavený raz zo skompilovaných stromov vzorcov a znovu použitý naprieč prepočtovými prechodmi. Nejde o dômyselnosť; ide o to, že náklad prepočtu má sledovať veľkosť vašej úpravy, nie veľkosť zošita

Ako graf závislostí premení úpravu na jediný prechod

Graf závislostí v HotXLS dáva každej formulovej bunke jeden uzol, s hranami vedúcimi od predchodcu k závislému. Keď váš kód zapíše hodnotu bunky, zošit si bunku poznačí ako špinavú; keď beží Recalculate, špinavosť sa šíri po hranách ku každému nadväzujúcemu vzorcu a špinavý podgraf sa vyhodnotí presne raz v topologickom poradí pomocou Kahnovho algoritmu. Keďže vzorec sa nikdy nenavštívi pred svojimi predchodcami, každý uzol potrebuje jediné vyhodnotenie — a práve to robí z prechodu O(špinavé)

Topologické poradie zároveň rieši problém rekurzie pri jeho koreni. Počas prepočtového prechodu sa engine prepne do vyhradeného režimu, v ktorom akýkoľvek odkaz na inú formulovú bunku prečíta jej hodnotu z cache priamo namiesto jej opätovného vyhodnotenia — usporiadanie zaručuje, že cache je už čerstvá. Ten istý mechanizmus znamená, že cyklus odkazov nemôže spustiť neohraničenú rekurziu: nič vnútri prechodu nikdy nevstúpi do evaluátora znovu kvôli susednej bunke

var
  Book: TXLSXWorkbook;
  Inputs, Model: TXLSXWorksheet;
begin
  Book := TXLSXWorkbook.Create;
  try
    Inputs := Book.Sheets.Add('Inputs');
    Model  := Book.Sheets.Add('Model');

    Inputs.Cells[2, 2].Value := 0.05;                 // predpoklad rastu
    Model.Cells[2, 2].Formula := 'Inputs!B2*1000';    // vzorce XLSX nemajú úvodné '='
    Model.Cells[3, 2].Formula := 'B2*(1+Inputs!B2)';
    // ... tisíce ďalších riadkov kaskádovito visiacich na tom istom predpoklade ...

    Book.Recalculate;                 // prvé volanie: postaví graf, plné vyhodnotenie

    Inputs.Cells[2, 2].Value := 0.07; // jedna úprava označí jednu bunku za špinavú
    Book.Recalculate;                 // druhé volanie: beží len nadväzujúca reťaz
  finally
    Book.Free;
  end;
end;

Každý výsledok pristane v hodnote Value uloženej v cache bunky, takže po návrate z Recalculate čítate výstupy rovnako ako ktorúkoľvek inú bunku. V slučke generovania reportov je vzor presne ten z kódu vyššie: model raz načítajte alebo postavte a potom striedajte zápis niekoľkých vstupných buniek s volaním Recalculate, pričom platíte len za vzorce, ktoré na zmenenom naozaj závisia

Ktoré funkcie Excelu vynútia prepočet pri každom prechode?

HotXLS považuje NOW, TODAY, RAND, OFFSET a INDIRECT za volatilné: každý vzorec obsahujúci niektorú z nich sa prepočíta pri každom prechode Recalculate bez ohľadu na to, či sa vyššie v reťazi niečo zmenilo. Prvé tri sú volatilné z rovnakého dôvodu ako v Exceli — ich výsledok závisí od okamihu vyhodnotenia, nie od iných buniek. OFFSET a INDIRECT sú volatilné z jemnejšieho dôvodu: bunky, ktoré čítajú, sa počítajú za behu, takže graf staticky nevie, aké hrany pre ne nakresliť

To isté konzervatívne pravidlo sa vzťahuje aj na odkazy, ktoré staviteľ grafu nedokáže pripnúť na jediný obdĺžnik. Vzorec, ktorý prechádza cez pomenovanú oblasť s viacerými časťami alebo odkazuje na externý zošit, je rovnako degradovaný na volatilný a prepočíta sa pri každom prechode. Táto politika je zámerná: vyhodnotenie navyše stojí trochu času, no chýbajúca hrana závislosti znamená ticho zastaranú hodnotu v odoslanom reporte, čo je oveľa horšie zlyhanie. Ak sa váš model opiera o názvy s rozsahom zošita, sprievodný článok o definovaných názvoch a vzorcoch naprieč hárkami rozoberá, ako sa vyhodnocujú jednooblastné názvy — tie sa grafu zúčastňujú normálne

Praktické odporúčanie z toho plynie priamo. Horúce cesty veľkého modelu držte na obyčajných odkazoch na bunky a oblasti, kde graf môže robiť svoju prácu, a OFFSET aj INDIRECT uzavrite do tých pár miest, ktoré dynamické adresovanie naozaj potrebujú. Model s tisíckou volatilných vzorcov ich tisíc prepočíta pri každom prechode bez ohľadu na to, aká malá bola úprava — presne to správanie, ktoré používatelia Excelu poznajú zo zošitov „prepočítavajúcich sa pri každom stlačení klávesu“

Ako HotXLS hlási cyklické odkazy?

TXLSXWorkbook.Recalculate vracia lxOk pri čistom prechode a lxErrorRef, keď zistí cyklus odkazov. Členovia cyklu sa identifikujú počas topologického triedenia — sú to uzly, ktoré Kahnov algoritmus nikdy nedokáže uvoľniť — a namiesto cyklenia sa preskočia: ich hodnoty v cache zostanú také, aké boli, kým každý vzorec mimo cyklu sa aj tak normálne vyhodnotí v poradí. Vaše volajúce miesto dostane jednoznačný chybový kód namiesto zamrznutia

case Book.Recalculate of
  lxOk:
    SaveReport(Book);
  lxErrorRef:
    // existuje cyklus odkazov; členovia cyklu si ponechali svoje predchádzajúce
    // hodnoty z cache a všetko mimo cyklu je aktuálne
    LogWarning('Circular reference detected - review model inputs');
end;

Nájsť, ktoré bunky cyklus tvoria, je ladiaca úloha a tracer vyhodnocovania vzorcov je na ňu tým správnym nástrojom: vytrasujte podozrivý vzorec a reťaz odkazov, ktorá sa sama do seba vracia, sa krok po kroku stane viditeľnou. Cykly v reálnych modeloch sú takmer vždy chybou autora — súhrnný riadok omylom zahrnutý do vlastnej oblasti SUM — takže hlasitý chybový kód v čase prepočtu je presne to, čo chcete

Maticové vzorce, sledovanie špinavosti a kedy sa graf prestavuje

Maticové vzorce zadávané cez CSE dostanú jeden uzol pre celý ukotvený obdĺžnik, nie jeden uzol na bunku. Koreňový vzorec sa vyhodnotí raz za prechod; výsledná matica sa zapíše priamo do každej členskej bunky a vzorec, ktorý odkazuje na ktorúkoľvek bunku vnútri ukotvenej oblasti — nielen na ľavú hornú kotvu — získa hranu závislosti od tohto koreňového uzla. Skalárne výsledky sa rozšíria po obdĺžniku tak, ako predpisuje staršia maticová sémantika Excelu

Sledovanie špinavosti sa zavesí na obyčajné settery vlastností, takže sa na vašom kóde nič nemení. Zápis do Value bunky upovedomí zošit a označí závislých za špinavých; priradenie nového Formula je štrukturálnou zmenou, takže označí celý graf za zastaraný a ďalší Recalculate ho pred vyhodnotením prestaví. Pridanie, zmazanie alebo presun hárkov graf tiež zneplatní, keďže identita uzla nesie index hárka. Keď žiadny graf nie je aktívny — zošit, na ktorom Recalculate nikdy nezavoláte — stoja tieto háčiky jednu kontrolu na nil pri každom priradení, takže bežné čítacie a zápisové záťaže nie sú dotknuté

Jedna hranica stojí za úprimné pomenovanie: graf sleduje závislosti medzi bunkami, takže používateľom definovaná funkcia zaregistrovaná cez OnUserFunction sa prepočíta vtedy, keď sa zmenia bunky napájajúce jej argumenty, rovnako ako každý iný vzorec. Ak engine takto rozširujete, článok o vlastných funkciách v engine vzorcov HotXLS prechádza kontrakt spätného volania aj to, ako prichádzajú hodnoty argumentov

Inkrementálny prepočet je súčasťou štandardného enginu XLSX v komponente HotXLS Delphi Excel Component, popri kalkulátore vzorcov, definovaných názvoch a importno-exportnej pipeline, ktorú zrýchľuje. Ak vaša aplikácia v Delphi alebo C++Builderi udržiava živé modely — cenníkové hárky, konsolidačné zošity, kaskády reportov — je Recalculate rozdielom medzi prepočítaním zošita a prepočítaním úpravy