7.11

The tree-evaluation algorithm can be turned into an O(n+m) procedure for a DAG simply by memoising the value of every node the first time it is computed.

Idea: perform a depth-first traversal from the (one or several) output node(s); before the recursive calls, check whether the node has already been evaluated. Thanks to the cache, each node and each edge is touched at most once.

value[v] ← undefined // cache Eval(v): if value[v] ≠ undefined: return value[v] // already done if v is a leaf: // integer constant value[v] ← label(v) else: // internal node children ← (v₁,v₂,…) x₁,…,x_k ← Eval(v₁),…,Eval(v_k) value[v] ← apply(label(v), x₁,…,x_k) // +,−,*,/ return value[v]

To evaluate the whole expression, call Eval(r) for every root r that represents an output of the DAG.

Correctness: because the graph is acyclic, the recursion reaches a leaf after a finite number of steps; caching guarantees that the value of a shared subexpression is computed once and then reused, so every operator receives already-computed operand values.

Complexity: each of the n nodes is evaluated exactly once and each of the m edges is traversed once during the first (and only) call to its child, yielding total time Θ(n+m) and Θ(n) extra space for the cache.

Back to Chapter 7