Re: [Boost-users] [Accumulators] Evaluation of Expression Tree

Subject: Re: [Boost-users] [Accumulators] Evaluation of Expression Tree
From: Eric Niebler (eric_at_[hidden])
Date: 2010-01-02 17:27:16

On 1/2/2010 7:55 PM, Horst S wrote:
> Hello!
>
> Given an expression tree over mathematical expressions like 'sum',
> 'min', 'product', etc. and
> a fixed number of variables X1..Xn like the following, would it be
> possible to use BOOST Accumulators
> to re-evaluate the root evaluation function based on changes in the
> values of the variables efficiently?
>
>        sum
>        /  \
>       /    \
>     min    product
>     /  \  /   |   \
>    X1   X2   X3   X4
>
> Note that variables appear only as leaf nodes.
>
> Obviously, one can flatten the tree to the following expression:
>
> RootValue = sum( min(X1,X2), product(X2,X3,X4) )
>
> Assuming that the current values of the variables are
>
> X1=3, X2=4, X3=2, X4=2
>
> then RootValue evaluates to 19.
> Now setting X2=2 results in 10.
>
>
> The main objective is to minimize the cost of computing the value of
> the root evaluation function
> when changing the value of a subset of variables in X1..Xn.
> One can assume that the subset of variables that changes each time is
> rather small (typically only one)
> and the size of the expression tree is rather large.
>
> Are BOOST Accumulators a suitable way to model such kind of expressions and the
> corresponding incremental evaluation?

I don't think Boost.Accumulators would be of much help here. It is for 
computing the statistical properties of a set of samples. That doesn't 
describe your problem.

For custom evaluation of expression trees Boost has Proto, a library for 
building and evaluating expression templates. But finding common 
sub-expressions and knowing what to reevaluate when a certain variable 
changes is going to be quite challenging.

-- 
Eric Niebler
BoostPro Computing
http://www.boostpro.com