Main Site Documentation

Snippet - Basic Moving Average Filter


#1

I just posted Basic Moving Average Filter on Codeshare. Feel free to discuss and make suggestions here.


#2

There is no reason to declare unsafe the variable lastValuePointer.

It is an index, not a pointer.


#3

I had to remove that to get it to compile and it works fine without it.

The filter works really well with an ADC input and I am going to try this on my oven controller as the G120 ADC is noisy as hell.


#4

Here’s the one I am using: https://searchcode.com/codesearch/view/9462171/


#5

I haven’t test this code at all but I think this would be a more efficient way to achieve this. I apologize in advance if it doesn’t work but its based on the idea that…

(new average) = (old average) - (oldest value portion) + (newest value portion)


	public double NextAverage(double lastAverage, double value)
        {
            var oldestNdx = (int)lastValuePointer % buffer.Length;
            var oldestValue = buffer[oldestNdx];
            buffer[oldestNdx] = value;
            lastValuePointer = (uint)oldestNdx + 1;
            return lastAverage + value/buffer.Length - oldestValue/buffer.Length;
        }

It could definitely be simplified for further optimization but I left it verbose to make it easier to understand.


#6

I’ll plug your code into my programme and see what it does and let you know.


#7

Sorry, I got tired of waiting :wink: I had a few free minutes, so I ran some tests on my PC. I expect the comparisons would be much better performed on a micro. Due to other processes running on my PC, my results varied from 350% to 3500% improvement but never lower than 350%. I’d be interested in the result of your tests done on a micro. Because of this variation, it makes it impossible to really compare my tests in regards to variances in the buffer size. My method should take the same time for a buffer size of 1M as it does for a size of 10. John’s method will take longer for a larger buffer size.

Here are my test results.

[quote]Test Size (data points): 10000
Buffer Size: 10
Last Smith Average: 462.8739 (16374 ticks)
Last Lee Average: 462.8739 (862 ticks, 1899.54% improvement)

Test Size (data points): 10000
Buffer Size: 100
Last Smith Average: 525.1411 (45170 ticks)
Last Lee Average: 525.1411 (1737 ticks, 2600.46% improvement)

Test Size (data points): 100000000
Buffer Size: 100
Last Smith Average: 481.4439 (273818896 ticks)
Last Lee Average: 481.4439 (7723470 ticks, 3545.28% improvement)

Test Size (data points): 100000000
Buffer Size: 10
Last Smith Average: 541.2846 (31914886 ticks)
Last Lee Average: 541.2846 (7506496 ticks, 425.16% improvement)[/quote]

And here is my test code and my full class. @ Mr John Smith, feel free to use my code to revise your snippet if you like (with attribution, please).

using System;
using System.Diagnostics;

namespace MovingAvgTest
{
    class Program
    {
        static void Main(string[] args)
        {
            const int TEST_SIZE = 10000;
            const int BUFFER_SIZE = 10;

            Console.WriteLine("Test Size (data points): {0}", TEST_SIZE);
            Console.WriteLine("Buffer Size: {0}", BUFFER_SIZE);

            // Generate datapoints.
            var dataPoints = new double[TEST_SIZE];
            var rnd = new Random();
            for (var i = 0; i < TEST_SIZE; i++)
            {
                dataPoints[i] = rnd.NextDouble()*1000;
            }

            // Test the Smith average across all datapoints.
            var smithAvg = new SmithMovingAverage(BUFFER_SIZE, 0);
            var avg = 0.0;
            var stopwatch = new Stopwatch();
            stopwatch.Start();
            for (var i = 0; i < TEST_SIZE; i++)
            {
                avg = smithAvg.NextAverage(dataPoints[i]);
            }
            stopwatch.Stop();
            var smithTicks = stopwatch.ElapsedTicks;
            Console.WriteLine("Last Smith Average: {0:0.####}  ({1} ticks)", avg, smithTicks);

            // Test the Lee average across all datapoints.
            var leeAvg = new LeeMovingAverage(BUFFER_SIZE, 0);
            avg = 0.0;
            stopwatch = new Stopwatch();
            stopwatch.Start();
            for (var i = 0; i < TEST_SIZE; i++)
            {
                avg = leeAvg.NextAverage(dataPoints[i]);
            }
            stopwatch.Stop();
            var leeTicks = stopwatch.ElapsedTicks;
            Console.WriteLine("Last Lee Average: {0:0.####}  ({1} ticks, {2:0.##}% improvement)", avg, leeTicks, (double)smithTicks/leeTicks * 100);

            Console.ReadLine();
        }
    }

