Re: [boost] [Review] Review of the Accumulators library begins today Jan 29

From: Hans Meine (meine_at_[hidden])
Date: 2007-01-31 10:38:49

Hi!

On Wednesday, 31. January 2007 16:19, Ben FrantzDale wrote:
> > Isn't this already a problem with sequences? Suppose you're storing the
> > current median, and a new value comes along. What's the new median -
> > without checking all the previous values? There are statistical estimates
> > for this, but I don't know any exact way other than essentially resorting
> > the data and checking the new median.
>
> Good point. Combining partial results may not be possible for all
> accumulated statistics or there may be a cost to making a statistic
> "combinable". Perhaps a refinement of the Accumulator concept would be
> needed.
>
> The idea of the Accumulator library is to implement online algorithms; is
> there a corresponding word for online algorithms for which partial results
> can be combined?

Actually, I don't see any "online algorithms" whose partial results cannot be 
combined.

IIUC, what James pointed out is exactly that the median is not an online 
algorithm.  AFAICS, the "partial result" (in terms of inner representation) 
of a median accumulator consists of the (possibly sorted) complete input seen 
so far.  (I would love to be corrected, but I cannot imagine a solution.)

IMO, combining accumulators should be an integral part of the accumulators 
library.

On Wednesday, 31. January 2007 08:03, Matthias Troyer wrote:
> Yes, this is definitely needed but I think it will be lots of work to  
> add it, based on my own experience in implementing something like  
> this in our ALPS library for parallel Monte Carlo simulations. I am  
> planning to think about this sometime this year, but believe it is a  
> substantial extension to the library and will not be easy to design  
> right.

Is it really such a "substantial extension"?  I fully agree with John here:

On Wednesday, 31. January 2007 10:23, John Maddock wrote:
> But can't we make this a conceptual requirement that if
> you try and combine two accumulator sets, then each accumulator must have a
> "combine" method (otherwise you get a compile time error).  The "combine"
> methods for min/max/sum/count etc are all trivial aren't they - and could
> be added fairly easily ?

Which accumulators would then have a non-trivial "combine" method?

Greetings,
  Hans