Incremental window average

Question

I am trying to calculate a windowed average where the newest value replaces the oldest value in a set of size 10. In this case, I have a real-time number stream and have access to current value, current average and the previous value.

Is there any way to calculate this value incrementally storing minimal amount of historical state? I have tried formulas in this question but they don't seem to be suitable for window situation

Answer 1

To do this you need to store all values currently in the window. This is best done using a double-linked list. So for each new value you append the value to the list and pop of the first (oldest) number in the list. Then you can subtract oldest/10 and add new/10 to the average value.

So the algorithm is (for maximal window size $\lambda$):

1. Initialize an empty List $L$, $\mathrm{avg} = 0$, $l = 0$
2. Get a new value $n$
3. If $l < \lambda$ set $\mathrm{avg} = (\mathrm{avg}\cdot l + n)/(l+1)$, $l=l+1$, and append $n$ to $L$
4. If $l = \lambda$ append $n$ to $L$ and pop the first element $o$ of $L$. Set $\mathrm{avg} = \mathrm{avg} + (n - o)/\lambda$
5. Jump to 2