У меня есть задача по вычислительной алгебре, которую мне нужно написать. Задача разбита на четко определенные индивидуальные задачи, которые естественным образом образуют дерево - задача носит комбинаторный характер, поэтому есть основная задача, для получения которой требуется небольшое количество подрасчетов. Эти субсчеты имеют субсубсчеты и так далее. Каждый расчет зависит только от вычислений под ним в дереве (при условии, что корневой узел является верхним). Не требуется обмена данными между филиалами. На более низких уровнях количество подзадач может быть очень большим.
Ранее я кодировал это функционально, вызывая функции по мере необходимости и сохраняя все в оперативной памяти. Это был ужасный подход, но тогда меня больше волновала теория.
Я планирую переписать код на C ++ по разным причинам. У меня есть несколько требований:
- Проверка: Расчет занимает много времени, поэтому мне нужно иметь возможность остановиться в любой точке и возобновить позже.
- Разделяйте отдельные задачи как объекты: Это помогает мне хорошо понимать, где я нахожусь в вычислениях, и предлагает чистый способ выполнения контрольных точек с помощью сериализации.
- Многопоточность: Задача явно смущающе параллельна, поэтому было бы неплохо ее использовать. Возможно, я бы хотел использовать для этого темы Boost.
Я хотел бы получить предложения о том, как на самом деле реализовать такую систему. Способы, которыми я думал об этом:
- Реализация задач в виде простого стека. Когда вы нажимаете на задачу, которая нуждается в подрасчетах, она проверяет, есть ли у нее все подрасчеты, которые ей требуются. Если нет, то он создает подзадачи и выбрасывает их в стек. Если это так, то он вычисляет свой результат и извлекает себя из стека.
- Храните задачи в виде дерева и делайте что-то вроде шаблона посетителя на глубину. Это создаст все задачи в начале, а затем вычисления просто пройдут по дереву.
Это кажется не совсем правильным из-за проблем нижних уровней, требующих огромного количества подзадач. Полагаю, я мог бы подойти к этому итератором на этом уровне.
Мне кажется, я слишком обдумываю это, и уже есть простой, устоявшийся способ сделать что-то подобное. Есть ли один?
Технические детали, если они имеют значение:
- Дерево задач имеет 5 уровней.
- Коэффициент ветвления дерева действительно мал (скажем, между 2 и 5) для всех уровней, кроме самого низкого, который составляет порядка нескольких миллионов.
- Каждая отдельная задача должна хранить только результат размером в десятки байт. Я не возражаю против использования диска в максимально возможной степени, если только он не снижает производительность.
- Для отладки я должен иметь возможность вспомнить / пересчитать любую отдельную задачу.
- Все вычисления являются дискретной математикой: вычисления с целыми числами, полиномами и группами. Никакой плавающей запятой вообще.