Simple round robin (moving average) array in C#

Question

As a diagnostic, I want to display the number of cycles per second in my app. (Think frames-per-second in a first-person-shooter.)

But I don't want to display the most recent value, or the average since launch. What I want to calculate is the mean of the last X values.

My question is, I suppose, about the best way to store these values. My first thought was to create a fixed size array, so each new value would push out the oldest. Is this the best way to do it? If so, how would I implement it?

EDIT: Here's the class I wrote: RRQueue. It inherits Queue, but enforces the capacity and dequeues if necessary.

Answer 1

The easiest option for this is probably to use a Queue<T>, as this provides the first-in, first-out behavior you're after. Just Enqueue() your items, and when you have more than X items, Dequeue() the extra item(s).

Answer 2

Keep an index where your next one goes. I'm not familiar with C# syntax, so here's a mock-up in Java. I'll leave it as an exercise to you to handle the case where the array is not yet populated.

class MovingArray {
    int[] values;
    int index;

    public MovingArray(int size) {
        values = new int[size];
        index = 0;
    }

    void add(int value) {
        values[index] = value;
        index = (index+1) % values.length;
    }

    float average() {
        int sum = 0;
        for(int i : values) sum += i;
        return ((float)sum)/values.length;
    }
}

Answer 3

If you need the fastest implementation, then yes, a fixed-size array ()with a separate count would be fastest.

Answer 4

A simple but fast implementation:

// untested

int[] values = new int [10];  // all 0's initially
int sum = 0;
int pos = 0;

void AddValue (int v)
{
   sum -= values[pos];  // only need the array to subtract old value
   sum += v;
   values[pos] = v;     
   pos = (pos + 1) % values.length;    
}

int Average()
{
   return sum / values.length;
}

Answer 5

You should take a look at the performance monitoring built into Windows :D.

MSDN

The API will feel a bit wonky if you haven't played with it before, but it's fast, powerful, extensible, and it makes quick work of getting usable results.