Fast Standard Deviation

using System;

using System.Linq;

using System.Collections.Generic;

public static class Utils {

public static double GetStandardDeviation(this IEnumerable<int> values)

{

double standardDeviation = 0;

int[] enumerable = values as int[] ?? values.ToArray();

int count = enumerable.Count();

if (count > 1)

{

double avg = enumerable.Average();

double sum = enumerable.Sum(d => (d - avg) * (d - avg));

standardDeviation = Math.Sqrt(sum / count);

}

return standardDeviation;

}

class Tuple3<X, Y, Z> {

public Tuple3(X x, Y y, Z z) {

this.Item1 = x;

this.Item2 = y;

this.Item3 = z;

}

public static Tuple3<X, Y, Z> Create(X x, Y y, Z z) {

return new Tuple3<X, Y, Z>(x, y, z);

}

public X Item1;

public Y Item2;

public Z Item3;

}

public static Tuple<Double, Double, Double> FastStandardDeviation(this IEnumerable<int> values) {

var res = values.Aggregate(Tuple3<Double, Double, Double>.Create(0d, 0d, 0d), (tup, a) => {

var n = tup.Item1 + 1;

var delta = a - tup.Item2;

var mean = tup.Item2 + delta / n;

var delta2 = a - mean;

var m2 = tup.Item3 + delta * delta2;

tup.Item1 = n;

tup.Item2 = mean;

tup.Item3 = m2;

return tup;

});

return Tuple.Create(res.Item1, res.Item2, Math.Sqrt(res.Item3 / res.Item1));

}

public static Tuple<Double, Double, Double> FastStandardDeviationWithTupleCreate(this IEnumerable<int> values) {

var res = values.Aggregate(Tuple.Create(0d, 0d, 0d), (tup, a) => {

var n = tup.Item1 + 1;

var delta = a - tup.Item2;

var mean = tup.Item2 + delta / n;

var delta2 = a - mean;

var m2 = tup.Item3 + delta * delta2;

return Tuple.Create(n, mean, m2);

});

return Tuple.Create(res.Item1, res.Item2, Math.Sqrt(res.Item3 / res.Item1));

}

}

public static class UtilsT<T> {

public static Tuple<long, T> Time(Func<T> act) {

var watch = System.Diagnostics.Stopwatch.StartNew();

var t = act();

watch.Stop();

return Tuple.Create(watch.ElapsedMilliseconds, t);

}

}

class MainClass {

static void Main() {

var rand = new Random();

var nums = Enumerable.Range(1, 10000000).Select(_ => rand.Next(1000));

var slow = UtilsT<Double>.Time(nums.GetStandardDeviation);

Console.WriteLine("Slow Method, Result = {0}, Time = {1}", slow.Item2, slow.Item1);

var fast = UtilsT<Tuple<Double, Double, Double>>.Time(nums.FastStandardDeviation);

Console.WriteLine("Fast Method, Result = {0}, Time = {1}", fast.Item2.Item3, fast.Item1);

}

}