Столбец из 10 000 формул, каждая из которых наращивает значение в ячейке над ней, — примерно самая дешёвая модель, какую может держать электронная таблица. В вычислителе, который вычисляет упомянутую формулу на месте при каждой встрече с ней, итоги всё равно сходятся, но арифметический счёт — нет: последняя ячейка протаскивает через вычисление 9 999 предков, та, что над ней, — 9 998, и один полный проход суммарно даёт около 50 миллионов вычислений ради 10 000 умножений. Поменяйте один темп роста наверху — и этому вычислителю придётся платить весь счёт заново, потому что он не ведёт записи о том, какая ячейка кого читает
Почему правка одной ячейки может стоить прохода по всей книге
Два упрощения дают такое поведение, и большинство самодельных движков формул берут одно из них. Рекурсивное упрощение вычисляет каждую упомянутую формулу заново и игнорирует уже кешированное значение — это превращает цепочку в квадратичную работу, а циклическую ссылку в переполнение стека. Упрощение полным проходом безопаснее: вычислить каждую формулу в каком-то фиксированном порядке столько раз, сколько потребуется, чтобы ничего не менялось. Он корректен, и его стоимость следует за размером книги, а не за размером правки
Excel избегает обоих с помощью своей цепочки вычислений — упорядочения формульных ячеек, при котором правка помечает небольшое множество ячеек, а обход идёт только по затронутому хвосту. Движок XLSX в HotXLS использует ту же идею в форме явного графа зависимостей за TXLSXWorkbook.Recalculate. Первый вызов строит граф по каждой формуле на каждом листе и вычисляет их все. Каждый последующий вызов вычисляет только формулы ниже по потоку от ячеек, чьи значения изменились с прошлого прохода, плюс короткий список формул, обязанных работать каждый раз
Как Recalculate превращает правку в один упорядоченный проход
Каждая формульная ячейка становится одним узлом, и ребро идёт от каждой читаемой формульной ячейки к читающей формуле. Ссылка вроде SUM(Model!B2:B500) даёт рёбра от каждой формульной ячейки внутри этого прямоугольника, а 3D-ссылка через пробег листов сверяется с каждым листом в пробеге. Обычные константы — вовсе не узлы; они важны лишь как место, где правка начинается
Запись Value в ячейку в момент записи почти ничего не делает. Книга ставит адрес ячейки в очередь — и всё. Когда Recalculate стартует, каждая формула, чьи ссылки покрывают адрес из очереди, помечается грязной, и метка течёт по рёбрам ко всем зависимым этой формулы, затем к зависимым зависимых. Книга, для которой Recalculate ни разу не вызывался, графа не держит, и её записи стоят одну проверку на nil, так что код, который только читает и пишет значения, за эту возможность не платит ничего
Затем грязная часть графа сортируется алгоритмом Кана. Деталь, делающая проход дешёвым, — как считаются входящие степени: считаются только грязные предшественники. Чистый предшественник уже держит валидное кешированное значение, поэтому формула его никогда не ждёт. Во время прохода формула, ссылающаяся на другую формульную ячейку, читает кешированное значение той ячейки вместо повторного вычисления; сортировка гарантирует, что кеш уже свежий. Каждая грязная формула вычисляется ровно один раз
Код ниже строит цепочку из вводного абзаца и правит её единственный вход. Индексы листов в HotXLS начинаются с 1, поэтому Inputs — лист 1, а Model — лист 2; строки и столбцы в Cells тоже отсчитываются с 1
uses
SysUtils, lxCalc, lxHandleX; // lxOk объявлен в 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; // допущение о росте в 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 // строит граф, вычисляет 9 999 формул
Exit;
Inputs.Cells[2, 2].Value := 0.07; // ставит в очередь один адрес
if Book.Recalculate = lxOk then // формулы, питающиеся от Inputs!B2, работают снова (здесь: все 9 999)
Last := Model.Cells[10000, 2].Value; // кешированный результат, читается как любое значение
// Разовое чтение: RecalcCell прогоняет Recalculate, затем возвращает ячейку
// (лист 2 = Model, строка 10000, столбец 2)
Book.RecalcCell(2, 10000, 2, Last);
finally
Book.Free;
end;
end;
В этой конкретной модели каждая формула читает Inputs!$B$2, так что второй проход всё равно трогает все 9 999; граф не может уменьшить правку, которая честно затрагивает всё. Экономия проявляется в моделях со множеством входов, где сценарный цикл пишет три-четыре ячейки, а остальная книга держит свои кешированные значения
Записи значений дёшевы, записи формул перестраивают граф
Инкрементальными остаются только правки значений. Всё, что может изменить множество узлов или рёбер, помечает весь граф устаревшим, и следующий Recalculate перестраивает его с нуля и вычисляет каждую формулу. Это покрывает присваивание Formula, очистку формульной ячейки записью Null или пустого значения, добавление, перемещение или удаление листов, вставку или удаление строк и столбцов, правку определённых имён и изменение таблиц данных «что-если». Регистрация или разрегистрация пользовательской функции или присваивание OnUserFunction сохраняют граф, но помечают грязным каждый узел
Практическое следствие для генераторов отчётов — форма цикла. Разложите формулы один раз, вызовите Recalculate и дальше трогайте только значения. Цикл, который переписывает шаблон формулы под каждого заказчика и затем пересчитывает, получает полную перестройку на каждой итерации — ровно ту стоимость, ради избежания которой граф и существует. Когда изменение шаблона действительно нужно, пакетируйте все правки формул впереди одного Recalculate, чтобы перестройка случилась один раз. Сам сценарный цикл дальше пишет только значения
// Модель построена один раз; Recalculate уже вызван
for I := 0 to High(Scenarios) do
begin
Inputs.Cells[2, 2].Value := Scenarios[I].Growth; // только записи значений
Inputs.Cells[3, 2].Value := Scenarios[I].Discount;
if Book.RecalcNeeded then // True, когда ячейки в очереди или грязные
if Book.Recalculate <> lxOk then
Break;
Results[I] := Model.Cells[10000, 2].Value;
end;
// Пусть SaveAs пересчитывает, только если что-то ещё в ожидании
Book.RecalcBeforeSave := xrmIfDirty;
Book.SaveAs('scenarios.xlsx');
RecalcBeforeSave по умолчанию xrmManual, который никогда не пересчитывает при сохранении. xrmIfDirty — настройка для генерируемых файлов: она пересчитывает, только когда граф устарел или имеет грязные формулы, так что книга, уже пересчитанная в цикле, записывается как есть, а книга с забытой правкой не сохраняется с устаревшими кешированными значениями
Какие функции Excel заставляют пересчитываться на каждом проходе
Формулы, вызывающие NOW, TODAY, RAND, RANDBETWEEN, RANDARRAY, OFFSET, INDIRECT, CELL, INFO или GETPIVOTDATA, волатильны в HotXLS: они помечаются грязными в начале каждого прохода, менялось ли что-то выше по потоку или нет, как и все их зависимые. Функции часов и случайных чисел волатильны по очевидной причине. OFFSET и INDIRECT волатильны потому, что ячейки, которые они читают, вычисляются из значений аргументов во время выполнения, и никакой статический обход формулы не скажет, какие рёбра рисовать
То же правило касается ссылок, которые построитель графа не может привязать к конкретному прямоугольнику, имени, ссылающегося само на себя через другие имена, ссылок на разливы динамических массивов и таблиц данных «что-если». Определённые имена в целом — не проблема: построитель разворачивает имя в диапазоны, на которые оно ссылается, так что формулы, идущие через имена уровня книги или листа, получают настоящие рёбра. Статья определённые имена и межлистовые формулы рассказывает, как эти имена разрешаются
Консервативное направление здесь — правильное. Лишнее вычисление стоит немного времени; пропущенное ребро значит устаревшее число в отчёте, который выглядит готовым. Держите OFFSET и INDIRECT подальше от горячих путей больших моделей и заприте их в немногих ячейках, которым реально нужны вычисляемые адреса, потому что волатильная ячейка у верха цепочки делает на практике волатильной всю цепочку
Функции, поставляемые через OnUserFunction или RegisterUserFunction, сидят на другом конце. Они не волатильны, поэтому обработчик вызывается снова только когда меняются ячейки, питающие его аргументы, — как любая встроенная функция. Обработчик, читающий курс валют из базы, поэтому продолжает возвращать свой последний ответ через проходы. Впишите курс в входную ячейку и передайте ту ячейку аргументом; тогда граф увидит зависимость, и формула перезапустится ровно при изменении курса. Статья пользовательские функции в движке формул HotXLS объясняет, как приходят аргументы обработчика
Циклические ссылки: lxErrorRef или итеративное вычисление
С умолчанием Iterate = False TXLSXWorkbook.Recalculate возвращает lxErrorRef, когда сортировка находит цикл. Члены цикла — грязные узлы, которые алгоритм Кана никогда не сможет освободить, и любая грязная формула ниже по потоку от них заблокирована по той же причине. Те формулы хранят прежние кешированные значения, тогда как всё остальное в грязном множестве вычисляется по порядку. Провальный проход также помечает граф устаревшим, так что следующий за ним вызов перестроит граф и вычислит каждую формулу ещё раз
case Book.Recalculate of
lxOk:
Book.SaveAs(OutputFile);
lxErrorRef:
// цикл и его нижележащие формулы всё ещё держат старые кеши;
// LogWarning — ваша собственная процедура
LogWarning('Circular reference in model, report not written');
else
LogWarning('Recalculation did not complete');
end;
Установка Iterate := True включает то же итеративное вычисление, что предлагает Excel. Движок вычисляет цикл и его заблокированных зависимых раз за разом, до IterateCount проходов (умолчание 100), пока никакое значение не сдвигается на IterateDelta (умолчание 0.001) или больше. Пустые члены цикла стартуют с 0. Достижение предела проходов сохраняет последние результаты и всё равно возвращает lxOk, поэтому для генерируемых отчётов итерация должна оставаться выключенной: циклы в настоящих отчётных моделях почти всегда ошибки — например, строка итога, пойманная внутри собственного диапазона SUM, — и от них вам нужен определённый код ошибки. Включайте только для моделей, построенных вокруг задуманного цикла, например проценты, начисляемые на средний баланс, включающий сами проценты
Один случай, выглядящий цикличным, циклом не сообщается. Аргумент lookup-array у VLOOKUP, HLOOKUP, LOOKUP, MATCH, XLOOKUP и XMATCH всё ещё делает формулу грязной при изменении ячейки в том диапазоне, но не идёт в счёт обнаружения циклов, поэтому VLOOKUP(A1,B:B,1), записанный в столбце B, вычисляется нормально. Для настоящих циклов трассировщик вычисления формул показывает цепочку ссылок, заворачивающуюся на себя, шаг за шагом
Формулы массива и многопоточные проходы
Legacy-формула массива CSE — один узел на весь заякоренный прямоугольник. Корневая формула вычисляется один раз за проход, её матрица записывается в каждую ячейку-члена (скалярный результат транслируется по прямоугольнику), и формула, ссылающаяся на любую ячейку прямоугольника, а не только на левый верхний якорь, получает ребро от корня. Формулы динамических массивов обрабатываются осторожнее: они работают каждый проход, и когда разлив меняет размер, Recalculate перестраивает граф и повторяет проход, пока формы разливов не устоятся. Если они не устоятся за 32 раунда, вызов возвращает lxErrorCalc
RecalcThreads выше 1 вычисляет каждый топологический уровень независимых формул по рабочим потокам, с отдельным вычислителем на поток. Таблицы данных всё ещё работают сериально, и книга с динамическими массивами остаётся на сериальном пути. Любой обработчик пользовательской функции обязан быть потокобезопасным, прежде чем вы поднимете это значение; для обработчика, трогающего общее состояние, надёжнее держать RecalcThreads на умолчании 0
Граф зависимостей, волатильная обработка и итеративное вычисление — часть движка XLSX в HotXLS Delphi Excel Component, который также покрывает калькулятор формул, определённые имена и конвейер чтения и записи вокруг них. Для приложений Delphi и C++Builder, которые держат открытыми тарифные листы или консолидационные книги и кормят их новыми входами весь день, работа за правку тогда следует ячейкам, которых правка реально достигает