13,353,124 members (54,721 online)
alternative version

#### Stats

287.2K views
77 bookmarked
Posted 4 Mar 2007

# A Simple Moving Average Algorithm

, 4 Mar 2007
 Rate this:
A simple moving average algorithm.

## Introduction

I needed a running average to monitor CPU utilization and ended writing a small class for doing the calculation. In writing the code, I realized that even something as simple as a running average algorithm requires some thought to writing it well. So I have written this article for beginners, to illustrate how even simple algorithms need some thought.

## What Is A Running Average?

A running average (also called a moving average) can be implemented in different ways. For an in-depth description, refer to wikipedia.

### Simply Moving Average

A simple moving average is the unweighted mean (the sum of all items in a list divided by the number of items in the list) of the previous n data points. This is the easiest running average to implement and is the one I'm illustrating in this article.

### Weighted Moving Average

A weighted moving average is an average in which the data points in the list are given different multiplying factors. This has the affect of making some items in the list more important (given more weight) than others. For example, you may wish to have older values to have more weight than newer ones, or vice-versa.

## Brute Force Implementation

A simple moving average takes the sample values and divides them by the sample count. A basic implementation might look something like this:

```using System;
using System.Collections.Generic;
using System.Text;

namespace AveragerTest
{
public class BruteForce
{
protected float[] samples;
protected int idx;

public float Average
{
get
{
float total=0;

for (int i=0; i<samples.Length; i++)
{
total+=samples[i];
}

}
}

public BruteForce(int numSamples)
{
if (numSamples <= 0)
{
throw new ArgumentOutOfRangeException(
"numSamples can't be negative or 0.");
}

samples = new float[numSamples];
idx = 0;
}

public void AddSample(float val)
{
samples[idx] = val;

if (++idx == samples.Length)
{
idx = 0;
}
}
}
}```

In fact, this reminds me a lot of an algorithm I wrote when I was first starting programming in Commodore BASIC! There are several problems with this algorithm:

• Until the sample array is completely loaded, the `Average `calculation includes unloaded (and zero) sample values. This results in the wrong average
• The algorithm is very inefficient for large sample sizes, having to total the samples every time the average is taken
• The algorithm implements a circular list. Wouldn't it be nice to extract the implementation of the circular list from the implementation of the running average algorithm?
• There is no good way to replace the simple running average with, say, a weighted running average, because the class does not implement an interface that promotes use-case flexibility.

## A Better Implementation

### Separating Out The Collection and Iteration Logic

The first step, in my opinion, would be to separate out the iteration logic. We have to be careful here because the circular list that we need isn't just an iterator--we actually have to set the values in the list as well. An iterator does not allow this. From MSDN:

An enumerator remains valid as long as the collection remains unchanged. If changes are made to the collection, such as adding, modifying, or deleting elements, the enumerator is irrecoverably invalidated and the next call to MoveNext or Reset throws an InvalidOperationException.

Changing the management of the sample list to a circular list eliminates two problems:

• The list management is decoupled from the algorithm
• We can use the `Count `method of the circular list to obtain the count of loaded items, not just the total number of items in the list

In addition, it leverages code re-use and helps debugging--we can isolate testing of the circular list from problems in the running average class. In other words, it would be easy to write unit tests for the circular list, validate its operation, then write unit tests to verify that the averager is working correctly.

The new code looks like this:

```using System;
using System.Collections.Generic;
using System.Text;

using Clifton.Collections.Generic;

namespace AveragerTest
{
public class BruteForce
{
CircularList<float> samples;

public float Average
{
get
{
float total=0;

foreach(float v in samples)
{
total+=v;
}

}
}

public BruteForce(int numSamples)
{
if (numSamples <= 0)
{
throw new ArgumentOutOfRangeException(
"numSamples can't be negative or 0.");
}

samples = new CircularList<float>(numSamples);
}

public void AddSample(float val)
{
samples.Value = val;
samples.Next();
}
}
}```

This is a much cleaner implementation already!

### Performance

The next issue is performance. For a large sample size, we don't want to be iterating over the entire sample to get the total. It would make more sense to manage a running total. This requires a little bit of logic when adding a sample value, to determine whether a sample already exists so that it can be subtracted from the total:

