Skip to content

Instantly share code, notes, and snippets.

@bicycle1885
Last active August 29, 2015 14:02
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save bicycle1885/15c9e8b5e0638cee9140 to your computer and use it in GitHub Desktop.
Haskell vs. C - variance calculation
#include <stdlib.h>
#include <stdio.h>
// Two-pass algorithm:
// http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Two-pass_algorithm
double var(double* v, size_t n)
{
double mean = 0.0;
for (int i = 0; i < n; i++) {
mean += v[i];
}
mean /= n;
double ssd = 0.0;
for (int i = 0; i < n; i++) {
ssd += (v[i] - mean) * (v[i] - mean);
}
return ssd / (n - 1);
}
int main(int argc, char* argv[])
{
int n = atoi(argv[1]);
double step = 0.1;
double *v;
v = malloc(sizeof(double) * n);
if (!v) {
fprintf(stderr, "failed to allocate memory");
return 1;
}
v[0] = 0.0;
for (int i = 1; i < n; i++) {
v[i] = v[i-1] + step;
}
printf("%d\n", n);
printf("%e\n", var(v, n));
return 0;
}
module Main (main) where
import Prelude hiding (sum, length, zipWith, map)
import System.Environment (getArgs)
import Data.Vector.Unboxed as V
-- | pairwise product
(.*) :: Vector Double -> Vector Double -> Vector Double
x .* y = zipWith (*) x y
-- | sample mean
mean :: Vector Double -> Double
mean v = sum v / fromIntegral (length v)
-- | deviations from the mean
deviation :: Vector Double -> Vector Double
deviation v = map (\x -> x - mean v) v
-- | vectorized square
square :: Vector Double -> Vector Double
square v = v .* v
-- | sum of squared deviations from the mean
ssd :: Vector Double -> Double
ssd = sum . square . deviation
-- | unbiased sample variance
var :: Vector Double -> Double
var v = ssd v / fromIntegral (length v - 1)
main :: IO ()
main = do
(n':_) <- getArgs
let n = read n' :: Int
let v1 = enumFromStepN 0.0 0.1 n
print n
print $ var v1
@bicycle1885
Copy link
Author

  • OS/CPU
    • Mac OS X 10.9.3
    • 2.4 GHz Intel Core i5
  • Haskell
    • GHC 7.8.2
    • ghc -fllvm -O2 variance.hs -o variance-hs
    • vector-0.10.11.0
  • C
    • Clang 3.4
    • clang -O3 variance.c -o variance-c
% cat n
100000000
% time ./variance-hs $(cat n)
100000000
8.333333383502066e12
./variance-hs $(cat n)  0.49s user 0.35s system 99% cpu 0.839 total
% time ./variance-c $(cat n)
100000000
8.333333e+12
./variance-c $(cat n)  0.48s user 0.33s system 98% cpu 0.815 total

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment