Time Moving Average

• Download source code - 114.2 KB
• Download demo - 9.5 KB

Introduction

I needed a sophisticated counter in my project. A counter which could show the quantity of events (incoming messages) for the last period of time (say, a minute). Due to this counter and with the help of periodic logging, I could understand when the remote system became passive and whether it just stopped working.

While I was solving this problem, I read Marc Clifton's article about Simple Moving average calculation. This is when it became obvious that my counter is a subtask of a more complicated task: counting of Moving average with respect to time. In this article, Marc Clifton's IMovingAverage interface, a bit extended, is used.

The term Time-Moving Average was invented by me. If someone knows the name of this concept, please correct me.

Background

I strongly recommend taking a look at Marc Clifton's article about Simple Moving average calculation. Some tricks are used here and are not explained, because they are covered in Marc's article.

One More Explanation of Moving Average

To get rid of abstract entities, let's consider a real-world example: you've got a web site presenting some kind of goods, and you need to know the average income. In this example, we have an event - buying a product. This event has a value - the price of the purchased product. How should we count the average income?

The simplest approach is to divide the total money ever paid on the total purchases quantity. Well, this gives you some information - an average sold products price in your shop. This might then be used in calculations for future incomes. But we won't stop here, and will move further.

Next, you think: I need something not so global: I need the average price of the last 100 sold products. This gives nice numbers in analyzing consumer needs or whatever. So you come to Simple Moving Average. To illustrate how this works, consider the following picture. On the given chart, we have five purchases, and we're always interested in the last three items.

When the 3^rd second came, I fix step 1 - when 3 items are already available for the first time. Next, on the 4^th second, an item for 4$ dollars was sold (step 2), but the #1 item for 6$ is not interesting to us any more. Then, on the 8^th second, the item for 3$ was purchased (step 3) but item #2 is not interesting to us any more. Note, that if we ask for Average value on 5^th, 6^th, 7^th seconds - it'll remain the same.

This is how Simple moving average works, and we've got another number (index) which shows some trends in our business. I hope, you've notice one point in the example: what if the last item was bought not 3 seconds later, but 3 days later? Should we consider the purchases made 3 days ago? What if we need monitoring average purchase amount only for last 20 minutes? This is where we come to Time-Moving Average concept.

Time-Moving Average

Now let's examine what is meant by the term Time-Moving average. Again, we shall see the same illustration, however, with some changes in our point of interest: we are not interested in last N events average, but we're interested in events average happened during last N seconds. In other words, all the purchases, that happened in last time interval t (3 seconds on the picture example) can take part in counting the average.

Time-Moving Average is good for our web shop example: we can monitor, the average purchase price for last, say, hour.

By the way, we also may need not only the average price during last hour, but also total money paid and purchases quantity during last hour.

Implementations

Well, we've got an idea, let's think of the ways in which we can implement it. First, the interface for all implementations will look like this:

public interface IMovingAverage
{
    /// <summary>
    /// Gets the moving average value
    /// </summary>
    float Average { get; }

    /// <summary>
    /// Gets the moving total value
    /// </summary>
    float MovingTotal { get; }

    /// <summary>
    /// Gets the moving count value
    /// </summary>
    int MovingCount { get; }

    /// <summary>
    /// Gets the whole sum of all samples.
    /// </summary>
    float Total { get; }

    /// <summary>
    /// Gets the total count of samples, that were ever added.
    /// </summary>
    long TotalCount { get; }

    /// <summary>
    /// Adds a sample into Moving average counting engine
    /// </summary>
    /// <param name="val"> A sample to add </param>
    void AddSample(float val);

    /// <summary>
    /// Clears the samples, making moving average equal to zero. 
    /// </summary>
    void ClearSamples();

    void InitializeSamples(float val);
}

Except moving average, why not give the user access to other numbers? First is a MovingTotal property, that gives the sum of all values for the TimeSpan passed. MovingCount property gives the count of events for TimeSpan interval. Total gives the sum of all values ever, and TotalCount gives the count of events ever happened.

The Precise Approach

The first strategy, that comes into mind is to fix the DateTime.Now for each value, that came into AddSample method. Then we need to decide when to check the collection of our "date-value" points for expiration. In other words, to see, which points can still take part in Time-Moving Average calculation. Two ways are possible: first - when one of the properties is read, second - to change repeatedly and frequently enough the tail of the events collection. I've chosen the second one.

public class PreciseTimeMovingAverage:IMovingAverage, IDisposable
{
    class DateTimeWrapper
    {
        public float Value { get; private set; }
        public DateTime EventTime { get; private set; }

        public DateTimeWrapper(float aValue)
        {
            Value = aValue;
            EventTime = DateTime.Now;
        }
    }

