Click here to Skip to main content
15,867,885 members
Please Sign up or sign in to vote.
5.00/5 (4 votes)
See more:
Given a stream of floating point data that may never end (think of a politician's speech converted to binary and cast to 4 byte floats), calculate a rolling average and standard deviation. Some background on this can be found at Efficient and accurate rolling standard deviation – The Mindful Programmer[^]. Your challenge is to code this efficiently. Or ridiculously. Your call.

Last week:

First: huge thanks to Griff for his puzzle. Very nice.

Graeme has once again nailed it in last week's challenge. Do we need to give him a handicap? Maybe something like "your code cannot contain the letter E or the + sign. Sound fair?
Posted
Updated 2-Mar-17 6:55am
Comments
Bryian Tan 24-Feb-17 11:32am    
Yes please :), nah, he just a very talented dude.
Graeme_Grant 24-Feb-17 17:16pm    
Thank you for your kind words Bryian. I have had no formal education, all self-taught. :)
Maciej Los 25-Feb-17 4:11am    
So you deserved for loud bravos!
Graeme_Grant 25-Feb-17 4:14am    
Thank you :)
Patrice T 24-Feb-17 11:33am    
What about setting a limit on the number of times someone can win the challenge over a given period of time ?
Like limiting to 6 times per year. When one win, he can't win again in next 2 months.

C++
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <math.h>

#define N 16

int cmpfloats(const void * a, const void * b)
{
	if (*(float*)a <  *(float*)b) return -1;
	if (*(float*)a >  *(float*)b) return 1;
	
	return 0;
}

static const int sample_size = 5;

int main(int argc, char* argv[])
{
	float population[N] = { 0 };

	for (int i = 0; i < N; i++)
		population[i] = rand() % 10 + rand() / (float)RAND_MAX;

	qsort((void*)population, N, sizeof(float), cmpfloats);

	printf("dataset:\n");

	for (int i = 0; i < N; i++)
		printf("%6.4f ", population[i]);

	printf("\n\n");

	float avg = 0.00F;
	for (int t = 0; t < sample_size; t++)
		avg += population[t] / (float)sample_size;

	printf("average = %6.4f\n\n", avg);

	float var = 0.00F;
	float avg_old = 0.00F, avg_new = avg_old;
	for (int i = 0; i < N - sample_size + 1; i++)
	{
		int wn_old = i; avg_old = avg;
		int wn_new = i + sample_size;

		float* temp = (float*)calloc(sample_size, sizeof(float));
		memcpy((void*)temp, (const void*)&population[wn_old], sizeof(float) * sample_size);

		printf("window sample #%d (wn_start = %d wn_end = %d):\n", i, wn_old, wn_new);
		for (int t = 0; t < sample_size; t++)
			printf("%6.4f ", temp[t]);

		printf("\n");

		avg = avg_new = avg_old + (population[wn_new] - population[wn_old]) / sample_size;

		float sum = 0.00F, sumsq = 0.00F;
		for (int t = 0; t < sample_size; t++)
		{
			sum += temp[t];
			sumsq += temp[t] * temp[t];
		}

		float mu = sum / sample_size;
		float delta = (sumsq / sample_size) - float(pow((double)mu, 2));
		float stdev_pop = float(sqrt(delta));

		float var_sampl = 0.00F;
		for (int t = 0; t < sample_size; t++)
			var_sampl += float(pow((double)(temp[t] - mu), 2));

		var_sampl /= (sample_size - 1);

		float stdev_sampl = float(sqrt(var_sampl));

		printf("average = %6.4f variance_pop = %6.4f stdev_pop = %6.4f varience_sampl = %6.4f stdev_sampl = %6.4f\n", avg_old, delta, stdev_pop, var_sampl, stdev_sampl);
	}

	_getch();

    return 0;
}

dataset:
1.0150 1.4457 1.5135 1.5636 1.5712 2.0047 2.3779 2.7466 4.8087 5.3645 5.8589 7.1659 7.6630 8.6072 8.8960 9.4799

average = 1.4218

window sample #0 (wn_start = 0 wn_end = 5):
1.0150 1.4457 1.5135 1.5636 1.5712
average = 1.4218 variance_pop = 0.0434 stdev_pop = 0.2083 varience_sampl = 0.0542 stdev_sampl = 0.2329
window sample #1 (wn_start = 1 wn_end = 6):
1.4457 1.5135 1.5636 1.5712 2.0047
average = 1.6197 variance_pop = 0.0391 stdev_pop = 0.1976 varience_sampl = 0.0488 stdev_sampl = 0.2209
window sample #2 (wn_start = 2 wn_end = 7):
1.5135 1.5636 1.5712 2.0047 2.3779
average = 1.8062 variance_pop = 0.1132 stdev_pop = 0.3364 varience_sampl = 0.1415 stdev_sampl = 0.3761
window sample #3 (wn_start = 3 wn_end = 8):
1.5636 1.5712 2.0047 2.3779 2.7466
average = 2.0528 variance_pop = 0.2121 stdev_pop = 0.4606 varience_sampl = 0.2652 stdev_sampl = 0.5149
window sample #4 (wn_start = 4 wn_end = 9):
1.5712 2.0047 2.3779 2.7466 4.8087
average = 2.7018 variance_pop = 1.2621 stdev_pop = 1.1234 varience_sampl = 1.5776 stdev_sampl = 1.2560
window sample #5 (wn_start = 5 wn_end = 10):
2.0047 2.3779 2.7466 4.8087 5.3645
average = 3.4605 variance_pop = 1.8488 stdev_pop = 1.3597 varience_sampl = 2.3110 stdev_sampl = 1.5202
window sample #6 (wn_start = 6 wn_end = 11):
2.3779 2.7466 4.8087 5.3645 5.8589
average = 4.2313 variance_pop = 1.9812 stdev_pop = 1.4076 varience_sampl = 2.4765 stdev_sampl = 1.5737
window sample #7 (wn_start = 7 wn_end = 12):
2.7466 4.8087 5.3645 5.8589 7.1659
average = 5.1889 variance_pop = 2.0995 stdev_pop = 1.4490 varience_sampl = 2.6244 stdev_sampl = 1.6200
window sample #8 (wn_start = 8 wn_end = 13):
4.8087 5.3645 5.8589 7.1659 7.6630
average = 6.1722 variance_pop = 1.1639 stdev_pop = 1.0789 varience_sampl = 1.4549 stdev_sampl = 1.2062
window sample #9 (wn_start = 9 wn_end = 14):
5.3645 5.8589 7.1659 7.6630 8.6072
average = 6.9319 variance_pop = 1.4008 stdev_pop = 1.1836 varience_sampl = 1.7510 stdev_sampl = 1.3233
window sample #10 (wn_start = 10 wn_end = 15):
5.8589 7.1659 7.6630 8.6072 8.8960
average = 7.6382 variance_pop = 1.1821 stdev_pop = 1.0872 varience_sampl = 1.4776 stdev_sampl = 1.2156
window sample #11 (wn_start = 11 wn_end = 16):
7.1659 7.6630 8.6072 8.8960 9.4799
average = 8.3624 variance_pop = 0.7028 stdev_pop = 0.8383 varience_sampl = 0.8785 stdev_sampl = 0.9373
 
