Алгоритм вычисления ссылочных формул только один раз
Я ищу хороший алгоритм для решения следующей проблемы.
У меня есть следующий список VARIABLES и FORMULAS (результат var — это сумма всех формул):
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. поэтому я бы дважды вызвал var3 (изменилось var2, изменилось var1) …
есть ли решение не рассчитывать var3 дважды в этом сценарии?
Спасибо!
Решение
Да, вы можете обеспечить пересчет каждой переменной только один раз (самое большее), используя тот факт, что нет циклических зависимостей (ни в коем случае не переменная x потребности y для того, чтобы быть рассчитанным, и в то же время y также необходимо x).
Это делается путем моделирования проблемы как график, где все переменные являются вершинами, а «нужное» отношение — это направленное ребро. (Так что, если переменная x переменная «needs» y чтобы быть рассчитанным, есть преимущество (y,x)).
Теперь, поскольку нециклическая зависимость, это на самом деле Направленный ациклический граф, что вы можете сделать топологический вид (Это можно сделать только один раз при предварительной обработке). Обратите внимание, что вполне возможно, что в вашем случае график уже отсортирован, так как он задан в виде хронологической последовательности событий, а хронологический порядок является топологической сортировкой.
Выполните топологическую сортировку на графике (при необходимости) и при каждом изменении переменных:
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
Легко видеть, что каждая переменная рассчитывается не более одного раза в соответствии с этим подходом.
Другие решения
Держите список переменных / формул, которые необходимо пересчитать. Используя этот список, вы можете увидеть, все ли зависимости актуальны или нет.
Если это не так, вам следует отложить обновление переменной.
Возвращаясь к вашему примеру, и скажем var1 изменения.
Первый шаг — поставить var в списке и проверьте все зависимые переменные / формулы. Это var2 а также var3так что внесите их в список.
Затем проверьте зависимые переменные / формулы var2 (как вы положили его в список), это var3, это уже в списке, так что оставьте это. Последняя проверка var3 (вы также добавили его), ничего не зависит от var3 так что вы сделали. (Обратите внимание на рекурсивное поведение!)
Второй шаг — обновить ваши значения. Так что найдите переменную / формулу, которая имеет все свои зависимости. Только var1 не имеет зависимостей, поэтому вытащите его из списка и рассчитайте его значение.
Затем найдите другую переменную / формулу в списке, var3 все еще зависит от var2 (который все еще / также в списке), так что только var2 подходит для обработки.
Поэтому поп var2 из списка и рассчитать его стоимость.
Продолжайте обрабатывать список, пока он не станет пустым.
Предполагая, что у вас нет циклических зависимостей: все рассчитывается только один раз!