# Moving average calculation

I am hoping to make this method run a little faster. I typically need to run this on a list with more than 100000 entries. Note that at the start and end of the list, I wish to weight the average so that it is closer to the start or end value, hence the smaller framesize.

public PointPairList GetMovingAverage(int frameSize, PointPairList data)
{
PointPairList movAvgPoints = new PointPairList();
//Smooth each point in the list
for (int i = 0; i < data.Count; i++)
{
//get the window range
int actualFrameSize = frameSize;
int start = i - (frameSize/2);
int end = i + (frameSize/2);
//ensure the window is the same size at the source list boundaries
if (start < 0)
{
actualFrameSize = frameSize + start;
start = 0;
}
if (end >= data.Count)
{
actualFrameSize = frameSize + (data.Count - 1 - end);
}
//Now get the sum of the window
double sum = data.Skip(start).Take(actualFrameSize).Sum(p => p.Y);
//add the average point to the result
}
return movAvgPoints;
}

• Just a note relating to your original post: make your titles more descriptive to what your code does. You can request what you would like specifically reviewed in your post. – syb0rg Jan 17 '14 at 3:00
• How does your PointPairList look like? Does it implement IList<T>? – svick Jan 17 '14 at 11:16
• @svick Yes it does – Simon Jan 17 '14 at 12:32
• If aPointPairList constructor overload can take a capacity parameter, you can pre-allocate the size of the list, such like List<T> does and score a little performance gain by constructing it with data.Count. – Jesse C. Slicer Jun 7 '16 at 21:10

Skip() is not optimized for IList<T>, it always enumerates the skipped elements. This means that your algorithm is O(n2) for no good reason. What you should do instead is to manually iterate just the required part of the input in each iteration using for. Something like:

double sum = 0;
for (int i = 0; i < actualFrameSize; i++)
{
sum += data[start + i].Y;
}


(I don't like using GetRange() for this, as in tinstaafl's answer, because it unnecessarily copies the frame into a new list.)

If frameSize is large, another optimization would be not to recompute the sum of the frame for each index. Instead, just add the item from the front and subtract the item from the back:

public PointPairList GetMovingAverage(int frameSize, PointPairList data)
{
var movAvgPoints = new PointPairList();

//Before zero
int currentFrameSize = frameSize/2;
double sum = data.Take(currentFrameSize).Sum(p => p.Y);

//Smooth each point in the list
for (int i = 0; i < data.Count; i++)
{
int removed = i - (frameSize/2) - 1;
int added = i + (frameSize/2);

if (removed >= 0)
{
sum -= data[removed].Y;
currentFrameSize--;
}
{
currentFrameSize++;
}


If the length of data is n and frameSize is f, then the previous algorithm would be O(fn), but the improved one just O(n).
Another thing: there is usually no need to create types that derive from List, just use List<PointPair> directly.