algorithm - 性能算法 - 排序 - 树(数据结构)唯一的解决方案？

Question

我手头有一个问题，乍一看它看起来很简单，但我正在寻找其他解决方案(也许更简单的解决方案):

表达式:

V0
V1
V2
V3
V4
SumA = V1 + V2
SumB = SumA + V3
SumC = SumB + SumA
SumD = SumC + V0

正如我们在这里看到的，“基本”变量是 V0、V1、V2、V3 和 V4(它们中的每一个的值都是从数据库查询返回的)

用户要求软件返回V1和SumC的结果。

我知道的解决方法:

找到所有必要的变量:V1、SumC、SumB、SumA、V3、V2

为了性能，我只想处理每个变量的数学运算一次。

这意味着我需要将表达式从“基本表达式”排序到“顶级变量”。

此时我只看到“树(数据结构)”类型的解决方案 > 获取 V1、V2 和 V3然后得到SumA，然后得到SumB，最后才得到SumC。

还有其他方法可以解决这个问题吗？

该算法的最终目标是使用更复杂的变量和几个“中间变量”。因此，性能至关重要，我不能对相同的数学运算进行超过 1 次。

Answer 1

我不确定我是否完全理解 - 但我认为您指的是 common subexpression elimination , [或类似的东西] 这是一个很常见的 compiler optimization .

进行这种优化的一种常见方法是使用图表 [实际上是 DAG ] 程序中的表达式，并迭代添加新表达式。 DAG 中的“来源”都是初始变量 [示例中的 V0、V1、V2、V3、V4]。如果您已经计算过，您可以“知道”哪个表达式是多余的 - 并避免重新计算它。

These lecture notes似乎是一个体面的更详细的解释[虽然我承认我没有读完]