Какие структуры данных использовать для построения формулы формулы

Question

Моя команда создает приложение, которое должно решать многие пользовательские формулы.Это замена для огромной таблицы, которую используют наши клиенты.Например, каждая формула использует простую арифметику (в основном) и несколько математических функций.Мы используем библиотеку оценки выражений под названием Parsii для выполнения фактической оценки формулы.Но среди всех формул мы должны оценивать их в порядке их зависимой формулы.Например,

F1 = a + b
F2 = F1 * 10%
F3 = b / 2
F4 = F2 + F3

В приведенном выше примере a, b являются значениями, введенными пользователями.Система должна изначально рассчитывать F1 и F3, поскольку они напрямую зависят от пользовательского ввода.Тогда F3 должен быть вычислен.И, наконец, F4.

Мой вопрос заключается в том, какая структура данных рекомендуется для моделирования этих зависимостей оценки формулы?

В настоящее время мы смоделировали ее как НАПРАВЛЕННЫЙ ГРАФ.В приведенном выше примере F1 и F3 являются корневым узлом, а F3 подключен к обоим, а F4 подключен к F3, F4 является конечным узлом.Мы использовали реализацию графа Tinkerpop3 для моделирования этого.

Любая структура данных, используемая для моделирования, должна иметь следующие характеристики.- Легко изменить некоторые входные данные нескольких корневых узлов верхнего уровня (на основе пользовательского ввода) - Пересчитать только те формулы, которые зависят от корневых узлов, которые были изменены (так как у нас есть сотни формул в конкретном контексте вычисления и мы имеемответить на уровень GUI в течение 1-2 секунд) - Минимизируйте объем кода для создания структуры данных с помощью некоторых существующих библиотек.- Уметь запрашивать структуру данных для запроса / поиска корневых узлов по различным ключам (имя объекта формулы, идентификатор объекта, год и т. Д.) И иметь возможность редактировать свойства этих ключей.

Answer 1

Храните ли вы это в виде простого файла в настоящее время?

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

Возможночто-то вроде этого (я ожидаю, что реальное решение будет несколько отличаться):

+-----------------------------------------------------------+
|                         FORMULA                           |
+------------+--------------+----------------+--------------+
|   ID (PK)  | FORMULA_NAME | FORMULA_STRING | FORMULA_YEAR |
+============+==============+================+==============+
|     1      |      F1      |     a + b      |              |
+------------+--------------+----------------+--------------+
|     2      |      F2      |    F1 * 10%    |              |
+------------+--------------+----------------+--------------+
|     3      |      F3      |     b / 2      |              |
+------------+--------------+----------------+--------------+
|     4      |      F4      |    F2 + F3     |              |
+------------+--------------+----------------+--------------+


+--------------------------------------+
|         FORMULA_DEPENDENCIES         |
+-----------------+--------------------+
| FORMULA_ID (FK) | DEPENDS_ON_ID (FK) |
+=================+====================+
|        2        |         1          |
+-----------------+--------------------+
|        4        |         2          |
+-----------------+--------------------+
|        4        |         3          |
+-----------------+--------------------+

С этим вы также можете легко узнать, зависит ли формула от несуществующей формулы, потому что это нарушитDEPENDS_ON_ID внешний ключ.Также база данных может определить, образует ли какая-либо из формул цикл зависимостей.Например, где F1 зависит от F2 зависит от F3 зависит от F1.

Кроме того, вы можете легко добавлять любые метаданные, которые вы хотите, в таблицы и индексировать все, к чему вы можете обращаться.