Типовой способ расчета электронной таблицы заключается в том, что в памяти строится таблица, содержащая выражения ячеек, а затем все эти ячейки рекурсивно вычисляются. То есть, если ячейка A1 ссылается на другую (скажем, C2), чтобы получить значение C2 из поцедуры вычисления A2 вызывается вычисление C2.

Несмотря на все достоинства, у такого метода есть очевидные недостатки.

• Циклические ссылки представляют проблему. Поэтому при расчетах требуются дополнительные усилия, чтобы либо отмечать ячейки, которые сейчас в состоянии расчета, либо вести определенный лог, в котором перечичслены ячейкм в состоянии расчета.
• Такой подход трудно масштабировать. Предполагается, что вся таблица должна быть в памяти и доступна в любой момент.

Я предполагаю использовать другой подход, который на мой взгляд проще для восприятия и сопровождения. Идея простая – мы пытаемся вычислить ячейки в том порядке, в котором нам их поставляет парсер. И если не хватает зависимостей, чтобы вычислить ячейку – мы просто откладываем ее вычисление на “попозже”.

То есть алгоритм такой

• парсер при разборе заносит все выражения ячеек в определенную очередь
• вычислитель пробует вычислить первую ячейку из очереди.
• если удалось, ее значение помещается в valuecache, а сама ячейка удаляется из очереди.
• если не удалось – эта ячейка помещается в конец очереди.
• когда очередь станет пустой – это значит вся таблица рассчитана, можно начинать ее печатать.
• В случае циклических зависимостей или нереальных ссылок (например за границы таблицы) в очереди образуется сухой остаток – ячейки которые невозможно рассчитать в принципе. Мы их просто переносим в valuecache со значением {error, badref};
• Чтобы узнать, что остались только нерешаемые ячейки в очереди, будем вести счетчик подряд неудачных вычислений (который сбрасывается при любом удачном вычислении). Если этот счетчик больше чем длина очереди – значит мы просто тасуем нерешаемые ячейки.

Тогда складывается такой набор модулей:

Модули

• Главный модуль, содержит start point
• parser считывает stdin и делает разбор таблицы и ячеек в внутреннюю форму. Результат помещается в “трубу”
• solver вычисляет значения ячеек из “трубы” и помещает значения ячеек в valuecache. Разруливает зависимости ячеек.
• print выводит простыню в stdout из valuecache.
• machine вычисление выражений ячеек
• cell управляет внешним видом ячеек. То есть – как они должны выглядеть в выводе, как должны собираться/разбираться ссылки на ячейки.
• valuecache хранит значения (только значения, никаких формул), ячеек. Простое KV storage
• pipe “труба” применяемая для разруливания порядка расчетов ячеек, это по натуре queue

Достоинства такого алгоритма

• Легко масштабируется по памяти – интерфейс valuecache и pipe простые, реализация скрыта, ничто не мешает при необходимости переписать valuecache чтобы он использовал, скажем, nosql для сохранения данных, Или к примеру использовать AMQP для очереди. При этом остальная часть программы, естественно, остается неихменной.
• Легко масштабируется по процессам/процессорам. Для этого надо всего лишь выполнить партиц. партишн. распилить очередь по числу процессов, и дать каждому процессу по его куску очереди. А когда они все завершат работу, собрать нерешаемые ячейки из этих очередей в одну и пройтись еще раз по ней решателем.
• Легко отлаживается – сам алгоритм простой и занимает полстраницы кода, модули имеют минимум зависимостей и ясные интерфейсы (что позволяет их эфективно проверять с помощью unit тестов),
• Не имеет в своем составе холестерина

Недостатки

• Скорость должна быть ниже, чем в случае рекурсивного решателя. Потому, что некоторые ячейки придется считать несколько раз.
• Этот алгоритм удобен только для пакетной обработки.