我正在研究为对应于大型数学表达式（数百万个节点）的表达式图实施公共子表达式消除（CSE）。
哪些算法适合执行此操作？我在互联网上搜索一个易于实现的算法，但我找不到任何东西。如果可能，算法应该在完整表达式图的节点数上具有线性复杂度。
问问题
4524 次
1 回答
10
这些是没有副作用的表达方式？然后最简单的做法是将每个子表达式的树散列到桶中，以确定子表达式消除的候选者。这是CSE的一个特例，其中所有表达式都在一个（巨大的）“基本块”中。（我以此思路作为检测重复代码的基础。）
如果表达式具有顺序和副作用，您可能需要考虑Value Numbering。
于 2012-07-04T10:50:33.023 回答