Share this answer
 
v3
Comments
Graeme_Grant 2-Mar-17 13:06pm    
You have the average and the variance, how about the Standard Deviation?
Arthur V. Ratz 2-Mar-17 23:25pm    
Fixed. Now it computes the standard deviation as well.
Graeme_Grant 2-Mar-17 23:39pm    
A couple of things:
1. You are missing the last test for your array of values:

Dataset: {7.1659,7.663,8.6072,8.896,9.4799}

2. I'm getting very different results:

Dataset: {5.8589,7.1659,7.663,8.6072,8.896}
Results: Avg = 7.6382
Std Dev = 1.21558758014386

So I ran it with Richard's and his returns the same results as myself. I think that there is an error in your calculation.
Arthur V. Ratz 3-Mar-17 1:15am    
I've fixed the code. I suppose this one will compute average and standard deviation correctly.
Graeme_Grant 3-Mar-17 6:48am    
:)
Yay, I love enumerations! :D

Here's my approach, a little different in a few ways:
  • I've never been a fan of moving averages that only look backwards, so mine uses a window centred on the current element instead.
  • I inherit from a generic window-maker. Unfortunately this means repeating the stats loops more often (order: input-length times window-length vs just input-length). However I prefer it because it helps avoid cumulative-numerical-error-disasters like Harold's test.
  • I chose to go with Welford's method for the standard deviation, preferring to iterate just once with a division operation, rather than re-iterate the IEnumerable (which probably wouldn't be too bad in our case).
Usage:
C#
IEnumerable<double> series = Enumerable.Range(0, 10).Select(a => (double)a);
var stats = series.RollingStats(n);
Windowing:
C#
/// <summary>
/// Enumerates this series and returns some basic stats.
/// </summary>
/// <param name="sourceSeries">The series to analyse</param>
public static SeriesStats GetStats(this IEnumerable<double> sourceSeries)
{
    return new SeriesStats(sourceSeries);
}

/// <summary>
/// Returns a rolling window around an element.
/// </summary>
/// <param name="elementsAround">
/// The number of elements to return before or after the current element.
/// Must be greater than or equal to zero.
/// Total number of elements in the window is between elementsAround + 1
/// and elementsAround * 2 + 1.
/// </param>
public static IEnumerable<IEnumerable<T>> RollingWindow<T>(
    this IEnumerable<T> source, int elementsAround)
{
    if (elementsAround < 0)
        throw new ArgumentOutOfRangeException(nameof(elementsAround));

    var preq = new Queue<T>(elementsAround + 1);
    var postq = new Queue<T>(elementsAround + 1);
    var fullq = preq.Concat(postq);
    var e = source.GetEnumerator();

    // preload elements into post-value queue
    for (int i = 0; i < elementsAround; i++)
    {
        if (!e.MoveNext()) break;
        postq.Enqueue(e.Current); // add look-ahead to post buffer
    }

    // send 
    while (e.MoveNext())
    {
        postq.Enqueue(e.Current); // add look-ahead to post buffer
        preq.Enqueue(postq.Dequeue()); // move the central value to pre buffer
        if (preq.Count > elementsAround + 1)
            preq.Dequeue(); // trim lookback
        yield return fullq;
    }

    // dump lookback
    while (postq.Count > 0)
    {
        preq.Enqueue(postq.Dequeue()); // move the central value to pre buffer
        if (preq.Count > elementsAround + 1)
            preq.Dequeue(); // trim lookback
        yield return fullq;
    }
}

/// <summary>
/// Returns stats for a rolling window around an element.
/// </summary>
/// <param name="elementsAround">
/// The number of elements to return before or after the current element.
/// Must be greater than or equal to zero.
/// Total number of elements in the window is between elementsAround + 1
/// and elementsAround * 2 + 1.
/// </param>
public static IEnumerable<SeriesStats> RollingStats(
    this IEnumerable<double> source, int elementsAround)
{
    return source.RollingWindow(elementsAround).Select(a => a.GetStats());
}
Stats:
C#
/// <summary>
/// Some basic stats about a series.
/// </summary>
public struct SeriesStats
{
    /// <summary>
    /// Enumerates a series and prepares some basic stats.
    /// </summary>
    /// <param name="sourceSeries">The series to analyse</param>
    public SeriesStats(IEnumerable<double> sourceSeries)
    {
        var n = 0;
        var sumx = 0d;
        var sumx2 = 0d;
        var m1 = 0d;
        var m2 = 0d;
        foreach (var x in sourceSeries)
        {
            n++;
            sumx += x;
            sumx2 += x * x;

            // Welford's method for stdev
            var d1 = (x - m1);
            m1 += d1 / n;
            var d2 = x - m1;
            m2 += d1 * d2;
        }
        this.Count = n;
        this.Variance = n < 2 ? double.NaN : m2 / (n - 1);
        this.Sum = sumx;
        this.SumSquares = sumx2;
    }

    /// <summary>
    /// The number of elements in the source series
    /// </summary>
    public int Count { get; private set; }

    /// <summary>
    /// The sum of the elements in the source series
    /// </summary>
    public double Sum { get; private set; }

    /// <summary>
    /// The sum of the squares of the elements in the source series
    /// </summary>
    public double SumSquares { get; private set; }

    /// <summary>
    /// The (estimated) variance of the elements in the source series
    /// </summary>
    public double Variance { get; private set; }

    /// <summary>
    /// The average of the elements in the source series
    /// </summary>
    public double Average { get { return Sum / Count; } }

    /// <summary>
    /// The (estimated) standard deviation
    /// of the elements in the source series
    /// </summary>
    public double StandardDeviation { get { return Math.Sqrt(Variance); } }
}
 
Share this answer
 
v2
Comments
Graeme_Grant 3-Mar-17 0:06am    
I'm not sure if I am running your code correctly but I've used Arthur's dataset and am not getting the results that I was expecting when compared with the output from Richard's and my solutions.

Here is the dataset:
Running

  avg=9.4799               std=NaN
  avg=9.18795              std=0.412879649534825
  avg=8.99436666666667     std=0.444587812848411
  avg=8.661525             std=0.758225900265437
  avg=8.3624               std=0.937314629673516
  avg=7.94515              std=1.32190481767788
  avg=7.57648571428571     std=1.5516401359299
  avg=7.2305125            std=1.73816737270486
  avg=6.7323               std=2.20850941700505
  avg=6.29686              std=2.4963268612548
  avg=5.90666363636364     std=2.69875309032624
  avg=5.545375             std=2.86138195509697
  avg=5.23908461538462     std=2.95377620424155
  avg=4.97297142857143     std=3.00750445883129
  avg=4.73782              std=3.03783617450692
  avg=4.50514375           std=3.07886838172052


