13,197,796 members (44,796 online)
alternative version

#### Stats

278.9K 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;
}

{
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);
}

{
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>
{
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.

## Share

 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.

## You may also be interested in...

 First Prev Next
 Moving average without the history.... adam fullerton13-Apr-15 3:47 adam fullerton 13-Apr-15 3:47
 real time moving avarage alijahan14-Jul-14 10:49 alijahan 14-Jul-14 10:49
 Re: real time moving avarage CatchExAs14-Jul-14 11:57 CatchExAs 14-Jul-14 11:57
 Re: real time moving avarage alijahan16-Jul-14 5:01 alijahan 16-Jul-14 5:01
 Love it! Nicolas Hoppe6-Jul-14 3:32 Nicolas Hoppe 6-Jul-14 3:32
 Easy Moving Average penguinman5735-Dec-13 12:32 penguinman573 5-Dec-13 12:32
 Re: Easy Moving Average Marc Clifton5-Dec-13 14:07 Marc Clifton 5-Dec-13 14:07
 Very simple alternative Member 83831321-Oct-13 10:14 Member 8383132 1-Oct-13 10:14
 Re: Very simple alternative UserMarcus11-Feb-14 2:58 UserMarcus 11-Feb-14 2:58
 Good job mwpowellhtx7-Sep-13 15:46 mwpowellhtx 7-Sep-13 15:46
 My vote of 5 Ruifeng Zhang2-Sep-12 23:04 Ruifeng Zhang 2-Sep-12 23:04
 My vote of 5 manoj kumar choubey2-Mar-12 22:47 manoj kumar choubey 2-Mar-12 22:47
 Nice
 CircularList.Drop respirator1-Apr-11 13:12 respirator 1-Apr-11 13:12
 Taking min and max values curlyfur2-Aug-10 18:13 curlyfur 2-Aug-10 18:13
 Re: Taking min and max values Marc Clifton3-Aug-10 0:42 Marc Clifton 3-Aug-10 0:42
 Re: Taking min and max values curlyfur3-Aug-10 1:31 curlyfur 3-Aug-10 1:31
 Re: Taking min and max values Marc Clifton3-Aug-10 2:42 Marc Clifton 3-Aug-10 2:42
 Re: Taking min and max values curlyfur3-Aug-10 3:37 curlyfur 3-Aug-10 3:37
 Can you help me with implementation?? cjsteury22-May-10 10:36 cjsteury 22-May-10 10:36
 Simple Moving Average in O(1) cheind22-Jan-10 22:20 cheind 22-Jan-10 22:20
 Keeping in mind that my math skills are poor... PIEBALDconsult29-Oct-08 10:23 PIEBALDconsult 29-Oct-08 10:23
 Re: Keeping in mind that my math skills are poor... pwasser9-Feb-09 12:35 pwasser 9-Feb-09 12:35
 Re: Keeping in mind that my math skills are poor... PIEBALDconsult9-Feb-09 12:47 PIEBALDconsult 9-Feb-09 12:47
 Re: Keeping in mind that my math skills are poor... pwasser9-Feb-09 13:09 pwasser 9-Feb-09 13:09
 Re: Keeping in mind that my math skills are poor... PIEBALDconsult10-Feb-09 3:41 PIEBALDconsult 10-Feb-09 3:41
 Re: This might be simpler Marc Clifton25-Mar-07 13:58 Marc Clifton 25-Mar-07 13:58
 Re: This might be simpler [modified] siana8-Nov-07 20:55 siana 8-Nov-07 20:55
 Re: This might be simpler pwasser8-Jan-08 15:25 pwasser 8-Jan-08 15:25
 Re: This might be simpler Marc Clifton10-Oct-11 0:37 Marc Clifton 10-Oct-11 0:37
 One more possible edge case... PhallGuy12-Mar-07 7:03 PhallGuy 12-Mar-07 7:03
 Re: One more possible edge case... Marc Clifton12-Mar-07 7:09 Marc Clifton 12-Mar-07 7:09
 Re: One more possible edge case... Leslie Sanford15-Mar-07 16:59 Leslie Sanford 15-Mar-07 16:59
 Excellent Jomit Vaghela6-Mar-07 20:00 Jomit Vaghela 6-Mar-07 20:00
 Thank You Mike DiRenzo5-Mar-07 15:26 Mike DiRenzo 5-Mar-07 15:26
 ewma gobgob5-Mar-07 4:30 gobgob 5-Mar-07 4:30
 Re: ewma Marc Clifton5-Mar-07 4:47 Marc Clifton 5-Mar-07 4:47
 Re: ewma pwasser5-Mar-07 12:21 pwasser 5-Mar-07 12:21
 You've been busy Colin Angus Mackay4-Mar-07 11:37 Colin Angus Mackay 4-Mar-07 11:37
 Re: You've been busy Marc Clifton4-Mar-07 13:25 Marc Clifton 4-Mar-07 13:25
 Re: You've been busy JeffPClark8-Mar-07 0:07 JeffPClark 8-Mar-07 0:07
 Last Visit: 31-Dec-99 18:00     Last Update: 21-Oct-17 4:27 Refresh 1