9
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – syb0rg Jan 17 '14 at 3:00
  • \$\begingroup\$ How does your PointPairList look like? Does it implement IList<T>? \$\endgroup\$ – svick Jan 17 '14 at 11:16
  • \$\begingroup\$ @svick Yes it does \$\endgroup\$ – Simon Jan 17 '14 at 12:32
  • \$\begingroup\$ 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. \$\endgroup\$ – Jesse C. Slicer Jun 7 '16 at 21:10
8
\$\begingroup\$

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--;
        }
        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.

\$\endgroup\$
  • \$\begingroup\$ Thanks svick, good info, I will probably try to squeeze out every little bit, however the PointPairList is not my code so cannot change. \$\endgroup\$ – Simon Jan 17 '14 at 15:50

protected by Community Dec 2 '16 at 4:03

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.