HotXLS, рідна бібліотека Excel для Delphi та C++Builder, виконує інкрементний перерахунок формул за допомогою TXLSXWorkbook.Recalculate. Перший виклик будує граф залежностей формул та обчислює кожну формульну клітинку; кожен наступний виклик переоцінює лише ті клітинки, на які вплинули записані значення з моменту останнього проходу, в топологічному порядку за один прохід, вартість якого пропорційна кількості брудних клітинок, а не розміру робочої книги
Саме це дизайнерське рішення визначає різницю між фінансовою моделлю, яка реагує на змінене припущення за мілісекунди, та тією, що зависає на секунди. Якщо ви генеруєте звіти, де кілька вхідних клітинок живлять тисячі підпорядкованих формул, інша частина цієї статті пояснює, що робить граф, які функції відмовляються від інкрементності та як повідомляється про циклічні посилання замість нескінченного зациклення
Чому зміна однієї клітинки перераховує сто тисяч формул?
Наївний рушій формул не пам'ятає, хто від кого залежить, тому його єдиний безпечний крок після будь-кого редагування — перерахувати все заново. Гірше того, класична рекурсивна стратегія — коли формула А посилається на формулу Б, обчислити Б на місці — переоцінює клітинки, на які посилаються, безумовно, ігноруючи будь-яке кешоване значення. Ланцюжок із n формул, кожна з яких посилається на попередню, коштує O(n²) обчислень за повний прохід, а циклічне посилання взагалі обриває рекурсію в прірву. Кожен розробник електронних таблиць, який підключав каскадну модель до рекурсивного обчислювача, спостерігав обидва режими відмови
Сам Excel вирішив це десятиліття тому за допомогою свого ланцюжка обчислень: впорядкування формульних клітинок підтримується так, що редагування позначає невеликий набір клітинок як брудні, і рушій проходить лише по ураженому хвосту ланцюжка. HotXLS застосовує ту саму ідею як явний граф залежностей, побудований один раз із скомпільованих дерев формул і повторно використаний у проходах перерахунку. Справа не у винахідливості, а в тому, що вартість перерахунку повинна відстежувати розмір вашого редагування, а не розмір вашої робочої книги
Як граф залежностей перетворює редагування на один прохід
Граф залежностей HotXLS надає кожній формульній клітинці один вузол, причому ребра йдуть від прецеденту до залежного. Коли ваш код записує значення клітинки, робоча книга фіксує клітинку як брудну; коли запускається Recalculate, бруд поширюється по ребрах до кожної підпорядкованої формули, і брудний підграф оцінюється рівно один раз у топологічному порядку за допомогою алгоритму Кана. Оскільки формула ніколи не відвідується раніше за свої прецеденти, кожному вузлу потрібна одна оцінка — саме це робить прохід O(dirty)
Топологічний порядок також вирішує проблему рекурсії в її корені. Під час проходу перерахунку рушій перемикається в спеціальний режим, у якому будь-яке посилання на іншу формульну клітинку зчитує кешоване значення цієї клітинки безпосередньо замість її переоцінки — впорядкування гарантує, що кеш уже свіжий. Цей самий механізм означає, що цикл посилань не може викликати необмежену рекурсію: ніщо всередині проходу ніколи не входить повторно в обчислювач для сусідньої клітинки
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; // growth assumption
Model.Cells[2, 2].Formula := 'Inputs!B2*1000'; // XLSX formulas take no leading '='
Model.Cells[3, 2].Formula := 'B2*(1+Inputs!B2)';
// ... thousands more rows cascading off the same assumption ...
Book.Recalculate; // first call: builds the graph, full evaluation
Inputs.Cells[2, 2].Value := 0.07; // one edit marks one cell dirty
Book.Recalculate; // second call: only the downstream chain runs
finally
Book.Free;
end;
end;Кожен результат потрапляє в кешоване значення клітинки Value, тому після повернення Recalculate ви зчитуєте вихідні дані так само, як і для будь-якої іншої клітинки. У циклі генерації звітів шаблон точно відповідає наведеному вище коду: завантажте або побудуйте модель один раз, а потім чергуйте запис кількох вхідних клітинок та виклик Recalculate, сплачуючи лише за формули, які реально залежать від того, що змінилося
Які функції Excel примусово викликають перерахунок на кожному проході?
HotXLS розглядає NOW, TODAY, RAND, OFFSET та INDIRECT як леткі: будь-яка формула, що містить одну з них, переоцінюється на кожному проході Recalculate, незалежно від того, чи змінилося щось вище за течією. Перші три є леткими з тієї ж причини, що й в Excel — їхній результат залежить від моменту обчислення, а не від інших клітинок. OFFSET та INDIRECT є леткими з більш тонкої причини: клітинки, які вони зчитують, обчислюються під час виконання, тому граф не може статично знати, які ребра малювати для них
Це саме консервативне правило поширюється на посилання, які конструктор графа не може прив'язати до одного прямокутника. Формула, яка проходить через іменований діапазон із кількома областями, або та, що посилається на зовнішню робочу книгу, так само понижується до леткої та переоцінюється при кожному проході. Ця політика є свідомою: додаткова оцінка коштує небагато часу, але відсутнє ребро залежності означає приховано застаріле значення у звіті, а це набагато гірша помилка. Якщо ваша модель спирається на імена в межах робочої книги, супутня стаття про визначені імена та формули між аркушами описує, як вирішуються імена з однією областю — вони беруть участь у графі звичайним чином
Практичне керівництво випливає безпосередньо з цього. Тримайте гарячі шляхи великої моделі на простих посиланнях на клітинки та діапазони, де граф може виконувати свою роботу, і ізолюйте OFFSET та INDIRECT у тих кількох місцях, які справді потребують динамічної адресації. Модель із тисячею летких формул повторно запускає цю тисячу на кожному проході, незалежно від того, наскільки дрібним було редагування — саме таку поведінку користувачі Excel знають з робочих книг, які «перераховуються при кожному натисканні клавіші»
Як HotXLS повідомляє про циклічні посилання?
Метод TXLSXWorkbook.Recalculate повертає lxOk при чистому проході та lxErrorRef при виявленні циклу посилань. Учасники циклу виявляються під час топологічного сортування — це вузли, які алгоритм Кана ніколи не може звільнити — і вони пропускаються, а не зациклюються: їхні кешовані значення залишаються такими, якими були, тоді як кожна формула поза циклом все одно оцінюється нормально по порядку. Місце виклику отримує чіткий код помилки замість зависання
case Book.Recalculate of
lxOk:
SaveReport(Book);
lxErrorRef:
// a reference cycle exists; cycle members kept their previous
// cached values and everything outside the cycle is up to date
LogWarning('Circular reference detected - review model inputs');
end;Пошук клітинок, які утворюють цикл, є завданням налагодження, і трасувальник обчислення формул є правильним інструментом для цього: простежте підозрілу формулу, і ланцюжок посилань, який згортається сам на себе, стане видимим крок за кроком. Цикли в реальних моделях майже завжди є помилкою автора — рядок підсумків випадково включений у свій власний діапазон SUM — тому гучний код помилки під час перерахунку є саме тим, що вам потрібно
Формули масивів, відстеження бруду та коли граф перебудовується
Формули масивів CSE отримують один вузол для всього закріпленого прямокутника, а не один вузол на клітинку. Коренева формула оцінюється один раз за прохід; отримана матриця записується безпосередньо в кожну клітинку-член, а формула, яка посилається на будь-яку клітинку всередині закріпленого діапазону — не лише на верхній лівий якір — підхоплює ребро залежності від цього кореневого вузла. Скалярні результати транслюються по прямокутнику так, як приписує застаріла семантика масивів Excel
Відстеження бруду підключається до звичайних методів встановлення властивостей, тому у вашому коді нічого не змінюється. Запис Value у клітинку сповіщає робочу книгу та позначає залежні клітинки як брудні; призначення нової Formula є структурною зміною, тому воно позначає весь граф як застарілий, і наступний виклик Recalculate перебудовує його перед оцінкою. Додавання, видалення або переміщення аркушів також анулює граф, оскільки ідентичність вузла кодує індекс аркуша. Коли граф не є активним — робоча книга, для якої ви ніколи не викликаєте Recalculate — гачки коштують однієї перевірки на nil на призначення, тому звичайні навантаження на читання-запис не зачіпаються
Один ліміт варто сформулювати чесно: граф відстежує залежності між клітинками, тому користувацька функція, зареєстрована через OnUserFunction, переоцінюється, коли змінюються клітинки, що живлять її аргументи, як і будь-яка інша формула. Якщо ви розширюєте рушій таким чином, стаття про користувацькі функції в рушії формул HotXLS описує контракт зворотного виклику та те, як надходять значення аргументів
Інкрементний перерахунок є частиною стандартного рушія XLSX у компоненті HotXLS Delphi Excel Component, разом із обчислювачем формул, визначеними іменами та конвеєром імпорту/експорту, який він прискорює. Якщо ваш додаток на Delphi або C++Builder підтримує живі моделі — листи ціноутворення, книги консолідації, каскади звітів — Recalculate є різницею між перерахунком робочої книги та перерахунком редагування