Cyclic moving average filter in LINQ

Question

I am looking for an elegant way to implement a moving average filter in C #. Now it will be easy, but at the borders the averaging window should wrap around the beginning / end. This type made my code ugly and unintuitive, and I was wondering if there was a smarter way to solve this problem using LINQ or so.

So, I have a:

// input is a List<double> y, output is List<double> yfiltered int yLength = y.Count; for (int i = 0; i < yLength; i++) { double sum = 0.0; for (int k = i - halfWindowWidth; k <= i + halfWindowWidth; k++) { if (k < 0) { // k is negative, wrap around sum += y[yLength - 1 + k]; } else if (k >= yLength) { // k exceeds y length, wrap around sum += y[k - yLength]; } else { // k within y.Count sum += y[k]; } } yfiltered[i] = sum / (2 * halfWindowWidth + 1); } 

Answer 1

Extending to comment , you can use mod ( % ) to get k to wrap from 0 to ylength - 1

  // input is a List<double> y, output is List<double> yfiltered int yLength = y.Count; for (int i = 0; i < yLength; i++) { double sum = 0.0; for (int k = i - halfWindowWidth; k <= i + halfWindowWidth; k++) { sum += y[(k + yLength) % yLength]; } yfiltered[i] = sum / (2 * halfWindowWidth + 1); } 

Answer 2

Here is a completely different sentence -

I tried to make it better, not more readable.

The problem with your current code is that it sums a lot of numbers over and over again when it really is not needed.

Comparing both approaches after implementation code ...

I just summarize the bunch for the first time, and then subtract the tail and add the head again and again:

 double sum = 0; // sum = Enumerable.Range(i - halfWindowWidth, halfWindowWidth * 2 + 1) // .Select(k => y[(k + yLength) % yLength]).Sum(); for (var i = -halfWindowWidth; i <= halfWindowWidth; i++) { sum += y[(i + yLength) % yLength]; } yFiltered[0] = sum / (2 * halfWindowWidth + 1); for (var i = 1; i < yLength; i++) { sum = sum - y[(i - halfWindowWidth - 1 + yLength) % yLength] + y[(i + halfWindowWidth) % yLength]; yFiltered[i] = sum / (2 * halfWindowWidth + 1); } 

And here are the speed tests comparing the full recount approach to this:

 private static double[] Foo1(IList<double> y, int halfWindowWidth) { var yfiltered = new double[y.Count]; var yLength = y.Count; for (var i = 0; i < yLength; i++) { var sum = 0.0; for (var k = i - halfWindowWidth; k <= i + halfWindowWidth; k++) { sum += y[(k + yLength) % yLength]; } yfiltered[i] = sum / (2 * halfWindowWidth + 1); } return yfiltered; } private static double[] Foo2(IList<double> y, int halfWindowWidth) { var yFiltered = new double[y.Count]; var windowSize = 2 * halfWindowWidth + 1; double sum = 0; for (var i = -halfWindowWidth; i <= halfWindowWidth; i++) { sum += y[(i + y.Count) % y.Count]; } yFiltered[0] = sum / windowSize; for (var i = 1; i < y.Count; i++) { sum = sum - y[(i - halfWindowWidth - 1 + y.Count) % y.Count] + y[(i + halfWindowWidth) % y.Count]; yFiltered[i] = sum / windowSize; } return yFiltered; } private static TimeSpan TestFunc(Func<IList<double>, int, double[]> func, IList<double> y, int halfWindowWidth, int iteration { var sw = Stopwatch.StartNew(); for (var i = 0; i < iterations; i++) { var yFiltered = func(y, halfWindowWidth); } sw.Stop(); return sw.Elapsed; } private static void RunTests() { var y = new List<double>(); var rand = new Random(); for (var i = 0; i < 1000; i++) { y.Add(rand.Next()); } var foo1Res = Foo1(y, 100); var foo2Res = Foo2(y, 100); Debug.WriteLine("Results are equal: " + foo1Res.SequenceEqual(foo2Res)); Debug.WriteLine("Foo1: " + TestFunc(Foo1, y, 100, 1000)); Debug.WriteLine("Foo2: " + TestFunc(Foo2, y, 100, 1000)); } 

Temporary difficulties:

MyWay: O (n + m)

OtherWay: O (n * m)

Since Foo1 is O (n * m) and Foo2 is O (n + m), it is not surprising that the difference is huge.

The results of this not very crazy big scale:

Results are: True

Foo1: 5.52 seconds

Foo2: 61.1 milliseconds

And on a larger scale (replacing 1000 by 10000 on iterations and counts):

Foo1: stopped after 10 minutes ...

Foo2: 6.9 seconds

Answer 3

 for (var i = 0; i < yLength; i++) { var sum = Enumerable.Range(i - halfWindowWidth, halfWindowWidth * 2 + 1) .Select(k => y[(yLength + k) % yLength]).Sum(); yFiltered[i] = sum / (2 * halfWindowWidth + 1); } 

Or even:

 var output = input.Select((val, i) => Enumerable.Range(i - halfWindowWidth, halfWindowWidth * 2 + 1) .Select(k => input[(input.Count + k) % input.Count]) .Sum()).ToList();