Windowed

  avg=1.51895              std=0.316239660700552
  avg=1.64165714285714     std=0.434440908360554
  avg=1.779775             std=0.560703613456215
  avg=2.11632222222222     std=1.13774613576335
  avg=2.44114              std=1.48516078979872
  avg=2.75184545454545     std=1.74557984312585
  avg=3.31101818181818     std=2.08562508031438
  avg=3.87622727272727     std=2.35466726103325
  avg=4.52110909090909     std=2.60133818887685
  avg=5.18769090909091     std=2.70508354120702
  avg=5.90666363636364     std=2.69875309032624
  avg=6.29686              std=2.4963268612548
  avg=6.7323               std=2.20850941700505
  avg=7.2305125            std=1.73816737270486
  avg=7.57648571428571     std=1.5516401359299
  avg=7.94515              std=1.32190481767788
And here is what I was expecting to see:
Running

  avg=1.015                std=NaN
  avg=1.23035              std=0.304550890657045
  avg=1.32473333333333     std=0.270370603678236
  avg=1.38445              std=0.250993685179527
  avg=1.4218               std=0.232859367430214
  avg=1.51895              std=0.31623966070055
  avg=1.64165714285714     std=0.434440908360553
  avg=1.779775             std=0.560703613456214
  avg=2.11632222222222     std=1.13774613576335
  avg=2.44114              std=1.48516078979872
  avg=2.75184545454545     std=1.74557984312585
  avg=3.11968333333333     std=2.09611569243222
  avg=3.46916923076923     std=2.36968022082608
  avg=3.83617142857143     std=2.65877796956206
  avg=4.17349333333333     std=2.87592690585306
  avg=4.50514375           std=3.07886838172052


Windowed

  avg=1.015                std=NaN
  avg=1.23035              std=0.304550890657045
  avg=1.32473333333333     std=0.270370603678236
  avg=1.38445              std=0.250993685179527
  avg=1.4218               std=0.232859367430214
  avg=1.61974              std=0.22095185674712
  avg=1.80618              std=0.376163590742112
  avg=2.0528               std=0.514931369213414
  avg=2.70182              std=1.25600065963359
  avg=3.46048              std=1.52018821597853
  avg=4.23132              std=1.57369314099033
  avg=5.18892              std=1.6200035253048
  avg=6.1722               std=1.20619160584046
  avg=6.9319               std=1.3232502654449
  avg=7.6382               std=1.21558758014386
  avg=8.3624               std=0.937314629673514
Graeme_Grant 3-Mar-17 0:09am    
Here is the test code used:
class Program
{
    static void Main(string[] args)
    {
        double[] data = { 1.0150, 1.4457, 1.5135, 1.5636, 1.5712, 2.0047, 2.3779, 2.7466, 4.8087, 5.3645, 5.8589, 7.1659, 7.6630, 8.6072, 8.8960, 9.4799 };
        IEnumerable<double> series = data.Select(a => (double)a);

        Console.WriteLine("Running\r\n");
        for (int i = 0; i < data.Length; i++)
        {
            var stats = series.RollingStats(i).ToList().Last();
            Console.WriteLine($"  avg={stats.Average,-20} std={stats.StandardDeviation,-20}");
        }

        Console.WriteLine("\r\n\r\nWindowed\r\n");
        foreach (var stats in series.RollingStats(5))
        {
            Console.WriteLine($"  avg={stats.Average,-20} std={stats.StandardDeviation,-20}");
        }
        Console.ReadKey();
    }
}
H2O-au 3-Mar-17 0:30am    
Looks like we're just expecting different window sizes! My parameter is a symmetric half-window, so for windows of total size 5 you need to put in 2 (i.e. current element +/- 2 elements). So try series.RollingStats(2), and you should get what you expect (offset by 2 elements).
Graeme_Grant 3-Mar-17 0:37am    
Running total is not possible I see. Also, windows can only be of odd size and 3 or greater.

Also, after changing as recommended, the values are still out. Here are the new results:Hide   Copy Code
Windowed

  avg=1.32473333333333     std=0.270370603678235
  avg=1.38445              std=0.250993685179528
  avg=1.4218               std=0.232859367430215
  avg=1.61974              std=0.22095185674712
  avg=1.80618              std=0.376163590742113
  avg=2.0528               std=0.514931369213413
  avg=2.70182              std=1.25600065963358
  avg=3.46048              std=1.52018821597853
  avg=4.23132              std=1.57369314099033
  avg=5.18892              std=1.62000352530481
  avg=6.1722               std=1.20619160584047
  avg=6.9319               std=1.3232502654449
  avg=7.6382               std=1.21558758014386
  avg=8.3624               std=0.937314629673516
  avg=8.661525             std=0.758225900265437
  avg=8.99436666666667     std=0.444587812848411
H2O-au 3-Mar-17 0:50am    
Yep, that's right, my centred window wrecks all standard tests! :D So your new results are the expected results, but skipping the first two expected elements and adding two extra elements at the end (since my function looks ahead by 2 elements).
Thought that I would throw my hat into the ring in my normal (multi-language) style but a single solution only... ;)

One advantage of this solution, besides the very small memory footprint, is that you can use one or more endless streams of data, not just a fixed array with a fixed window.


C#
using System;
using System.Linq;

namespace RollingSD
{
    class Program
    {
        static void Main(string[] args)
        {
            double[] data = { 1E30f, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };

            Console.WriteLine("Running");
            Console.WriteLine("-------\r\n");

            int count = 0;
            var avg = 0.0;
            var t = new Tuple<double, double, int>(0.0, 0.0, 0);
            for (int i = 0; i < data.Length; i++)
            {
                avg = avg.Average(data[i], ref count);
                Console.WriteLine($"Dataset: {{{string.Join(", ", data.Take(i + 1))}}}");
                Console.WriteLine($"Results: Avg = {avg,-20} Std Dev = {data[i].StandardDeviation(ref t),-20}\r\n");
            }

            Console.WriteLine("\r\n\r\nWindowed");
            Console.WriteLine("--------\r\n");

            var window = new CircularBuffer<double>(5);
            foreach (var item in data)
            {
                window.Add(item);
                Console.WriteLine($"Dataset: {window}");
                Console.WriteLine($"Results: Avg = {window.Average(),-20} Std Dev = {window.StandardDeviation(),-20}\r\n");
            }

            Console.WriteLine("-- Press any ket to exit --");
            Console.ReadKey();
        }
    }