    private LinkedList<DateTimeWrapper> allSamples = new LinkedList<DateTimeWrapper>();
    private object samplesAccess = new object(); 
    private float movingTotal = 0;
    private int movingCounter = 0;

    private float total;
    private long totalCount;
    private Timer measurer;
    private TimeSpan interval;

    private void checkTime()
    {
        DateTime borderTime = DateTime.Now - interval;
        lock (samplesAccess)
        {
            while (allSamples.Count != 0 && allSamples.First.Value.EventTime < borderTime)
            {
                movingTotal -= allSamples.First.Value.Value;
                movingCounter -= 1;
                allSamples.RemoveFirst();
            }
        }
    }
    public PreciseTimeMovingAverage() : this(TimeSpan.FromMinutes(1.0)) { }

    public PreciseTimeMovingAverage(TimeSpan checkInterval)
    {
        interval = checkInterval;
        measurer = new Timer(200);
        measurer.Elapsed += new ElapsedEventHandler(measurer_Elapsed);
        measurer.Start();
    }

    void measurer_Elapsed(object sender, ElapsedEventArgs e)
    {
        checkTime();
    }

    #region IMovingAverage Members

    public float Average
    {
        get 
        {
            lock (samplesAccess)
            {
                if (allSamples.Count != 0)
                {
                    return movingTotal / movingCounter;
                }
                else return 0;
            }
        }
    }

    public void AddSample(float val)
    {
        lock (samplesAccess)
        {
            allSamples.AddLast(new DateTimeWrapper(val));
            movingCounter++;
            movingTotal += val;
            totalCount++;
            total += val;

        }
    }

    public int MovingCount
    {
        get { return movingCounter; }
    }

    public float MovingTotal
    {
        get { return movingTotal; }
    }

    public float Total { get { return total; } }

    public long TotalCount { get { return totalCount; } }

    public void ClearSamples()
    {
        lock(samplesAccess)
            allSamples.Clear();
    }

    public void InitializeSamples(float val)
    {
        lock(samplesAccess)
            allSamples.AddLast(new DateTimeWrapper(val));
    }

    #endregion

    public void Dispose()
    {
        measurer.Dispose();
    }
}

So, in this implementation, we've got a Timer object, which may change the collection, while AddSample also changes it. That's why we need locks inside the class. It should be also noted that the precise approach consumes most memory and CPU cycles. For the systems, which have hundred thousands events per minute, this approach may become too expensive.

The strategy we've got here is the most precise one. If we need to know average price for the last hour and make the request at 7:37 - then we'll get an average price of all purchased goods starting from 6:37. Do we always need such accuracy? The next approach will show a less precise and more simple approach.

The Rude Approach

The rude approach is opposite to the previous one. For this approach, we also have a Timer object, which raises Elapsed event when the needed Time-Moving average interval passed. Unlike in the previous approach, where the check was done each 200 ms.

public class RudeTimeMovingAverage:IMovingAverage,IDisposable
{
    TimeIntervalWrapper current = new TimeIntervalWrapper();
    TimeIntervalWrapper last = new TimeIntervalWrapper();
    float total = 0;
    long totalCount = 0;
    private object wrappersAccess = new object();

    private Timer aTimer;

    public RudeTimeMovingAverage(TimeSpan frequencyInterval)
    {
        aTimer = new Timer(frequencyInterval.TotalMilliseconds);
        aTimer.Elapsed += new ElapsedEventHandler(aTimer_Elapsed);
        aTimer.Start();
    }

    void aTimer_Elapsed(object sender, ElapsedEventArgs e)
    {
        lock (wrappersAccess)
        {
            last = current;
            current = new TimeIntervalWrapper();
        }
    }

    #region IMovingAverage Members

    public float Average { get { return last.Average; }}

    public float MovingTotal { get { return last.Total; } }

    public int MovingCount  { get { return last.Quantity; } }

    public float Total { get { return total; } }

    public long TotalCount { get { return totalCount; } }

    public void AddSample(float val)
    {
        lock (wrappersAccess)
        {
            total += val;
            totalCount++;
            current.AddSample(val);
        }
    }

    public void ClearSamples()
    {
        lock (wrappersAccess)
        {
            current.Clear();
            last.Clear();
        }
    }

    public void InitializeSamples(float val)
    {
        current.AddSample(val);
        last.AddSample(val);
    }

    #endregion

    public void Dispose()
    {
        aTimer.Dispose();
    }
}

This class and the class from the next approach use a helper class called TimeIntervalWrapper which allowed simplifying the code:

internal class TimeIntervalWrapper
{
    public DateTime EventTime { get; private set; }
    public float Total { get; private set; }
    public int Quantity { get; private set; }
    public float Average
    {
        get
        {
            if (Quantity == 0) return 0;
            return Total / Quantity;
        }
    }

