Simple Moving Average

Sliding Window

In statistics a simple moving average is an algorithm that calculates the unweighted mean of the last n samples. The parameter n is often called the window size, because the algorithm can be thought of as an window that slides over the data points.

By using a recursive formulation of the algorithm, the number of operations required per sample is reduced to one addition, one subtraction and one division. Since the formulation is independent of the window size n, the runtime complexity is O(1), i.e. constant.

The recursive formula of the unweighted moving average is , where avg is the rolling average and x represents a data point. So, whenever the window slides to the right, one data point, the tail, drops out and one data point, the head, moves in.

Implementation

An implementation of the simple moving average has to take the following into account

• Algorithm initialization As long as the window is not fully populated with values, the recursive formula fails.
• Storage Access to the tail element is required, which depending on the implementation requires a storage of n elements.

My implementation uses the presented formula when the window is totally populated with values, and otherwise switches to the formula , which updates the mean by recalculating the sum of the previous elements. Note that this can lead to numerical instabilities because of floating point arithmetic.

As far as memory consumption is concerned, the implementation uses iterators to keep track of head and tail elements. This leads to an implementation with constant memory requirements independent of the window size. Here is the update procedure that slides the window to the right.

// _head and _next are enumerators of the data points collection
// _count is the number of elements in the window (at max _n)
// _running is the moving average initialized with zero.

public void Shift() {
  if (!_head.MoveNext())
    throw new InvalidOperationException("Cannot move to next element");
  double next = _head.Current;
  
  if (_count < _n) {
    // Window not filled
    _count++;
    _running = (_running * (_count - 1) + next) / _count;
  } else {
    _tail.MoveNext();
    double drop= (double)_tail.Current;
    _running = _running + (next - drop) / _n;
  }
}

In .NET most of the collections invalidate their enumerators when the underlying collection is modified. The implementation, however, relies on valid enumerators. Especially in streaming based applications the underlying collection needs modified when a new element arrives. One way to deal with that is to create a simple circular fixed size collection of size n+1 that never invalidates its iterators and alternately add an element and call Shift.