    public static class HelperExtensions
    {
        public static double StandardDeviation(this CircularBuffer<double> data)
        {
            var s1 = 0.0;
            var t = new Tuple<double, double, int>(0.0, 0.0, 0);
            for (int i = 0; i < data.Length; i++)
                s1 = data[i].StandardDeviation(ref t);
            return s1;
        }

        public static double StandardDeviation(this double value, ref Tuple<double, double, int> t)
        {
            var c = t.Item3 + 1;
            double m, s = m = 0.0;
            if (c == 1)
                m = value;
            else
            {
                m = t.Item1 + (value - t.Item1) / c;
                s = t.Item2 + (value - t.Item1) * (value - m);
            }
            t = new Tuple<double, double, int>(m, s, c);
            return Math.Sqrt(c > 1 ? s / (c - 1) : 0);
        }

        public static double Average(this CircularBuffer<double> data)
        {
            var a1 = 0.0;
            int count = 0;
            for (int i = 0; i < data.Length; i++)
                a1 = a1.Average(data[i], ref count);
            return a1;
        }

        public static double Average(this double average, double value, ref int count)
            => (average * count + value) / ++count;
    }

    public class CircularBuffer<T>
    {
        T[] buffer;
        int nextFree, len;

        public CircularBuffer(int length)
        {
            buffer = new T[length];
            nextFree = 0;
        }

        public void Add(T o)
        {
            buffer[nextFree] = o;
            nextFree = (nextFree + 1) % buffer.Length;
            if (len < buffer.Length) len++;
        }

        public T this[int index]
            => index >= 0 && index <= buffer.Length ? buffer[index] : default(T);

        public int Length => len;

        public override string ToString()
            => $"{{{string.Join(", ", ToList())}}}";

        public IEnumerable<T> ToList()
        {
            foreach (var item in nextFree < len
                ? buffer.Skip(nextFree)
                        .Take(len - nextFree)
                        .Concat(buffer.Take(nextFree))
                : buffer.Take(len))
                yield return item;
        }
    }
}

VB.NET
Imports System.Runtime.CompilerServices

