Moving average calculation

Question

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
        movAvgPoints.Add(new PointPair(data[i].X, sum/actualFrameSize));
    }
    return movAvgPoints;
}

Answer 1

Skip() is not optimized for IList<T>, it always enumerates the skipped elements. This means that your algorithm is O(n²) 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--;
        }
        if (added < data.Count)
        {
            sum += data[added].Y;
            currentFrameSize++;
        }

        movAvgPoints.Add(new PointPair(data[i].X, sum/actualFrameSize));
    }

    return movAvgPoints;
}

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.