rolling min and rolling max for C++ boost?

Question

I have some code that uses a Boost accumulator to track a mean across a rolling window -- "rolling mean". In addition to the rolling mean, I would like to track the minimum and maximum across this same rolling window.

Is there a way to compute a rolling min and rolling max with a Boost accumulator? I am not seeing a way...

I have tried adding min and max tags to the accumulator used for rolling_mean, but that does not give me what I want.

typedef accumulator_set<uint32_t, stats<tag::rolling_mean> > rollingMeanAcc_t;

becomes

typedef accumulator_set<uint32_t, stats<tag::rolling_mean,tag::min,tag::max> > rollingMeanAcc_t;

However, the min and max provided here are calculated over the entire accumulator, rather than limited to the same rolling window as the mean.

The Boost documentation says that min and max are computed across all samples, not limited to a rolling window. They do not appear to provide a way to restrict or weight the samples.

I would like to be able to report mean/min/max all across a rolling window.

I am currently using Boost version 1.48.0. I have looked at the documentation for the latest version (1.54.0) and do not see a rolling min/max implemented there.

I have found a non-Boost way to track a sliding window minimum, but this does not appear to be what I want either. I don't want to remove values just because they are greater/less than the previous min/max, as that would make the rolling_mean inaccurate.

Answer 1

I don't think an accumulator can do a rolling min/max.

The problem is pretty simple: an accumulator pretty much by definition uses only O(1) data -- it doesn't store the data being processed. It can maintain a min or max with O(1) data, because it simply changes the current min/max when a number falls outside the range of the current min/max.

For a window, however, it needs to be prepared to do the opposite: when the current min goes out of the window, it needs to find the new minimum -- the next smallest number in the window. Likewise for maximum, of course.

Now, consider what happens to the minimum if (for example) the input is sorted. Every time an item is removed from the window, we get a different minimum value. In other words, the accumulator would need to store all the data in the window to maintain the current minimum properly. Likewise, for maximum with input sorted in descending order.

In short, you can't use an accumulator for this. You need to store all the data in the window.

Answer 2

There might be a more clever algorithm (in fact there probably is), but off the top of my head, I would simply store the window in a circular buffer and calculate the rolling min/max on-demand. Cache the result and set a dirty flag when the window changes. That gives an O(1) accumulate operation and an amortized O(1) extract operation with a worst case of O(K), where K is the size of the window.