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