Module Module1

    Sub Main()

        Dim data As Double() = {1.0E+30F, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

        Console.WriteLine("Running")
        Console.WriteLine("-------{0}", vbCrLf)

        Dim count As Integer = 0
        Dim avg As Double = 0F
        Dim t = New Tuple(Of Double, Double, Integer)(0.0, 0.0, 0)
        For i As Integer = 0 To data.Length - 1
            avg = avg.Average(data(i), count)
            Console.WriteLine("Dataset: {{{0}}}", String.Join(", ", data.Take(i + 1)))
            Console.WriteLine("Results: Avg = {0,-20} Std Dev = {1,-20}{2}",
                              avg, data(i).StandardDeviation(t), vbCrLf)
        Next

        Console.WriteLine("{0}{0}Windowed", vbCrLf)
        Console.WriteLine("--------{0}", vbCrLf)

        Dim window = New CircularBuffer(Of Double)(5)
        For Each item In data
            window.Add(item)
            Console.WriteLine("Dataset: {0}", window)
            Console.WriteLine("Results: Avg = {0,-20} Std Dev = {1,-20}{2}",
                              window.Average(), window.StandardDeviation(), vbCrLf)
        Next
        Console.WriteLine("-- Press any ket to exit --")
        Console.ReadKey()
    End Sub

End Module

Module HelperExtensions

    <Extension>
    Public Function StandardDeviation(data As CircularBuffer(Of Double)) As Double
        Dim s1 = 0.0
        Dim t = New Tuple(Of Double, Double, Integer)(0.0, 0.0, 0)
        For i As Integer = 0 To data.Length - 1
            s1 = data(i).StandardDeviation(t)
        Next
        Return s1
    End Function

    <Extension>
    Public Function StandardDeviation(value As Double, ByRef t As Tuple(Of Double, Double, Integer)) As Double
        Dim c = t.Item3 + 1
        Dim m = 0.0
        Dim s = 0.0
        If c = 1 Then
            m = value
        Else
            m = t.Item1 + (value - t.Item1) / c
            s = t.Item2 + (value - t.Item1) * (value - m)
        End If
        t = New Tuple(Of Double, Double, Integer)(m, s, c)
        Return Math.Sqrt(IIf(c > 1, s / (c - 1), 0))
    End Function

    <Extension>
    Public Function Average(data As CircularBuffer(Of Double)) As Double
        Dim a1 = 0.0
        Dim count As Integer = 0
        For i As Integer = 0 To data.Length - 1
            a1 = a1.Average(data(i), count)
        Next
        Return a1
    End Function

    <Extension>
    Public Function Average(avg As Double, value As Double, ByRef count As Integer) As Double
        count += 1
        Dim ret As Double = (avg * (count - 1) + value) / count
        Return ret
    End Function

End Module

Public Class CircularBuffer(Of T)

    Private buffer As T()
    Private nextFree As Integer, len As Integer

    Public Sub New(length As Integer)
        buffer = New T(length - 1) {}
        nextFree = 0
    End Sub

    Public Sub Add(o As T)
        buffer(nextFree) = o
        nextFree = (nextFree + 1) Mod buffer.Length
        If len < buffer.Length Then
            len += 1
        End If
    End Sub

    Default Public ReadOnly Property Item(index As Integer) As T
        Get
            Return If(index >= 0 AndAlso index <= buffer.Length, buffer(index), Nothing)
        End Get
    End Property

    Public ReadOnly Property Length() As Integer
        Get
            Return len
        End Get
    End Property

    Public Overrides Function ToString() As String
        Return String.Format("{{{0}}}", String.Join(", ", ToList()))
    End Function

    Public Iterator Function ToList() As IEnumerable(Of T)
        For Each Item As T In If(nextFree < len,
            buffer.Skip(nextFree) _
                  .Take(len - nextFree) _
                  .Concat(buffer.Take(nextFree)), buffer.Take(len))
            Yield Item
        Next
    End Function

End Class


Output:
Running
-------

Dataset: {1.00000001504747E+30}
Results: Avg = 1.00000001504747E+30 Std Dev = 0

Dataset: {1.00000001504747E+30, 1}
Results: Avg = 5.00000007523733E+29 Std Dev = 7.07106791826713E+29

Dataset: {1.00000001504747E+30, 1, 1}
Results: Avg = 3.33333338349155E+29 Std Dev = 5.77350277877284E+29

Dataset: {1.00000001504747E+30, 1, 1, 1}
Results: Avg = 2.50000003761867E+29 Std Dev = 5.00000007523733E+29

Dataset: {1.00000001504747E+30, 1, 1, 1, 1}
Results: Avg = 2.00000003009493E+29 Std Dev = 4.47213602229389E+29

Dataset: {1.00000001504747E+30, 1, 1, 1, 1, 1}
Results: Avg = 1.66666669174578E+29 Std Dev = 4.08248296606965E+29

Dataset: {1.00000001504747E+30, 1, 1, 1, 1, 1, 1}
Results: Avg = 1.42857145006781E+29 Std Dev = 3.77964478696635E+29

Dataset: {1.00000001504747E+30, 1, 1, 1, 1, 1, 1, 1}
Results: Avg = 1.25000001880933E+29 Std Dev = 3.53553395913357E+29

Dataset: {1.00000001504747E+30, 1, 1, 1, 1, 1, 1, 1, 1}
Results: Avg = 1.11111112783052E+29 Std Dev = 3.33333338349155E+29

Dataset: {1.00000001504747E+30, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Results: Avg = 1.00000001504747E+29 Std Dev = 3.16227770775265E+29

Dataset: {1.00000001504747E+30, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Results: Avg = 9.09090922770424E+28 Std Dev = 3.01511349114745E+29



Windowed
--------

Dataset: {1.00000001504747E+30}
Results: Avg = 1.00000001504747E+30 Std Dev = 0

Dataset: {1.00000001504747E+30, 1}
Results: Avg = 5.00000007523733E+29 Std Dev = 7.07106791826713E+29

Dataset: {1.00000001504747E+30, 1, 1}
Results: Avg = 3.33333338349155E+29 Std Dev = 5.77350277877284E+29

Dataset: {1.00000001504747E+30, 1, 1, 1}
Results: Avg = 2.50000003761867E+29 Std Dev = 5.00000007523733E+29

Dataset: {1.00000001504747E+30,1,1,1,1}
Results: Avg = 2.00000003009493E+29 Std Dev = 4.47213602229389E+29

Dataset: {1,1,1,1,1}
Results: Avg = 1                    Std Dev = 0

Dataset: {1,1,1,1,1}
Results: Avg = 1                    Std Dev = 0

Dataset: {1,1,1,1,1}
Results: Avg = 1                    Std Dev = 0

Dataset: {1,1,1,1,1}
Results: Avg = 1                    Std Dev = 0

Dataset: {1,1,1,1,1}
Results: Avg = 1                    Std Dev = 0

Dataset: {1,1,1,1,1}
Results: Avg = 1                    Std Dev = 0

-- Press any ket to exit --

Passes Harold's test[^] from The Lounge. :)

UPDATE: I thought that I would add a live visualization of the formula using the above code. Here is a screenshot[^] of the app. Data fed in every 1/2 second and runs until closed.

To help with the visualzations, I have used the excellent free charting library Live Charts[^].

1. Xaml page
XML
<Window 
    x:Class="WpfRollingSD.MainWindow"
    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"

    xmlns:lvc="clr-namespace:LiveCharts.Wpf;assembly=LiveCharts.Wpf"
    xmlns:vm="clr-namespace:WpfRollingSD.ViewModels"

    xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
    xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
    mc:Ignorable="d" WindowStartupLocation="CenterScreen"
    Title="Coding Challenge: Windows Std Dev & Average" Height="660" Width="600">

    <Window.DataContext>
        <vm:MainViewModel/>
    </Window.DataContext>
    
    <Grid Margin="15" MaxHeight="600">
        <Grid.Effect>
            <DropShadowEffect BlurRadius="15" Direction="-90" 
                              RenderingBias="Quality" Opacity=".2" 
                              ShadowDepth="1"/>
        </Grid.Effect>
        <Grid.OpacityMask>
            <VisualBrush Visual="{Binding ElementName=Border1}" />
        </Grid.OpacityMask>
        <Grid.RowDefinitions>
            <RowDefinition Height="Auto"/>
            <RowDefinition Height="Auto"/>
            <RowDefinition Height="0.60*"/>
            <RowDefinition Height="0.4*"/>
        </Grid.RowDefinitions>
        <Grid.Resources>
            <Style x:Key="CleanSeparator" TargetType="lvc:Separator">
                <Setter Property="IsEnabled" Value="False"/>
            </Style>
            <Style x:Key="ValueStyle" TargetType="lvc:LineSeries">
                <Setter Property="Stroke" Value="Red"/>
                <Setter Property="Fill" Value="Transparent"/>
                <Setter Property="StrokeDashArray" Value="2"/>
                <Setter Property="PointGeometrySize" Value="6"/>
                <Setter Property="PointGeometry"
                        Value="{x:Static lvc:DefaultGeometries.Diamond}"/>
            </Style>
            <Style x:Key="AverageStyle" TargetType="lvc:LineSeries">
                <Setter Property="Stroke" Value="#FF4095FC"/>
                <Setter Property="Fill" Value="Transparent"/>
                <Setter Property="PointGeometrySize" Value="0"/>
                <Setter Property="LineSmoothness" Value="0"/>
            </Style>
            <Style x:Key="StdDevStyle" TargetType="lvc:LineSeries">
                <Setter Property="Stroke" Value="#FF004A26"/>
                <Setter Property="Fill" Value="Transparent"/>
                <Setter Property="PointGeometrySize" Value="0"/>
                <Setter Property="LineSmoothness" Value="0"/>
            </Style>
        </Grid.Resources>
        <Border x:Name="Border1" Grid.Row="0" Grid.RowSpan="4" CornerRadius="5" Background="White"/>
        <Border Grid.Row="0" Grid.RowSpan="3"/>
        <TextBlock Grid.Row="0" TextAlignment="Center" Padding="10, 10, 0, 5" FontSize="18">
            Windowed Standard Deviation & Average
        </TextBlock>
        <lvc:CartesianChart Grid.Row="2" Margin="10 0"
                            BorderBrush="LightGray" BorderThickness="0 0 0 1"
                            Hoverable="False" 
                            DataTooltip="{x:Null}">
            <lvc:CartesianChart.AxisY>
                <lvc:Axis Foreground="Red" Title="Value">
                    <lvc:Axis.Separator>
                        <lvc:Separator Style="{StaticResource CleanSeparator}"/>
                    </lvc:Axis.Separator>
                </lvc:Axis>
                <lvc:Axis Foreground="#FF4095FC" Title="Average" Position="RightTop">
                    <lvc:Axis.Separator>
                        <lvc:Separator Style="{StaticResource CleanSeparator}"/>
                    </lvc:Axis.Separator>
                </lvc:Axis>
                <lvc:Axis Foreground="#FF004A26" Title="Standard Deviation"
                          Position="RightTop">
                    <lvc:Axis.Separator>
                        <lvc:Separator Style="{StaticResource CleanSeparator}"/>
                    </lvc:Axis.Separator>
                </lvc:Axis>
            </lvc:CartesianChart.AxisY>
            <lvc:CartesianChart.AxisX>
                <lvc:Axis MinValue="2" ShowLabels="False" IsEnabled="False"/>
            </lvc:CartesianChart.AxisX>
            <lvc:CartesianChart.Series>
                <lvc:LineSeries Values="{Binding ValueSeries[0].Values}"
                                Style="{StaticResource ValueStyle}" ScalesYAt="0"/>
                <lvc:LineSeries Values="{Binding ValueSeries[1].Values}"
                                Style="{StaticResource AverageStyle}" ScalesYAt="1"/>
                <lvc:LineSeries Values="{Binding ValueSeries[2].Values}"
                                Style="{StaticResource StdDevStyle}" ScalesYAt="2"/>
            </lvc:CartesianChart.Series>
        </lvc:CartesianChart>
        <Grid Grid.Row="3" HorizontalAlignment="Center">
            <Grid.ColumnDefinitions>
                <ColumnDefinition/>
                <ColumnDefinition/>
                <ColumnDefinition/>
            </Grid.ColumnDefinitions>
            <Grid.Resources>
                <Style x:Key="HeaderStyle" TargetType="TextBlock">
                    <Setter Property="TextAlignment" Value="Left"/>
                    <Setter Property="Margin" Value="0 0 0 10"/>
                    <Setter Property="FontWeight" Value="Bold"/>
                </Style>
                <Style TargetType="StackPanel">
                    <Setter Property="HorizontalAlignment" Value="Left"/>
                    <Setter Property="Margin" Value="10"/>
                </Style>
            </Grid.Resources>
            <StackPanel>
                <TextBlock Style="{StaticResource HeaderStyle}">
                    Values
                </TextBlock>
                <ItemsControl ItemsSource="{Binding ValueSeries[0].Values}"
                              DisplayMemberPath="Value"/>
            </StackPanel>
            <StackPanel Grid.Column="1">
                <TextBlock Style="{StaticResource HeaderStyle}">
                    Averages
                </TextBlock>
                <ItemsControl ItemsSource="{Binding ValueSeries[1].Values}"
                              DisplayMemberPath="Value"/>
            </StackPanel>
            <StackPanel Grid.Column="2">
                <TextBlock Style="{StaticResource HeaderStyle}">
                    Std Devs
                </TextBlock>
                <ItemsControl ItemsSource="{Binding ValueSeries[2].Values}"
                              DisplayMemberPath="Value"/>
            </StackPanel>
        </Grid>
    </Grid>
</Window>
2. ViewModel:


C#
using LiveCharts;
using LiveCharts.Defaults;
using LiveCharts.Wpf;
using System;
using System.Linq;
using System.Windows.Threading;

namespace WpfRollingSD.ViewModels
{
    public class MainViewModel
    {
        public MainViewModel()
        {
            ValueSeries = new SeriesCollection()
            {
                new LineSeries { Values = new ChartValues<ObservableValue>() },
                new LineSeries { Values = new ChartValues<ObservableValue>() },
                new LineSeries { Values = new ChartValues<ObservableValue>() }
            };

            timer.Interval = new TimeSpan(0, 0, 0, 0, 500);
            timer.Tick += Update;
            timer.Start();
        }

        public SeriesCollection ValueSeries { get; set; }

        private DispatcherTimer timer = new DispatcherTimer();
        private CircularBuffer<double> window = new CircularBuffer<double>(5);

        private void Update(object sender, EventArgs e)
        {
            var r = new Random();
            var value = r.Next(-10, 10);
            window.Add(value);
            ValueSeries[0].Values.Add(new ObservableValue(value));
            ValueSeries[1].Values.Add(new ObservableValue(window.Average()));
            ValueSeries[2].Values.Add(new ObservableValue(window.StandardDeviation()));
            if (ValueSeries[0].Values.Count > 12)
            {
                ValueSeries[0].Values.RemoveAt(0);
                ValueSeries[1].Values.RemoveAt(0);
                ValueSeries[2].Values.RemoveAt(0);
            }
        }
    }
}

VB
Imports System.Runtime.CompilerServices
Imports System.Windows.Threading
Imports LiveCharts
Imports LiveCharts.Defaults
Imports LiveCharts.Wpf

Public Class MainViewModel

    Public Sub New()

        ValueSeries = New SeriesCollection() From
        {
            New LineSeries() With {.Values = New ChartValues(Of ObservableValue)()},
            New LineSeries() With {.Values = New ChartValues(Of ObservableValue)()},
            New LineSeries() With {.Values = New ChartValues(Of ObservableValue)()}
        }

        timer.Interval = New TimeSpan(0, 0, 0, 0, 500)
        AddHandler timer.Tick, AddressOf Update
        timer.Start()

    End Sub

    Public Property ValueSeries() As SeriesCollection

    Private timer As New DispatcherTimer()
    Private window As New CircularBuffer(Of Double)(5)

    Private Sub Update(sender As Object, e As EventArgs)
        Dim r = New Random()
        Dim value = r.[Next](-10, 10)
        window.Add(value)
        ValueSeries(0).Values.Add(New ObservableValue(value))
        ValueSeries(1).Values.Add(New ObservableValue(window.Average()))
        ValueSeries(2).Values.Add(New ObservableValue(window.StandardDeviation()))
        If ValueSeries(0).Values.Count > 12 Then
            ValueSeries(0).Values.RemoveAt(0)
            ValueSeries(1).Values.RemoveAt(0)
            ValueSeries(2).Values.RemoveAt(0)
        End If
    End Sub

End Class

You can download and try out the app:
* WPF C# Version[^]
* WPF VB Version[^]

UPDATE #2: Not everyone does WPF. So here are WinForms Live Data versions that works just like the WPF versions above.


C#
using System;
using System.Linq;
using System.Windows.Media;
using System.Windows.Forms;
using LiveCharts;
using LiveCharts.Wpf;
using System.Collections.Generic;
using LiveCharts.Defaults;

namespace WfRollingSD
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();

            InitChart();
            SetBindings();

            Timer = new Timer { Interval = 500 };
            Timer.Tick += Update;
            Timer.Start();
        }

        private void InitChart()
        {
            // Values
            cartesianChart1.AxisY.Add(new Axis
            {
                Foreground = Brushes.Red,
                Title = "Value"
            });

            cartesianChart1.Series.Add(new LineSeries
            {
                Stroke = Brushes.Red,
                Fill = Brushes.Transparent,
                StrokeDashArray = new DoubleCollection { 2 },
                PointGeometrySize = 6,
                PointGeometry = DefaultGeometries.Diamond,
                ScalesYAt = 0,
                Values = new ChartValues<ObservableValue>()
            });

            // Average
            cartesianChart1.AxisY.Add(new Axis
            {
                Foreground = new SolidColorBrush(Color.FromArgb(0xFF, 0x40, 0x95, 0xFC)),
                Title = "Average",
                Position = AxisPosition.RightTop,
                Separator = new Separator { IsEnabled = false }
            });

            cartesianChart1.Series.Add(new LineSeries
            {
                Stroke = new SolidColorBrush(Color.FromArgb(0xFF, 0x40, 0x95, 0xFC)),
                Fill = Brushes.Transparent,
                PointGeometrySize = 0,
                LineSmoothness = 0,
                ScalesYAt = 1,
                Values = new ChartValues<ObservableValue>()
            });

            //Standard Deviation
            cartesianChart1.AxisY.Add(new Axis
            {
                Foreground = new SolidColorBrush(Color.FromArgb(0xFF, 0x00, 0x4A, 0x26)),
                Title = "Standard Deviation",
                Position = AxisPosition.RightTop,
                Separator = new Separator { IsEnabled = false }
            });

            cartesianChart1.Series.Add(new LineSeries
            {
                Stroke = new SolidColorBrush(Color.FromArgb(0xFF, 0x00, 0x4A, 0x26)),
                Fill = Brushes.Transparent,
                PointGeometrySize = 0,
                LineSmoothness = 0,
                ScalesYAt = 2,
                Values = new ChartValues<ObservableValue>()
            });

            // Timeline
            cartesianChart1.AxisX.Add(new Axis
            {
                ShowLabels = false,
                IsEnabled = false
            });
        }

        private void RefreshBindings()
        {
            if (lbValues.InvokeRequired)
            {
                lbValues.Invoke((Action)(() => RefreshBindings()));
                return;
            }

            SetBindings();
            RefreshUI();
        }

        private BindingSource valueBinding = new BindingSource();
        private BindingSource avgBinding = new BindingSource();
        private BindingSource stdDevBinding = new BindingSource();

        private void SetBindings()
        {
            lbValues.Bind<int>(valueBinding, cartesianChart1.Series[0].Values);
            lbAverages.Bind<double>(avgBinding, cartesianChart1.Series[1].Values);
            lbStdDevs.Bind<double>(stdDevBinding, cartesianChart1.Series[2].Values);
        }

        private void RefreshUI()
        {
            lbValues.Refresh();
            lbAverages.Refresh();
            lbStdDevs.Refresh();
        }

        private Timer Timer;
        private Random r = new Random();
        private CircularBuffer<double> window = new CircularBuffer<double>(5);

        private void Update(object sender, EventArgs eventArgs)
        {
            var value = r.Next(-10, 10);
            window.Add(value);
            cartesianChart1.Series[0].Values.Add(new ObservableValue(value));
            cartesianChart1.Series[1].Values.Add(new ObservableValue(window.Average()));
            cartesianChart1.Series[2].Values.Add(new ObservableValue(window.StandardDeviation()));
            if (cartesianChart1.Series[0].Values.Count > 12)
            {
                cartesianChart1.Series[0].Values.RemoveAt(0);
                cartesianChart1.Series[1].Values.RemoveAt(0);
                cartesianChart1.Series[2].Values.RemoveAt(0);
            }
            RefreshBindings();
        }
    }

    public static class LiveChartsExtensions
    {
        public static IEnumerable<T> ToList<T>(this IChartValues values)
        {
            foreach (var item in values)
                yield return (T)Convert.ChangeType(((ObservableValue)item).Value, typeof(T));
        }

        public static void Bind<T>(this ListBox lb, BindingSource source, IChartValues values)
        {
            source.DataSource = values.ToList<T>();
            lb.DataSource = source;
        }
    }
}

