Artykuł techniczny

Przyrostowe przeliczanie formuł w HotXLS dla Delphi

Kolumna 10 000 formuł, z których każda powiększa wartość z komórki nad sobą, to około najtańszy model, jaki arkusz może pomieścić. W evaluatorze, który liczy wskazywaną formułę na miejscu za każdym razem, gdy na nią trafia, sumy wychodzą w porządku, ale rachunek za arytmetykę już nie: ostatnia komórka wlecze przez wyliczenie 9 999 przodków, ta nad nią 9 998, a jeden pełny przebieg sumuje się do około 50 milionów wyliczeń dla 10 000 mnożeń. Zmień jedną stopę wzrostu na górze, a ten evaluator musi zapłacić cały rachunek jeszcze raz, bo nie trzyma żadnej ewidencji, która komórka czyta którą

Dlaczego edycja jednej komórki może kosztować przebieg po całym skoroszycie

Dwa uproszczenia dają takie zachowanie i większość ręcznie robionych silników formuł biera jedno z nich. Uproszczenie rekurencyjne wylicza każdą wskazywaną formułę od zera i ignoruje dowolną już zbuforowaną wartość, co zamienia łańcuch w pracę kwadratową, a odwołanie cykliczne w przepełnienie stosu. Uproszczenie pełnego przebiegu jest bezpieczniejsze: wylicz każdą formułę w pewnym ustalonym porządku, tyle razy, aż nic już się nie zmienia. To działa, a jego koszt rośnie z rozmiarem skoroszytu, nie z rozmiarem edycji

Excel omija jedno i drugie łańcuchem obliczeń — uporządkowaniem komórek z formułami, dzięki któremu edycja oznacza mały zbiór komórek i przechodzi tylko przez dotknięty ogon. Silnik XLSX w HotXLS używa tego samego pomysłu w postaci jawnego grafu zależności za TXLSXWorkbook.Recalculate. Pierwsze wywołanie buduje graf ze wszystkich formuł na wszystkich arkuszach i wylicza wszystkie. Każde kolejne wylicza tylko formuły w dół od komórek, których wartości zmieniły się od poprzedniego przebiegu, plus krótką listę formuł, które muszą biec za każdym razem

Jak Recalculate zamienia edycję w jeden uporządkowany przebieg

Każda komórka z formułą staje się jednym węzłem, a krawędź biegnie od każdej komórki z formułą, którą formuła czyta, do formuły czytającej. Referencja taka jak SUM(Model!B2:B500) produkuje krawędź od każdej komórki z formułą w tym prostokącie, a referencja 3D przez ciąg arkuszy jest zestawiana z każdym arkuszem ciągu. Zwykłe stałe nie są węzłami wcale; mają znaczenie tylko jako miejsce, w którym zaczyna się edycja

Zapis Value w komórce nie robi prawie nic w chwili zapisu. Skoroszyt kolejkuje adres komórki i to wszystko. Gdy Recalculate startuje, każda formuła, której referencje pokrywają skolejkowany adres, jest oznaczana jako zmieniona, a oznaczenie płynie krawędziami do wszystkich zależnych tej formuły, potem do ich zależnych. Skoroszyt, na którym Recalculate nigdy nie było wywoływane, nie trzyma grafu, a jego zapisy kosztują jedno sprawdzenie nil, więc kod, który tylko czyta i pisze wartości, nie płaci za tę funkcję nic

Zmieniona część grafu jest potem sortowana algorytmem Kahna. Szczegół, który czyni przebieg tanim, to sposób liczenia stopni wchodzących: liczą się tylko zmienieni poprzednicy. Czysty poprzednik trzyma już ważną zbuforowaną wartość, więc formuła nigdy na niego nie czeka. W trakcie przebiegu formuła odwołująca się do innej komórki z formułą czyta jej zbuforowaną wartość zamiast wyliczać ją ponownie; sortowanie gwarantuje, że bufor jest już świeży. Każda zmieniona formuła jest wyliczana dokładnie raz