    public class SmithMovingAverage
    {
        double[] buffer;
        uint lastValuePointer = 0;
        public SmithMovingAverage(int bufferSize, double initialValue)
        {
            buffer = new double[bufferSize];
            for (int i = 0; i < bufferSize; i++)
            {
                buffer[i] = initialValue;
            }
        }

        public double NextAverage(double value)
        {
            int currentPointer = (int)lastValuePointer % buffer.Length;
            buffer[currentPointer] = value;
            double sum = 0;
            for (int i = 0; i < buffer.Length; i++)
            {
                sum += buffer[lastValuePointer % buffer.Length];
                lastValuePointer++;
            }
            lastValuePointer = (uint)currentPointer + 1;
            return sum / buffer.Length;
        }
    }

    public class LeeMovingAverage
    {
        private readonly double[] _buffer;
        private uint _lastNdx = 0;
        public double LastAverage;

        public LeeMovingAverage(int bufferSize, double initialValue)
        {
            _buffer = new double[bufferSize];
            for (var i = 0; i < bufferSize; i++)
            {
                _buffer[i] = initialValue;
            }
        }

        public double NextAverage(double value)
        {
            var oldestNdx = _lastNdx % _buffer.Length;
            var oldestValue = _buffer[oldestNdx];
            _buffer[oldestNdx] = value;
            _lastNdx = (uint)(++oldestNdx);
            LastAverage = LastAverage + (value - oldestValue) / _buffer.Length;
            return LastAverage;
        }
    }
}


#8

@ ianlee74 - Lol, I might as well delete it.


#9

Na. It’s still a good snippet to have in case someone wants it in the future. In all my years on this forum, I’ve never published a Snippet or Codeshare… I might as well not start now :frowning: Perhaps someone will suggest a further optimization later. Let’s keep it alive!


#10

Both work really well in my test setup using Integer values from a 16 bit ADC. I get a really nice stable reading using 20 data points.

I am reading a 4-20mA sensor that is 2000 PSI range and I am reading 2000.1 solid on the display using a simulator that is outputting 20.000mA

Nice work guys.


#11

If you make that buffer length a power of 2, you should be able to make it faster by applying a shift operator instead of a division?


#12

Good idea. Of course, that makes buffer size a bit less flexible but that shouldn’t be a problem for this use case.


#13

@ marius - Division takes longer than shift?


#14

Shift is perhaps the easiest operation for a CPU and division is probably the hardest of the basic math operations a CPU has to perform. I remember in my computer architectures class that we did division last since it was dependent on so many other register functions. See the workflow attached. That is what a basic CPU has to do just for unsigned division. It’s even more complicated for signed. Note that there are many shift operations required to do a single division.

Source: http://cise.ufl.edu/~mssz/CompOrg/CDA-arith.html


#15

@ ianlee74: That is a good link

@ Mr. Jon Smith: Sorry, I am not close to anything to be able to test it, by why don’t you take the example posted by @ ianlee74 and try it for yourself. It will be interesting to see the results. :wink:


#16

I’ve used JohnSMith’s one and it works extremely well handling an analog input and smooths it out.


#17

Using a shift instead of a division?
It should still work, just much faster. The problem is, as stated by @ ianlee74 that you are “limited” to buffer size that must be a power of 2, so it depends on how big or small the buffer must be to get a nice smooth result.Jumping from a buffer size of 10 to 16 might still be fine, but going from say a random 80 to 128 might be too big and the reverse of 64 might be too small…


#18

@ marius - If there are performance issues then I’ll just do multiple methods of the moving average. Some that support large buffers and some that support small ones. Calling different methods will give different performance advantages. I just need to confirm that shift is faster than divide.


#19

Since the example was using double for the data, converting to int and using shift would certainly be faster. Would it really matter? Probably not, unless you are doing a very large number of averages very frequently.

Not adding the same numbers every time is certainly a good idea.


#20

Just out of interest, I ported Ian’s code to C to try and filter the same ADC that I was using with C# but after some time there is an error creeping in and I get the wrong value from it.

I used int as the buffer.

Eg, I feed 6398 into to it and after a short time, I was getting 7550 from it. All the values in the buffer where 6398 so can’t see how 7550 came from this?

Should I be re-seting the lastAverage value to 0 before I make the call in the loop?