How to calculate simple moving average faster in C

Question

What is the fastest library/algorithm for calculating simple moving average? I wrote my own, but it takes too long on 330 000 items decimal dataset.

• period / time(ms)
• 20 / 300;
• 60 / 1500;
• 120 / 3500.

Here is the code of my method:

public decimal MA_Simple(int period, int ii) {
    if (period != 0 && ii > period) {
        //stp.Start();
        decimal summ = 0;
        for (int i = ii; i > ii - period; i--) {
            summ = summ + Data.Close[i];
        }
        summ = summ / period;
        //stp.Stop();
        //if (ii == 1500) System.Windows.Forms.MessageBox.Show((stp.ElapsedTicks * 1000.0) / Stopwatch.Frequency + " ms");
        return summ;
    } else return -1;
}

The Data.Close[] is a fixed size(1 000 000) decimal array.

Answer 1

    public class MovingAverage  
    {
        private Queue<Decimal> samples = new Queue<Decimal>();
        private int windowSize = 16;
        private Decimal sampleAccumulator;
        public Decimal Average { get; private set; }

        /// <summary>
        /// Computes a new windowed average each time a new sample arrives
        /// </summary>
        /// <param name="newSample"></param>
        public void ComputeAverage(Decimal newSample)
        {
            sampleAccumulator += newSample;
            samples.Enqueue(newSample);

            if (samples.Count > windowSize)
            {
                sampleAccumulator -= samples.Dequeue();
            }

            Average = sampleAccumulator / samples.Count;
        }
    }

Answer 2

/// <summary>
/// Fast low CPU usage moving average based on floating point math
/// Note: This algorithm algorithm compensates for floating point error by re-summing the buffer for every 1000 values
/// </summary>
public class FastMovingAverageDouble
{
    /// <summary>
    /// Adjust this as you see fit to suit the scenario
    /// </summary>
    const int MaximumWindowSize = 100;

    /// <summary>
    /// Adjust this as you see fit
    /// </summary>
    const int RecalculateEveryXValues = 1000;

    /// <summary>
    /// Initializes moving average for specified window size
    /// </summary>
    /// <param name="_WindowSize">Size of moving average window between 2 and MaximumWindowSize 
    /// Note: this value should not be too large and also bear in mind the possibility of overflow and floating point error as this class internally keeps a sum of the values within the window</param>
    public FastMovingAverageDouble(int _WindowSize)
    {
        if (_WindowSize < 2)
        {
            _WindowSize = 2;
        }
        else if (_WindowSize > MaximumWindowSize)
        {
            _WindowSize = MaximumWindowSize;
        }
        m_WindowSize = _WindowSize;
    }
    private object SyncRoot = new object();
    private Queue<double> Buffer = new Queue<double>();
    private int m_WindowSize;
    private double m_MovingAverage = 0d;
    private double MovingSum = 0d;
    private bool BufferFull;
    private int Counter = 0;

    /// <summary>
    /// Calculated moving average
    /// </summary>
    public double MovingAverage
    {
        get
        {
            lock (SyncRoot)
            {
                return m_MovingAverage;
            }
        }
    }

    /// <summary>
    /// Size of moving average window set by constructor during intialization
    /// </summary>
    public int WindowSize
    {
        get
        {
            return m_WindowSize;
        }
    }

    /// <summary>
    /// Add new value to sequence and recalculate moving average seee <see cref="MovingAverage"/>
    /// </summary>
    /// <param name="NewValue">New value to be added</param>
    public void AddValue(int NewValue)
    {
        lock (SyncRoot)
        {
            Buffer.Enqueue(NewValue);
            MovingSum += NewValue;
            if (!BufferFull)
            {
                int BufferSize = Buffer.Count;
                BufferFull = BufferSize == WindowSize;
                m_MovingAverage = MovingSum / BufferSize;
            }
            else
            {
                Counter += 1;
                if (Counter > RecalculateEveryXValues)
                {
                    MovingSum = 0;
                    foreach (double BufferValue in Buffer)
                    {
                        MovingSum += BufferValue;
                    }
                    Counter = 0;
                }
                MovingSum -= Buffer.Dequeue();
                m_MovingAverage = MovingSum / WindowSize;
            }
        }
    }
}

Answer 3

These days, the Math DotNet library has a class called RunningStatistics that will do this for you. If you want to do it over the last "X" items only, use MovingStatistics instead.

Both will calculate running averages, variance, and standard deviation, on the fly with one-pass only and without storing extra copies of the data.

Answer 4

If the data is static, you can preprocess the array to make moving average queries very fast:

decimal[] GetCSum(decimal[] data) {
    decimal csum[] = new decimal[data.Length];
    decimal cursum = 0;
    for(int i=0; i<data.Length; i++) {
        cursum += data[i];
        csum[i] = cursum;
    }
    return csum;
}

Now the moving average calculation is easy and fast:

decimal CSumMovingAverage(decimal[] csum, int period, int ii) {
    if(period == 0 || ii <= period)
        return -1;
    return csum[ii] - csum[ii - period];
}

Answer 5

Here's how I tried it. But warning I'm a complete amateur so this may be completely wrong.

List<decimal> MovingAverage(int period, decimal[] Data)
{
     decimal[] interval = new decimal[period];
     List<decimal> MAs = new List<decimal>();

     for (int i=0, i < Data.length, i++)
     {
          interval[i % period] = Data[i];
          if (i > period - 1)
          {
               MAs.Add(interval.Average());
          }
     }
     return MAs;
}

Should return a list of decimals containing the moving averages for your data.