php - 仅计算一次引用公式的算法

Question

我正在寻找一个很好的算法来解决以下问题。

我有以下 VARIABLES 和 FORMULAS 列表(var 的结果是所有公式的总和):

var1, result=10
  - 5+5=10

var2, result=15
  - var1+5

var3, result=30
  - var1+var2+5

现在我正在寻找一种计算所有引用的好方法。如果我正在更改 var1，结果现在是 15，我必须计算所有引用 var1 的值。首先，我遇到了 var2 并重新计算了 var2，如果 var2 的结果发生了变化，我必须将所有引用的公式重新计算到 var2。因此我会重新计算 var3 两次(var2 已更改，var1 已更改)...

在这种情况下有没有不计算 var3 两次的解决方案？

谢谢!

Answer 1

是的，你可以确保你只重新计算每个变量一次(最多)，通过使用没有循环依赖的事实(变量 x 不可能需要 y 为了计算，同时 y 还需要 x)。

这是通过将问题建模为 graph 来完成的，其中所有变量都是顶点，“所需”关系是有向边。 (因此，如果变量 x“需要”计算变量 y，则存在边 (y,x))。

现在，由于无循环依赖，这实际上是一个 Directed Acyclic Graph ，你可以做到topological sort (这只能在预处理中完成一次)。请注意，在您的情况下，图表很可能已经排序，因为它是作为事件的时间顺序给出的，并且时间顺序是拓扑排序。

对图进行拓扑排序(如果需要)，每当变量发生变化时:

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

很容易看出，根据这种方法，每个变量最多计算一次。