VB
Imports System.Runtime.CompilerServices
Imports System.Windows.Media
Imports LiveCharts
Imports LiveCharts.Defaults
Imports LiveCharts.Wpf

Public Class Form1

    Public Sub New()
        InitializeComponent()

        InitChart()
        SetBindings()

        Timer = New Timer() With {
            .Interval = 500
        }
        AddHandler Timer.Tick, AddressOf Update
        Timer.Start()
    End Sub

    Private Sub InitChart()
        ' Values
        cartesianChart1.AxisY.Add(New Axis() With {
            .Foreground = Brushes.Red,
            .Title = "Value"
        })

        cartesianChart1.Series.Add(New LineSeries() With {
            .Stroke = Brushes.Red,
            .Fill = Brushes.Transparent,
            .StrokeDashArray = New DoubleCollection() From {
                2
            },
            .PointGeometrySize = 6,
            .PointGeometry = DefaultGeometries.Diamond,
            .ScalesYAt = 0,
            .Values = New ChartValues(Of ObservableValue)()
        })

        ' Average
        cartesianChart1.AxisY.Add(New Axis() With {
            .Foreground = New SolidColorBrush(Color.FromArgb(&HFF, &H40, &H95, &HFC)),
            .Title = "Average",
            .Position = AxisPosition.RightTop,
            .Separator = New Separator() With {
                .IsEnabled = False
            }
        })

        cartesianChart1.Series.Add(New LineSeries() With {
            .Stroke = New SolidColorBrush(Color.FromArgb(&HFF, &H40, &H95, &HFC)),
            .Fill = Brushes.Transparent,
            .PointGeometrySize = 0,
            .LineSmoothness = 0,
            .ScalesYAt = 1,
            .Values = New ChartValues(Of ObservableValue)()
        })

        'Standard Deviation
        cartesianChart1.AxisY.Add(New Axis() With {
            .Foreground = New SolidColorBrush(Color.FromArgb(&HFF, &H0, &H4A, &H26)),
            .Title = "Standard Deviation",
            .Position = AxisPosition.RightTop,
            .Separator = New Separator() With {
                .IsEnabled = False
            }
        })

        cartesianChart1.Series.Add(New LineSeries() With {
            .Stroke = New SolidColorBrush(Color.FromArgb(&HFF, &H0, &H4A, &H26)),
            .Fill = Brushes.Transparent,
            .PointGeometrySize = 0,
            .LineSmoothness = 0,
            .ScalesYAt = 2,
            .Values = New ChartValues(Of ObservableValue)()
        })

        ' Timeline
        cartesianChart1.AxisX.Add(New Axis() With {
            .ShowLabels = False,
            .IsEnabled = False
        })

    End Sub

    Private Sub RefreshBindings()

        If lbValues.InvokeRequired Then
            lbValues.Invoke(DirectCast(Sub() RefreshBindings(), Action))
            Return
        End If

        SetBindings()
        RefreshUI()
    End Sub

    Private valueBinding As New BindingSource()
    Private avgBinding As New BindingSource()
    Private stdDevBinding As New BindingSource()

    Private Sub SetBindings()
        lbValues.Bind(Of Integer)(valueBinding, cartesianChart1.Series(0).Values)
        lbAverages.Bind(Of Double)(avgBinding, cartesianChart1.Series(1).Values)
        lbStdDevs.Bind(Of Double)(stdDevBinding, cartesianChart1.Series(2).Values)
    End Sub

    Private Sub RefreshUI()
        lbValues.Refresh()
        lbAverages.Refresh()
        lbStdDevs.Refresh()
    End Sub

    Private Timer As Timer
    Private r As New Random()
    Private window As New CircularBuffer(Of Double)(5)

    Private Sub Update(sender As Object, eventArgs As EventArgs)
        Dim value = r.[Next](-10, 10)
        window.Add(value)
        cartesianChart1.Series(0).Values.Add(New ObservableValue(value))
        cartesianChart1.Series(1).Values.Add(New ObservableValue(window.Average()))
        cartesianChart1.Series(2).Values.Add(New ObservableValue(window.StandardDeviation()))
        If cartesianChart1.Series(0).Values.Count > 12 Then
            cartesianChart1.Series(0).Values.RemoveAt(0)
            cartesianChart1.Series(1).Values.RemoveAt(0)
            cartesianChart1.Series(2).Values.RemoveAt(0)
        End If
        RefreshBindings()
    End Sub

