Calculating moving-averages of variable parameters

Question

I have an integer property which is updated every second with a signal-strength value ranging from 0 - 100.

I'd like to be able to keep an ongoing measure of the moving average over the last 10, 25, 50 measurements.

What's the most efficient way of doing this?

I'm currently thinking of implementing a set of FIFO queues using NSMutableArray and popping the leading value every time I add a new one at the end once the array has the requisite number of entries. However, I'm not sure if there's a more efficient way of doing this or not.

Answer 1

I wrote a simple class called MovingAverage to handle this. You init the method with the number of periods to maintain and it keeps track of the rest using the modulus of the sample count to know which of the static slots to put it in.

Initialize with

MovingAverage *avg5periods = [[MovingAverage alloc] initWithSize:5];

Add items:

[avg5periods addSample:1.0];
NSLog(@"1.2f",[avg5periods movingAverage]); //1.0
[avg5periods addSample:2.0];
NSLog(@"1.2f",[avg5periods movingAverage]); //1.5
[avg5periods addSample:3.0];
NSLog(@"1.2f",[avg5periods movingAverage]); //2.0
[avg5periods addSample:4.0];
NSLog(@"1.2f",[avg5periods movingAverage]); //2.5
[avg5periods addSample:5.0];
NSLog(@"1.2f",[avg5periods movingAverage]); //3.0
[avg5periods addSample:6.0];
NSLog(@"1.2f",[avg5periods movingAverage]); //4.0

Header file:

#import <Foundation/Foundation.h>

@interface MovingAverage : NSObject {
    NSMutableArray *samples;
    int sampleCount;
    int averageSize;
}
-(id)initWithSize:(int)size;
-(void)addSample:(double)sample;
-(double)movingAverage;
@end

and the implementation file:

#import "MovingAverage.h"

@implementation MovingAverage
-(id)initWithSize:(int)size {
    if (self = [super init]) {
        samples = [[NSMutableArray alloc] initWithCapacity:size];
        sampleCount = 0;
        averageSize = size;
    }
    return self;
}
-(void)addSample:(double)sample {
    int pos = fmodf(sampleCount++, (float)averageSize);
    [samples setObject:[NSNumber numberWithDouble:sample] atIndexedSubscript:pos];
}
-(double)movingAverage {
    return [[samples valueForKeyPath:@"@sum.doubleValue"] doubleValue]/(sampleCount > averageSize-1?averageSize:sampleCount);
}
@end

Answer 2

A queue is the right way. The real efficiency comes with how you recalculate the average.

It should be done with:

avg = avg + newSample/N - [queue dequeue]/N
[queue enqueue:newSample]

i.e. the new running average is simply the old average minus the weight of the oldest value you dropped, plus the weight of the newest value you enqueued.

Answer 3

I think you've got the right solution.

If you really care about performance, instead of moving things in and out of a dynamically resized array you could use an array of static size and keep track of the current index.

I.e. if N is the size the array and % is the modulo operator (I'm not an objective C programmer):

values[current] = get_current_sample()
previous = (current + N - 1) % N
sum = sum + values[current] - values[previous]
current = (current + 1) % N

The average = sum / N. You have to treat the warm up period separately (before you have N samples).

This could be much faster depending on how NSMutableArray handles memory allocation.