```public void AddSample(float val)
{
if (samples.Count == samples.Length)
{
total -= samples.Value;
}

samples.Value = val;
total += val;
samples.Next();
}```

and the `Average `getter no longer needs to sum up all the samples:

```public float Average
{
}```

#### But Is It Really Better Performance?

That's always the question, and it depends on usage! Arguably, the first method might be better performing if ratio of samples being added to the number of times the average is taken is very high. For example, you might be adding a million samples between taking average, and the sample size might only be a hundred items. In this scenario, the overhead of keeping the total current probably far outweighs the overhead of calculating the total on the fly.

So, the right answer regarding performance is to select the algorithm that works well for your requirements. The algorithm I describe above is what I consider to be a typical case, where the average is taken after every new sample, and in this case, it does make sense to use a running total, especially if the sample size is large.

### Improving Usability

Usability can be improved by providing an interface that the programmer can use rather than the class directly. By using an interface, the programmer can create the correct moving average algorithm without the code needing to know which (simple or weighted) was actually constructed. Some other part of the application can make this decision.

```public interface IMovingAverage
{
float Average { get;}

void ClearSamples();
void InitializeSamples(float val);
}```

## Comments, Error Checking, And Bells And Whistles

The final implementation, with some additional error checking and the ability to clear the average or pre-load the samples with a particular value, looks like this:

```using System;

using Clifton.Collections.Generic;

namespace Clifton.Tools.Data
{
public class SimpleMovingAverage : IMovingAverage
{
CircularList<float> samples;
protected float total;

/// <summary>
/// Get the average for the current number of samples.
/// </summary>
public float Average
{
get
{
if (samples.Count == 0)
{
throw new ApplicationException("Number of samples is 0.");
}

}
}

/// <summary>
/// Constructor, initializing the sample size to the specified number.
/// </summary>
public SimpleMovingAverage(int numSamples)
{
if (numSamples <= 0)
{
throw new ArgumentOutOfRangeException(
"numSamples can't be negative or 0.");
}

samples = new CircularList<float>(numSamples);
total = 0;
}

/// <summary>
/// Adds a sample to the sample collection.
/// </summary>
public void AddSample(float val)
{
if (samples.Count == samples.Length)
{
total -= samples.Value;
}

samples.Value = val;
total += val;
samples.Next();
}

/// <summary>
/// Clears all samples to 0.
/// </summary>
public void ClearSamples()
{
total = 0;
samples.Clear();
}

/// <summary>
/// Initializes all samples to the specified value.
/// </summary>
public void InitializeSamples(float v)
{
samples.SetAll(v);
total = v * samples.Length;
}
}
}```

## Usage

A simple program demonstrating the usage of the `SimpleMovingAverage `class is:

```using System;

using Clifton.Collections.Generic;
using Clifton.Tools.Data;

namespace AveragerTest
{
class Program
{
static void Main(string[] args)
{
IMovingAverage avg = new SimpleMovingAverage(10);
Test(avg);
}

static void Test(IMovingAverage avg)
{
for (int i = 0; i < 20; i++)
{
Console.WriteLine(avg.Average);
}
}
}
}```

Note how the sample size is 10 items but there are 20 samples added to the moving average. The old samples are replaced as new samples are added. As the code illustrates, a `SimpleMovingAverage `instance is constructed and used to initialize the variable avg, whose type is `IMovingAverage`. The `Test `method takes the interface for a parameter. If we implemented, say, a `WeightedMovingAverage `class, we could change the construction to:

`IMovingAverage avg = new WeightedMovingAverage(10);`

and call the exact same `Test `routine to see how the new moving average works. By using the interface, we promote the usability of the code.

## All This Work!

Admittedly, this is a lot of work for a simple algorithm. Personally, I try to follow the principle of doing the job right, even if it's a small job, because small jobs quickly turn into large jobs. The old excuse "we don't have the time and the budget", or "it's simple, just bang it out and we'll refactor it later" has proven time and time again to be lies. It does not save time and money to do it wrong first! Refactoring is rarely put into the "new" budget. Bad practices continue on unless they are changed from the beginning. The only reason to hack out an algorithm is for a prototype, so you can learn from it and develop the production algorithm correctly.