    public TimeIntervalWrapper()
    {
        EventTime = DateTime.Now;
        Total = 0;
        Quantity = 0;
    }

    public void AddSample(float val)
    {
        Total += val;
        Quantity += 1;
    }

    public void Add(TimeIntervalWrapper toAdd)
    {
        Total += toAdd.Total;
        Quantity += toAdd.Quantity;
    }

    public void Remove(TimeIntervalWrapper toRemove)
    {
        Total -= toRemove.Total;
        Quantity -= toRemove.Quantity;
    }
    public void Clear()
    {
        Total = 0;
        Quantity = 0;
    }
}

The rude approach updates values only once in a needed time interval. For example: you asked for average at 7:37, while the last update happened at 7:00. So until 8 o'clock, you will see the same values that appeared at 7.

The word rude is a bit emotional, gives some negative feeling. But there's nothing bad about this class: you get the correct values and no data is lost.

Trade-Off Approach

As it's expected, this one gives an opportunity to get something that is between the rude and precise approaches. It divides the time interval into N equal parts, and manipulates these parts.

The average value is updated with period NeededTimeInterval/N. The approach is a bit more complicated than the two previous ones, but you gain memory and CPU economy, and the needed level of preciseness.

public class TradeOffTimeMovingAverage : IMovingAverage, IDisposable
{
    private readonly int partsCount = 20;    

    private LinkedList<TimeIntervalWrapper> timePieces = new LinkedList<TimeIntervalWrapper>();
    private TimeIntervalWrapper totalTillCurrent;
    private object pastAccess = new object();//an access to both timePieces 
                                             //and totalTillCurrent variables
    
    private TimeIntervalWrapper current;
    private object currentAccess = new object();

    private TimeSpan interval;
    private Timer measurer;

    private long totalCount = 0;
    private float total = 0;

    private TimeSpan onePartInterval;

    private void checkIntervals()
    {
        DateTime borderTime = DateTime.Now - interval;
        lock (pastAccess)
        {
            while (timePieces.Count !=0 && timePieces.First.Value.EventTime < borderTime)
            {
                totalTillCurrent.Remove(timePieces.First.Value);
                timePieces.RemoveFirst();
            }
        }
        lock (currentAccess)
        {
            if (DateTime.Now - current.EventTime > onePartInterval)
            {
                totalTillCurrent.Add(current);
                timePieces.AddLast(current);
                current = new TimeIntervalWrapper();
            }
        }
    }

    public TradeOffTimeMovingAverage(TimeSpan frequency)
    {
        interval = frequency;
        onePartInterval = TimeSpan.FromMilliseconds
                            ( frequency.TotalMilliseconds / partsCount );
        current = new TimeIntervalWrapper();
        totalTillCurrent = new TimeIntervalWrapper();
        measurer = new Timer(200);
        measurer.Elapsed += new ElapsedEventHandler(measurer_Elapsed);
        measurer.Start();
    }

    void measurer_Elapsed(object sender, ElapsedEventArgs e)
    {
        checkIntervals();
    }

    #region IMovingAverage Members

    public float Average
    {
        get 
        {
            lock (pastAccess)
            {
                return totalTillCurrent.Average;
            }
        }
    }

    public float MovingTotal
    {
        get 
        {
            lock (pastAccess)
            {
                return totalTillCurrent.Total;
            }
        }
    }

    public int MovingCount
    {
        get
        { 
            lock(pastAccess)
            {
                return totalTillCurrent.Quantity;
            }
        }
    }

    public float Total
    {
        get { return total; }
    }

    public long TotalCount { get { return totalCount; } }

    public void AddSample(float val)
    {
        lock (currentAccess)
        {
            total += val;
            totalCount++;
            current.AddSample(val);
        }
    }

    public void ClearSamples()
    {
        lock (pastAccess)
        {
            totalTillCurrent.Clear();
        }
        lock (currentAccess)
        {
            current.Clear();
        }
    }

    public void InitializeSamples(float val)
    {
        
    }

    #endregion

    public void Dispose()
    {
        measurer.Dispose();
    }
}

Example Program

The demo application shows three possible approaches in action. If the explanations given above are a bit hard and dim, the example should clarify the difference to you. There's a TextBox accepting digit chars only. By entering the digits, you "generate the events". The results for each approach are shown in groupboxes with appropriate names.

We may see the Moving Average, Moving count for the last 10 seconds. As you'll see, while typing, the Precise approach values change almost immediately, for the rude approach, the values change once in 10 seconds, and for Trade-Off approach, they change faster than for Rude and not so often as for Precise.

Points of Interest

There's a Weighted Moving average for the given N points. It might be useful for somebody to use Weighted Time-Moving average... but it's a rather complicated thing. :)

History

• 29.01.2012 - First published