我正在寻找一种不错的算法来解决以下问题。
我有以下变量和公式列表(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"需要"计算变量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并计算其值。
继续处理列表，直到它为空。
假设您没有循环依赖：一切都只计算一次！