Schemat blokowy jednego przebiegu Workbook.Recalculate HotXLS w Delphi, od zbierania flag brudu i sortowania topologicznego po ewaluację i raportowanie cykli
Każdy przebieg zbiera zbiór zmienionych komórek, sortuje go topologicznie i wylicza każdą dotkniętą komórkę raz; przy wyłączonym obliczaniu iteracyjnym cykl odwołań wraca jako lxErrorRef zamiast zapętlać

Kod poniżej buduje łańcuch z akapitu otwierającego i edytuje jego jedyne wejście. Indeksy arkuszy w HotXLS startują od 1, więc Inputs to arkusz 1, a Model to arkusz 2; wiersze i kolumny w Cells też są liczone od 1

uses
  SysUtils, lxCalc, lxHandleX;   // lxOk jest zadeklarowany w lxCalc

var
  Book: TXLSXWorkbook;
  Inputs, Model: TXLSXWorksheet;
  Row: Integer;
  Last: Variant;
begin
  Book := TXLSXWorkbook.Create;
  try
    Inputs := Book.Sheets.Add('Inputs');   // Sheets[1]
    Model  := Book.Sheets.Add('Model');    // Sheets[2]

    Inputs.Cells[2, 2].Value := 0.05;      // założenie wzrostu w Inputs!B2
    Model.Cells[2, 2].Formula := 'Inputs!B2*1000';
    for Row := 3 to 10000 do
      Model.Cells[Row, 2].Formula :=
        'B' + IntToStr(Row - 1) + '*(1+Inputs!$B$2)';

    if Book.Recalculate <> lxOk then      // buduje graf, wylicza 9 999 formuł
      Exit;

    Inputs.Cells[2, 2].Value := 0.07;      // kolejkuje jeden adres
    if Book.Recalculate = lxOk then        // formuły zasilane z Inputs!B2 biegną ponownie (tu: wszystkie 9 999)
      Last := Model.Cells[10000, 2].Value; // zbuforowany wynik, czytany jak każda wartość

    // Odczyt jednorazowy: RecalcCell uruchamia Recalculate, potem zwraca komórkę
    // (arkusz 2 = Model, wiersz 10000, kolumna 2)
    Book.RecalcCell(2, 10000, 2, Last);
  finally
    Book.Free;
  end;
end;

W tym konkretnym modelu każda formuła czyta Inputs!$B$2, więc drugi przebieg i tak dotyka wszystkich 9 999; graf nie umie zmniejszyć edycji, która faktycznie dotyczy wszystkiego. Oszczędność pokazuje się w modelach z wieloma wejściami, gdzie pętla scenariuszy zapisuje trzy czy cztery komórki, a reszta skoroszytu trzyma swoje zbuforowane wartości

Przykład grafu zależności pokazujący, że jedna edytowana komórka wejściowa w HotXLS oznacza jako brudne do ponownego wyliczenia tylko swoje docelowe formuły modelu Delphi
Edycja Inputs!B2 sieje jeden brudny węzeł; brudność spływa w dół krawędziami od poprzednika do zależnego, a tylko ten podgraf biegnie ponownie

Zapisy wartości są tanie, zapisy formuł przebudowują graf

Przyrostowe są tylko edycje wartości. Cokolwiek może zmienić zbiór węzłów albo krawędzi, oznacza cały graf jako przestarzały, a następne Recalculate buduje go od zera i wylicza każdą formułę. To obejmuje przypisanie Formula, wyczyszczenie komórki z formułą przez zapis Null albo pustej wartości, dodawanie, przenoszenie i usuwanie arkuszy, wstawianie i usuwanie wierszy i kolumn, edycję zdefiniowanych nazw oraz zmiany tabel danych what-if. Zarejestrowanie albo wyrejestrowanie funkcji użytkownika albo przypisanie OnUserFunction zachowuje graf, ale oznacza każdy węzeł jako zmieniony

Praktycznym skutkiem dla generatorów raportów jest kształt pętli. Rozmieść formuły raz, wywołaj Recalculate, a od tego momentu dotykaj wyłącznie wartości. Pętla, która przepisuje szablon formuły per klient i potem przelicza, dostaje pełną przebudowę w każdej iteracji — dokładnie ten koszt, przeciw któremu graf istnieje. Kiedy zmiana szablonu naprawdę jest potrzebna, zbierz wszystkie edycje formuł przed jednym Recalculate, żeby przebudowa stała się raz. Sama pętla scenariuszy pisze potem już tylko wartości

