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

Question

Я ищу хороший алгоритм для решения следующей проблемы.

У меня есть следующий список ПЕРЕМЕННЫХ и ФОРМУЛЫ (результат вар является суммой всех формул):

var1, result=10 
    - 5+5=10 

var2, result=15 
    - var1+5 

var3, result=30 
    - var1+var2+5 

теперь я ищу хороший способ вычислить все ссылки. если я изменяю var1, а результат равен 15, я должен вычислить все ссылки на var1. сначала я столкнулся с var2 и recalc var2, если результат var2 изменился, мне нужно пересчитать все ссылочные формулы в var2. поэтому я бы recalc var3 дважды (var2 изменен, var1 изменен) ...

Есть ли какое-либо решение, чтобы не генерировать var3 дважды в этом сценарии?

thx!

Answer 1

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

Это делается путем моделирования проблемы как graph, где все переменные являются вершинами, а «необходимое» отношение является направленным ребром. (Итак, если переменная x «нужна» переменная y для расчета, есть край (y,x)).

Теперь, поскольку зависимость No-Cyclic на самом деле является Directed Acyclic Graph, которую вы можете сделать topological sort (это можно сделать только один раз в предварительной обработке). Обратите внимание, что очень возможно, что в вашем случае график уже отсортирован, sine задан как хронологическая последовательность событий, а хронологический порядок - топологический.

ли топологическую сортировку на графике (если это необходимо), и всякий раз, когда переменные изменяются:

Upon variable change: 
1. Mark all changed variables 
2. From first variable to last (according to topological sort), for each variable x: 
     2.1. If there is some dependency `(y,x)` on the graph such that `y` is marked: 
      2.1.1. mark x 
      2.1.2. recalculate x 

Легко видеть, что каждая переменная вычисляется как минимум раз в соответствии с этим подходом.

Answer 2

Сохраните список переменных/формул, которые необходимо пересчитать. Используя этот список, вы можете узнать, обновлены ли все зависимости или нет. Если это не так, вам следует отложить обновление переменной.

Возвращаясь к вашему примеру и скажем, var1 изменений.

Первый шаг - положить var в список и проверить все зависящие переменные/формулы. Это var2 и var3, поэтому поместите их в список.

Далее проверьте зависимые переменные/формулы var2 (как вы положили его в список), это var3, он уже находится в списке, поэтому оставьте его. Последняя проверка var3 (вы также добавили ее), ничего не зависит от var3, так что все готово. (Обратите внимание на рекурсивное поведение!)

Второй шаг - обновить ваши значения. Поэтому найдите переменную/формулу, которая имеет все свои зависимости. Только var1 не имеет зависимостей, поэтому вытащите его из списка и вычислите его значение.

Далее найти другую переменную/формулу в списке, var3 по-прежнему в зависимости от var2 (который до сих пор/также в списке), так что только var2 подходит к процессу. Посему pop var2 из списка и рассчитать его стоимость.

Продолжить обработку списка, пока он не станет пустым.

Предполагая, что у вас нет круговых зависимостей: все рассчитано только один раз!