Инкрементный пересчёт формул в HotXLS для Delphi

HotXLS, нативная библиотека Excel для Delphi и C++Builder, выполняет инкрементный пересчёт формул через TXLSXWorkbook.Recalculate. Первый вызов строит граф зависимостей формул и вычисляет каждую формульную ячейку; каждый последующий вызов пересчитывает только те ячейки, которые затронуты записями значений с прошлого прохода, в топологическом порядке, за один проход, чья стоимость пропорциональна числу грязных ячеек, а не размеру книги

Одно это проектное решение отделяет финансовую модель, отвечающую на изменённое допущение за миллисекунды, от модели, которая застревает на секунды. Если вы генерируете отчёты, где горстка входных ячеек питает тысячи формул ниже по потоку, остальная часть статьи объясняет, что делает граф, какие функции отказываются от инкрементальности и как циклические ссылки сообщаются вместо того, чтобы крутиться вечно

Почему изменение одной ячейки пересчитывает сто тысяч формул?

Наивный движок формул не помнит, кто от кого зависит, поэтому его единственный безопасный ход после любой правки — вычислить всё заново. Хуже того, классическая рекурсивная стратегия — когда формула A ссылается на формулу B, вычислить B на месте — пересчитывает ячейки, на которые ссылаются, безусловно, игнорируя любое кешированное значение. Цепочка из n формул, каждая из которых ссылается на предыдущую, стоит O(n²) вычислений за полный проход, а циклическая ссылка отправляет рекурсию в пропасть. Каждый разработчик электронных таблиц, который завёл каскадную модель в рекурсивный вычислитель, видел оба этих режима отказа

Сам Excel решил это десятилетия назад своей цепочкой вычислений: упорядочением формульных ячеек, поддерживаемым так, чтобы правка помечала грязным небольшой набор ячеек, а движок обходил только затронутый хвост цепочки. HotXLS применяет ту же идею в виде явного графа зависимостей, построенного один раз по скомпилированным деревьям формул и переиспользуемого между проходами пересчёта. Дело не в изобретательности; дело в том, что стоимость пересчёта должна следовать за размером вашей правки, а не за размером вашей книги

Как граф зависимостей превращает правку в один проход

Граф зависимостей HotXLS даёт каждой формульной ячейке один узел, а рёбра идут от предшественника к зависимому. Когда ваш код пишет значение ячейки, книга помечает эту ячейку грязной; когда работает Recalculate, грязность распространяется по рёбрам на каждую нижележащую формулу, и грязный подграф вычисляется ровно один раз в топологическом порядке по алгоритму Кана. Поскольку формула никогда не посещается раньше своих предшественников, каждому узлу нужно одно вычисление — именно это и делает проход O(грязных)

Топологический порядок заодно устраняет проблему рекурсии в корне. Во время прохода пересчёта движок переключается в особый режим, в котором любая ссылка на другую формульную ячейку читает кешированное значение этой ячейки напрямую, а не пересчитывает её, — упорядочение гарантирует, что кеш уже свежий. Тот же механизм означает, что цикл ссылок не может вызвать неограниченную рекурсию: ничто внутри прохода никогда не входит в вычислитель повторно ради соседней ячейки

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;                 // допущение о росте
    Model.Cells[2, 2].Formula := 'Inputs!B2*1000';    // формулы XLSX идут без ведущего '='
    Model.Cells[3, 2].Formula := 'B2*(1+Inputs!B2)';
    // ... ещё тысячи строк, каскадом идущих от того же допущения ...

    Book.Recalculate;                 // первый вызов: строит граф, полное вычисление

    Inputs.Cells[2, 2].Value := 0.07; // одна правка помечает одну ячейку грязной
    Book.Recalculate;                 // второй вызов: работает только нисходящая цепочка
  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:
    // существует цикл ссылок; участники цикла сохранили свои прежние
    // кешированные значения, а всё вне цикла актуально
    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 и есть разница между пересчётом книги и пересчётом правки