I thought I'd share a simple moving average template class. I got this idea while at work yesterday when talking to an electrical engineer about making a writing efficient average function. Afterward I continued to think about ways to continue to improve upon the idea.
A mean average is simply the sum of all the data divided by the number of data points. A moving average assumes a fixed number of data points. When new data is added, the oldest sample is lost replaced with the new data added. So the mean average reflects the average over the most recent data only. This functions like a low-pass filter and is often used as an easy way to clean up analog signals.
What if the moving average was over a huge number of samples, and the type of samples was some kind of object with computationally difficult math operations? Perhaps the moving average is being preformed on a long list of arbitrary-precision data points. Adding up all the data points and dividing by the number of points could take too long.
We can speed the process of taking the average by keeping a sum. When a new point is added, the oldest data point is subtracted from the sum, and the new data added. In this way the only math operation needed to take the average at any time is dividing by the number of samples.
In making an average class I also considered how to resize the moving average. If the average becomes larger, empty data is simply placed at the end. If it becomes smaller, only the most recent samples need to be saved.
Here is a C++ implementation:
//==============================================================================
// Template class for keeping a moving average.
// Assumes math operations on 'TYPE' are computationally expensive, so used
// sparingly.
//==============================================================================
template< class TYPE >
class Average
{
protected:
// Storage of all the data points that make the average.
TYPE * array;
// A representation of zero in the type of this template.
TYPE zero;
// Index into 'array' to save next data point.
unsigned currentIndex;
// How many data points are currently in array.
unsigned top;
// Length of 'array'.
unsigned length;
// Running sum used to compute average.
TYPE sum;
public:
//------------------------------------------------------------------------
// Create moving average with 'lengthParameter' number of samples to be
// averaged together.
//------------------------------------------------------------------------
Average( unsigned lengthParameter )
{
length = lengthParameter;
// Allocate storage for
array = new TYPE[ length ];
// We need a definition of zero, so make a cast to get this.
// NOTE: This is important if TYPE is truly a class.
zero = static_cast< TYPE >( 0 );
reset();
}
//------------------------------------------------------------------------
// Reset all data in average.
// NOTE: Average result will be the equivalent of zero.
//------------------------------------------------------------------------
void reset()
{
// Empty array.
for ( currentIndex = 0; currentIndex < length; ++currentIndex )
array[ currentIndex ] = zero;
currentIndex = 0;
top = 0;
sum = 0;
}
//------------------------------------------------------------------------
// Resize the number of samples used in average.
// If the size becomes larger, then the average will not change until
// more data is added.
// If the size becomes smaller, then the last 'newLength' samples will be
// copied to new average.
//------------------------------------------------------------------------
void resize( unsigned newLength )
{
// Allocate memory for new array.
TYPE * newArray = new TYPE[ newLength ];
// Reset sum.
sum = zero;
for ( unsigned count = newLength; count > 0; --count )
{
unsigned index = count - 1;
// Do we have data to copy from the old array at this index?
if ( index < top )
{
// Get previous data index.
if ( currentIndex == 0 )
currentIndex = length - 1;
else
currentIndex -= 1;
// Save data in new array.
newArray[ index ] = array[ currentIndex ];
// Sum this data.
sum += newArray[ index ];
}
else
// Set this position to zero.
newArray[ index ] = zero;
}
// Delete old array holder and switch to new array.
delete array;
array = newArray;
// Move top if the new length is lower than previous top.
if ( top > newLength )
top = newLength;
// New length.
length = newLength;
// Set new index location.
currentIndex = top;
if ( currentIndex >= length )
currentIndex = 0;
}
//------------------------------------------------------------------------
// Return the computed average.
// NOTE: Uses the data in the average thus far. If average isn't full,
// then only those data points in the array are used.
//------------------------------------------------------------------------
TYPE get() const
{
TYPE result;
if ( top > 0 )
result = sum / static_cast< TYPE >( top );
else
result = zero;
return result;
}
//------------------------------------------------------------------------
// Return the number of data points in the moving average so far.
//------------------------------------------------------------------------
unsigned getNumberOfDataPoints() const
{
return top;
}
//------------------------------------------------------------------------
// Add new data to average.
//------------------------------------------------------------------------
void push( TYPE newData )
{
// Remove old data from average sum.
sum -= array[ currentIndex ];
// Add new data to average sum.
sum += newData;
// Save new data.
array[ currentIndex ] = newData;
// Advance index.
++currentIndex;
// If this marks the top...
if ( currentIndex > top )
// Update the top.
top = currentIndex;
// Wrap-around index.
if ( currentIndex >= length )
currentIndex = 0;
}
};
Download the code
Use it like this:
Average< int > average( 5 );
average.push( 1 );
average.push( 2 );
average.push( 3 );
int meanAverage = average.get();
This code will create a rolling average of up to 5 elements. It then adds the data [1, 2, 3] to the average. 'meanAverage' will be 2.