// Model zbudowany raz; Recalculate już wywołane
for I := 0 to High(Scenarios) do
begin
  Inputs.Cells[2, 2].Value := Scenarios[I].Growth;    // tylko zapisy wartości
  Inputs.Cells[3, 2].Value := Scenarios[I].Discount;
  if Book.RecalcNeeded then          // True, gdy komórki są skolejkowane albo zmienione
    if Book.Recalculate <> lxOk then
      Break;
  Results[I] := Model.Cells[10000, 2].Value;
end;

// Pozwól SaveAs przeliczać tylko wtedy, gdy coś jeszcze czeka
Book.RecalcBeforeSave := xrmIfDirty;
Book.SaveAs('scenarios.xlsx');

RecalcBeforeSave domyślnie ma xrmManual, które nigdy nie przelicza w trakcie zapisu. xrmIfDirty to ustawienie dla generowanych plików: przelicza tylko wtedy, gdy graf jest przestarzały albo ma zmienione formuły, więc skoroszyt już przeliczony w pętli jest zapisywany jak leci, a ten z zapomnianą edycją nie zostaje zapisany z nieświeżymi zbuforowanymi wartościami

Które funkcje Excela wymuszają przeliczanie przy każdym przebiegu?

Formuły wołające NOW, TODAY, RAND, RANDBETWEEN, RANDARRAY, OFFSET, INDIRECT, CELL, INFO albo GETPIVOTDATA są w HotXLS nietrwałe (volatile): są oznaczane jako zmienione na starcie każdego przebiegu, niezależnie od tego, czy cokolwiek po stronie dopływu się zmieniło, podobnie jak wszystkie ich zależne. Funkcje zegara i losowe są nietrwałe z oczywistego powodu. OFFSET i INDIRECT są nietrwałe, bo komórki, które czytają, są liczone z wartości argumentów w czasie biegu i żaden statyczny spacer po formule nie powie, które krawędzie narysować

Ta sama reguła dotyczy referencji, których budowniczy grafu nie potrafi przypiąć do konkretnego prostokąta, zdefiniowanej nazwy odsyłającej samej do siebie przez inne nazwy, referencji rozlań tablic dynamicznych i tabel danych what-if. Zdefiniowane nazwy ogólnie nie są problemem: budowniczy rozwija nazwę do zakresów, na które wskazuje, więc formuły przechodzące przez nazwy o zasięgu skoroszytu albo arkusza dostają prawdziwe krawędzie. Artykuł o zdefiniowanych nazwach i formułach międzyarkuszowych opisuje, jak te nazwy się rozwiązują

Kierunek konserwatywny jest tutaj właściwy. Zbędne wyliczenie kosztuje chwilę czasu; brakująca krawędź znaczy nieświeżą liczbę w raporcie, który wygląda na skończony. Trzymaj OFFSET i INDIRECT z dala od gorących ścieżek dużych modeli i zamknij je w kilku komórkach, które naprawdę potrzebują liczonych adresów, bo nietrwała komórka blisko góry łańcucha czyni w praktyce nietrwałym cały łańcuch

Funkcje dostarczone przez OnUserFunction albo RegisterUserFunction siedzą na drugim końcu. Nie są nietrwałe, więc handler jest wołany ponownie tylko wtedy, gdy zmienią się komórki zasilające jego argumenty — jak każda wbudowana funkcja. Handler czytający kurs walutowy z bazy danych będzie więc dalej zwracał swoją ostatnią odpowiedź przez kolejne przebiegi. Zapisz kurs do komórki wejściowej i przekaż tę komórkę jako argument; graf wtedy widzi zależność, a formuła odpala dokładnie wtedy, gdy kurs się zmieni. Artykuł o funkcjach własnych w silniku formuł HotXLS wyjaśnia, jak przychodzą argumenty handlera

Odwołania cykliczne: lxErrorRef albo obliczanie iteracyjne