## About the Author

 United States
Marc is the creator of two open source projects, MyXaml, a declarative (XML) instantiation engine and the Advanced Unit Testing framework, and Interacx, a commercial n-tier RAD application suite.  Visit his website, www.marcclifton.com, where you will find many of his articles and his blog.

Marc lives in Philmont, NY.

## Comments and Discussions

 First PrevNext
 Moving average without the history.... adam fullerton13-Apr-15 4:47 adam fullerton 13-Apr-15 4:47
 real time moving avarage alijahan14-Jul-14 11:49 alijahan 14-Jul-14 11:49
 Re: real time moving avarage CatchExAs14-Jul-14 12:57 CatchExAs 14-Jul-14 12:57
 Re: real time moving avarage alijahan16-Jul-14 6:01 alijahan 16-Jul-14 6:01
 Love it! Nicolas Hoppe6-Jul-14 4:32 Nicolas Hoppe 6-Jul-14 4:32
 Easy Moving Average penguinman5735-Dec-13 13:32 penguinman573 5-Dec-13 13:32
 Re: Easy Moving Average Marc Clifton5-Dec-13 15:07 Marc Clifton 5-Dec-13 15:07
 Very simple alternative Member 83831321-Oct-13 11:14 Member 8383132 1-Oct-13 11:14
 Re: Very simple alternative UserMarcus11-Feb-14 3:58 UserMarcus 11-Feb-14 3:58
 Good job mwpowellhtx7-Sep-13 16:46 mwpowellhtx 7-Sep-13 16:46
 My vote of 5 Ruifeng Zhang3-Sep-12 0:04 Ruifeng Zhang 3-Sep-12 0:04
 My vote of 5 manoj kumar choubey2-Mar-12 23:47 manoj kumar choubey 2-Mar-12 23:47
 CircularList.Drop respirator1-Apr-11 14:12 respirator 1-Apr-11 14:12
 Taking min and max values curlyfur2-Aug-10 19:13 curlyfur 2-Aug-10 19:13
 Re: Taking min and max values Marc Clifton3-Aug-10 1:42 Marc Clifton 3-Aug-10 1:42
 Re: Taking min and max values curlyfur3-Aug-10 2:31 curlyfur 3-Aug-10 2:31
 Re: Taking min and max values Marc Clifton3-Aug-10 3:42 Marc Clifton 3-Aug-10 3:42
 curlyfur wrote:I can't see how I can just pop a value without finding what the next largest or smallest one is, given a 5 min or 10 min sampling. And that get me back to iterating the whole thing. If you sort your structure, the max would be at the end of the list and the min at the beginning. If you want min/max of both heartrate and SpO2, then you'd need two buffers. Marc
 Re: Taking min and max values curlyfur3-Aug-10 4:37 curlyfur 3-Aug-10 4:37
 Can you help me with implementation?? cjsteury22-May-10 11:36 cjsteury 22-May-10 11:36
 Simple Moving Average in O(1) cheind22-Jan-10 23:20 cheind 22-Jan-10 23:20
 Keeping in mind that my math skills are poor... PIEBALDconsult29-Oct-08 11:23 PIEBALDconsult 29-Oct-08 11:23
 Re: Keeping in mind that my math skills are poor... pwasser9-Feb-09 13:35 pwasser 9-Feb-09 13:35
 Re: Keeping in mind that my math skills are poor... PIEBALDconsult9-Feb-09 13:47 PIEBALDconsult 9-Feb-09 13:47
 Re: Keeping in mind that my math skills are poor... pwasser9-Feb-09 14:09 pwasser 9-Feb-09 14:09
 Re: Keeping in mind that my math skills are poor... PIEBALDconsult10-Feb-09 4:41 PIEBALDconsult 10-Feb-09 4:41
 Last Visit: 31-Dec-99 19:00     Last Update: 21-Jan-18 11:40 Refresh 12 Next »

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.