End Class

Module LiveChartsExtensions

    <Extension>
    Public Iterator Function ToList(Of T)(values As IChartValues) As IEnumerable(Of T)
        For Each item In values
            Yield Convert.ChangeType(DirectCast(item, ObservableValue).Value, GetType(T))
        Next
    End Function

    <Extension>
    Public Sub Bind(Of T)(lb As ListBox, source As BindingSource, values As IChartValues)
        source.DataSource = values.ToList(Of T)()
        lb.DataSource = source
    End Sub

End Module

You can download and try out the app:
* WinForm C# Version[^]
* WinForm VB Version[^]
 
Share this answer
 
v9
Comments
Richard Deeming 26-Feb-17 13:14pm    
Pssst... something's gone wrong with your calculations! :)

For an input sequence of {1, 1, 1, 1, 1}:

* the mean is 1;
* for each number, subtract the mean and square the result: (1 - 1)*(1 - 1) = 0*0 = 0;
* the mean of the squared difference is 0;
* the square-root of that is also 0;
* so the standard deviation should be 0, not 1.

:)
Graeme_Grant 26-Feb-17 13:30pm    
Yes, my shortcut in the formula had a flaw. Now corrected and posting correction.
Here's a C# version I knocked up a while back:
C#
public struct StandardDeviationData
{
    private readonly double _sum;
    private readonly double _sumOfSquares;