Przy domyślnym Iterate = False TXLSXWorkbook.Recalculate zwraca lxErrorRef, gdy sortowanie znajdzie cykl. Członkowie cyklu to zmienione węzły, których algorytm Kahna nigdy nie zwolni, a każda zmieniona formuła w dół od nich jest zablokowana z tego samego powodu. Te formuły zachowują swoje poprzednie zbuforowane wartości, podczas gdy wszystko inne w zmienionym zbiorze jest wyliczane w porządku. Nieudany przebieg oznacza też graf jako przestarzały, więc wywołanie po nim przebuduje graf i wyliczy każdą formułę jeszcze raz

case Book.Recalculate of
  lxOk:
    Book.SaveAs(OutputFile);
  lxErrorRef:
    // cykl i jego formuły w dół wciąż trzymają stare bufory;
    // LogWarning to Twoja własna procedura
    LogWarning('Circular reference in model, report not written');
else
  LogWarning('Recalculation did not complete');
end;

Ustawienie Iterate := True włącza to samo obliczanie iteracyjne, które oferuje Excel. Silnik wylicza cykl i jego zablokowane zależne w kółko, do IterateCount przebiegów (domyślnie 100), aż żadna wartość nie ruszy się o IterateDelta (domyślnie 0,001) albo więcej. Puste członkowie cyklu startują od 0. Dobicie do limitu przebiegów zachowuje ostatnie wyniki i wciąż zwraca lxOk — dlatego iteracja powinna być wyłączona dla generowanych raportów: cykle w prawdziwych modelach raportów to prawie zawsze pomyłki, jak wiersz sumy złapany we własnym zakresie SUM, i od nich chce się jednoznaczny kod błędu. Włączaj ją tylko dla modeli zbudowanych wokół zamierzonej pętli, jak odsetki naliczane od średniego salda zawierającego te odsetki

Jeden przypadek wyglądający na cykliczny nie jest raportowany jako cykl. Argument lookup-array w VLOOKUP, HLOOKUP, LOOKUP, MATCH, XLOOKUP i XMATCH nadal oznacza formułę jako zmienioną, gdy komórka w tym zakresie się zmieni, ale nie liczy się do detekcji cykli, więc VLOOKUP(A1,B:B,1) wpisany w kolumnie B wylicza się normalnie. Dla prawdziwych cykli tracer wyliczania formuł pokazuje łańcuch odwołań zawijający się w siebie, krok po kroku

Formuły tablicowe i przebiegi wielowątkowe

Dawna formuła tablicowa CSE to jeden węzeł dla całego zakotwiczonego prostokąta. Formuła korzenia jest wyliczana raz na przebieg, jej macierz jest zapisywana do każdej komórki członkowskiej (wynik skalarny jest rozgłaszany po prostokącie), a formuła odwołująca się do dowolnej komórki prostokąta, nie tylko do lewego górnego kotwicy, dostaje krawędź od korzenia. Formuły tablic dynamicznych są prowadzone ostrożniej: biegają przy każdym przebiegu, a gdy rozlanie zmieni rozmiar, Recalculate przebudowuje graf i powtarza przebieg, aż kształty rozlań się ustabilizują. Jeśli nie ustabilizują się w ciągu 32 rund, wywołanie zwraca lxErrorCalc

RecalcThreads ustawione powyżej 1 wylicza każdy poziom topologiczny niezależnych formuł na wątkach roboczych, z osobnym kalkulatorem na wątek. Tabele danych wciąż biegają seryjnie, a skoroszyt zawierający tablice dynamiczne zostaje na ścieżce seryjnej. Każdy handler funkcji użytkownika musi być thread-safe, zanim podniesiesz tę wartość; dla handlera dotykającego współdzielonego stanu bezpieczniejszym wyborem jest trzymanie RecalcThreads na domyślnym 0

Graf zależności, obsługa nietrwałych i obliczanie iteracyjne są częścią silnika XLSX w HotXLS Delphi Excel Component, który obejmuje też kalkulator formuł, zdefiniowane nazwy i potok odczytu i zapisu wokół nich. Dla aplikacji Delphi i C++Builder, które trzymają otwarte arkusze wycen albo skoroszyty konsolidacyjne i zasilają je nowymi danymi cały dzień, koszt jednej edycji idzie wtedy po komórkach, do których edycja faktycznie dociera