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