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

From: Matt Hurd (matthurd_at_[hidden])
Date: 2007-02-01 01:55:15

> On 01/02/07, james.jones_at_[hidden] <james.jones_at_[hidden]> wrote:
> From: Matthias Troyer <troyer_at_[hidden]>

<snip>

> 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.

You can get improvement to an on-line median by have storing some of
the central state.  If the distribution is kind and you get lucky you
can avoid a lot of checking of previous values giving nice
improvements.

Similar stuff works for min/max, quartiles and pecentiles.

For windowed esimates you need to account for values falling off and
those coming in but the same works.

Done wisely you can get an order of magnitude improvement for appropriate data.

$AUD 0.0002

Matt.