    private StandardDeviationData(uint count, double sum, double sumOfSquares)
    {
        Count = count;
        _sum = sum;
        _sumOfSquares = sumOfSquares;
    }

    public uint Count { get; }
    
    public double Average => (Count == 0) ? double.NaN : _sum / Count;
    
    // The uncorrected sample standard deviation:
    // https://en.wikipedia.org/wiki/Standard_deviation#Uncorrected_sample_standard_deviation
    public double UncorrectedSampleStandardDeviation
    {
        get
        {
            if (Count == 0) return double.NaN;

            var diff = _sumOfSquares - (_sum * _sum / Count);
            return Math.Sqrt(diff / Count);
        }
    }

    // The corrected sample standard deviation:
    // https://en.wikipedia.org/wiki/Standard_deviation#Corrected_sample_standard_deviation
    public double CorrectedSampleStandardDeviation
    {
        get
        {
            if (Count < 2) return double.NaN;

            var diff = _sumOfSquares - (_sum * _sum / Count);
            return Math.Sqrt(diff / (Count - 1));
        }
    }

    public StandardDeviationData Add(double value)
    {
        return new StandardDeviationData(checked(Count + 1), _sum + value, _sumOfSquares + (value * value));
    }

    public static StandardDeviationData operator +(StandardDeviationData data, double value)
    {
        return data.Add(value);
    }

    public static StandardDeviationData Create(IReadOnlyCollection<double> values)
    {
        double sum = 0, sumOfSquares = 0;
        foreach (double x in values)
        {
            sum += x;
            sumOfSquares += x * x;
        }
        
        return new StandardDeviationData((uint)values.Count, sum, sumOfSquares);
    }
}

public static class Extensions
{
    private static IEnumerable<StandardDeviationData> RollingStandardDeviationIterator(IEnumerable<double> source)
    {
        var result = default(StandardDeviationData);
        foreach (double value in source)
        {
            result += value;
            yield return result;
        }
    }

    public static IEnumerable<StandardDeviationData> RollingStandardDeviation(this IEnumerable<double> source)
    {
        if (source == null) throw new ArgumentNullException(nameof(source));
        return RollingStandardDeviationIterator(source);
    }
    
    public static IEnumerable<StandardDeviationData> RollingStandardDeviation(this IEnumerable<double?> source)
    {
        if (source == null) throw new ArgumentNullException(nameof(source));
        return RollingStandardDeviationIterator(source.Where(n => n != null).Select(n => n.GetValueOrDefault()));
    }
    
    private static IEnumerable<StandardDeviationData> RollingStandardDeviationIterator(IEnumerable<double> source, int windowSize)
    {
        var window = new Queue<double>(windowSize);
        
        foreach (double value in source)
        {
            if (window.Count == windowSize)
            {
                window.Dequeue();
            }
            
            window.Enqueue(value);
            yield return StandardDeviationData.Create(window);
        }
    }

    public static IEnumerable<StandardDeviationData> RollingStandardDeviation(this IEnumerable<double> source, int windowSize)
    {
        if (source == null) throw new ArgumentNullException(nameof(source));
        if (windowSize < 2) throw new ArgumentOutOfRangeException(nameof(windowSize));
        return RollingStandardDeviationIterator(source, windowSize);
    }
    
    public static IEnumerable<StandardDeviationData> RollingStandardDeviation(this IEnumerable<double?> source, int windowSize)
    {
        if (source == null) throw new ArgumentNullException(nameof(source));
        if (windowSize < 2) throw new ArgumentOutOfRangeException(nameof(windowSize));
        return RollingStandardDeviationIterator(source.Where(n => n != null).Select(n => n.GetValueOrDefault()), windowSize);
    }
}

EDIT: Now updated to support a rolling window. And yes, it passes Harold's test[^] from The Lounge. :)
 
Share this answer
 
v3
Comments
Slacker007 24-Feb-17 11:40am    
Why did you uses a struct instead of a class? Just curious. I normally don't put implementation code in my structs, but that is just me.
Richard Deeming 24-Feb-17 11:45am    
To avoid the overhead of creating a new class instance for each item in the source, just to hold two doubles and an int.

It's 20 bytes, so it's technically over the recommended maximum size[^] of 16 bytes. But only just.

And a struct just felt like the right choice. :)
OriginalGriff 24-Feb-17 12:11pm    
To add to what Richard said, it can get complicated:
https://www.codeproject.com/Articles/728836/Using-struct-and-class-whats-that-all-about
Tries to explain.
Jon McKee 24-Feb-17 15:09pm    
Well said in that article :thumbsup:
Graeme_Grant 24-Feb-17 23:44pm    
I like what you have done. The Running calcs look good however when I run it the Windowed results don't meet Harold's test for me:

[edit] removed sample data.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900