Cumulative standard deviation: Difference between revisions
m copy edit - wiki link to wikipedia |
|||
Line 1,267: | Line 1,267: | ||
Uses an object to keep state. |
Uses an object to keep state. |
||
"Simplification of the formula [...] for standard deviation [...] can be memorized as taking the square root of (the average of the squares less the square of the average)." [[ |
"Simplification of the formula [...] for standard deviation [...] can be memorized as taking the square root of (the average of the squares less the square of the average)." [[wp:Standard_deviation#Simplification_of_the_formula|c.f. wikipedia]]. |
||
<lang ruby>class StdDevAccumulator |
<lang ruby>class StdDevAccumulator |
Revision as of 23:03, 11 August 2010
You are encouraged to solve this task according to the task description, using any language you may know.
Write a stateful function, class, generator or coroutine that takes a series of floating point numbers, one at a time, and returns the running standard deviation of the series. The task implementation should use the most natural programming style of those listed for the function in the implementation language; the task must state which is being used. Do not apply Bessel's correction; the returned standard deviation should always be computed as if the sample seen so far is the entire population.
Use this to compute the standard deviation of this demonstration set, , which is .
See also: Moving Average
Ada
<lang ada>with Ada.Numerics.Elementary_Functions; use Ada.Numerics.Elementary_Functions; with Ada.Text_IO; use Ada.Text_IO;
procedure Test_Deviation is
type Sample is record N : Natural := 0; Mean : Float := 0.0; Squares : Float := 0.0; end record; procedure Add (Data : in out Sample; Point : Float) is begin Data.N := Data.N + 1; Data.Mean := Data.Mean + Point; Data.Squares := Data.Squares + Point ** 2; end Add; function Deviation (Data : Sample) return Float is begin return Sqrt (Data.Squares / Float (Data.N) - (Data.Mean / Float (Data.N)) ** 2); end Deviation;
Data : Sample; Test : array (1..8) of Float := (2.0, 4.0, 4.0, 4.0, 5.0, 5.0, 7.0, 9.0);
begin
for Item in Test'Range loop Add (Data, Test (Item)); end loop; Put_Line ("Deviation" & Float'Image (Deviation (Data)));
end Test_Deviation;</lang> Sample output:
Deviation 2.00000E+00
ALGOL 68
Note: the use of a UNION to mimic C's enumerated types is "experimental" and probably not typical of "production code". However it is a example of ALGOL 68s conformity CASE clause useful for classroom dissection. <lang Algol68>MODE VALUE = STRUCT(CHAR value),
STDDEV = STRUCT(CHAR stddev), MEAN = STRUCT(CHAR mean), VAR = STRUCT(CHAR var), COUNT = STRUCT(CHAR count), RESET = STRUCT(CHAR reset);
MODE ACTION = UNION ( VALUE, STDDEV, MEAN, VAR, COUNT, RESET );
LONG REAL sum := 0; LONG REAL sum2 := 0; INT num := 0;
PROC stat object = (LONG REAL v, ACTION action)LONG REAL: (
LONG REAL m; CASE action IN (VALUE):( num +:= 1; sum +:= v; sum2 +:= v*v; stat object(0, LOC STDDEV) ), (STDDEV): long sqrt(stat object(0, LOC VAR)), (MEAN): IF num>0 THEN sum/LONG REAL(num) ELSE 0 FI, (VAR):( m := stat object(0, LOC MEAN); IF num>0 THEN sum2/LONG REAL(num)-m*m ELSE 0 FI ), (COUNT): num, (RESET): sum := sum2 := num := 0 ESAC
);
[]LONG REAL v = ( 2,4,4,4,5,5,7,9 );
main: (
LONG REAL sd; FOR i FROM LWB v TO UPB v DO sd := stat object(v[i], LOC VALUE) OD; printf(($"standard dev := "g(0,6)l$, sd))
)</lang>Output:
standard dev := 2.000000
A code sample in an object oriented style: <lang Algol68>MODE STAT = STRUCT(
LONG REAL sum, LONG REAL sum2, INT num
);
OP INIT = (REF STAT new)REF STAT:
(init OF class stat)(new);
MODE CLASSSTAT = STRUCT(
PROC (REF STAT, LONG REAL #value#)VOID plusab, PROC (REF STAT)LONG REAL stddev, mean, variance, count, PROC (REF STAT)REF STAT init
);
CLASSSTAT class stat;
plusab OF class stat := (REF STAT self, LONG REAL value)VOID:(
num OF self +:= 1; sum OF self +:= value; sum2 OF self +:= value*value );
OP +:= = (REF STAT lhs, LONG REAL rhs)VOID: # some syntatic sugar #
(plusab OF class stat)(lhs, rhs);
stddev OF class stat := (REF STAT self)LONG REAL:
long sqrt((variance OF class stat)(self));
OP STDDEV = ([]LONG REAL value)LONG REAL: ( # more syntatic sugar #
REF STAT stat = INIT LOC STAT; FOR i FROM LWB value TO UPB value DO stat +:= value[i] OD; (stddev OF class stat)(stat)
);
mean OF class stat := (REF STAT self)LONG REAL:
sum OF self/LONG REAL(num OF self);
variance OF class stat := (REF STAT self)LONG REAL:(
LONG REAL m = (mean OF class stat)(self); sum2 OF self/LONG REAL(num OF self)-m*m );
count OF class stat := (REF STAT self)LONG REAL:
num OF self;
init OF class stat := (REF STAT self)REF STAT:(
sum OF self := sum2 OF self := num OF self := 0; self );
[]LONG REAL value = ( 2,4,4,4,5,5,7,9 );
main: (
printf(($"standard deviation operator = "g(0,6)l$, STDDEV value));
REF STAT stat = INIT LOC STAT;
FOR i FROM LWB value TO UPB value DO stat +:= value[i] OD; printf(($"standard deviation = "g(0,6)l$, (stddev OF class stat)(stat))); printf(($"mean = "g(0,6)l$, (mean OF class stat)(stat))); printf(($"variance = "g(0,6)l$, (variance OF class stat)(stat))); printf(($"count = "g(0,6)l$, (count OF class stat)(stat)))
)</lang>Output:
standard deviation operator = 2.000000 standard deviation = 2.000000 mean = 5.000000 variance = 4.000000 count = 8.000000
A simple - but "unpackaged" - code example, useful if the standard deviation is required on only one set of concurrent data: <lang Algol68>LONG REAL sum, sum2; INT n;
PROC sd = (LONG REAL x)LONG REAL:(
sum +:= x; sum2 +:= x*x; n +:= 1; IF n = 0 THEN 0 ELSE long sqrt(sum2/n - sum*sum/n/n) FI
);
sum := sum2 := n := 0; []LONG REAL values = (2,4,4,4,5,5,7,9); FOR i TO UPB values DO
LONG REAL value = values[i]; printf(($2(xg(0,6))l$, value, sd(value)))
OD</lang>Output:
2.000000 .000000 4.000000 1.000000 4.000000 .942809 4.000000 .866025 5.000000 .979796 5.000000 1.000000 7.000000 1.399708 9.000000 2.000000
AutoHotkey
ahk forum: discussion <lang AutoHotkey>std(2),std(4),std(4),std(4),std(5),std(5),std(7) MsgBox % std(9) ; 2
std(x="") {
Static sum:=0, sqr:=0, n:=0 If (x="") ; blank parameter: reset sum := 0, sqr := 0, n := 0 Else sum += x, sqr += x*x, n++ ; update state Return sqrt((sqr-sum*sum/n)/n)
}</lang>
C
<lang c>#include <stdio.h>
- include <stdlib.h>
- include <math.h>
enum Action { STDDEV, MEAN, VAR, COUNT };
typedef struct stat_obj_struct {
double sum, sum2; size_t num; Action action;
} sStatObject, *StatObject;
StatObject NewStatObject( Action action ) {
so = malloc(sizeof(sStatObject)); so->sum = 0.0; so->sum2 = 0.0; so->num = 0; so->action = action; return so;
}
- define FREE_STAT_OBJECT(so) \
free(so); so = NULL
double stat_obj_value(StatObject so, Action action) {
double num, mean, var, stddev; if (so->num == 0.0) return 0.0; num = so->num; if (action==COUNT) return num; mean = so->sum/num; if (action==MEAN) return mean; var = so->sum2/num - mean*mean; if (action==VAR) return var; stddev = sqrt(var); if (action==STDDEV) return stddev; return 0;
}
double stat_object_add(StatObject so, double v) {
so->num++; so->sum += v; so->sum2 += v*v; return stat_obj_value(so->action);
}</lang>
<lang c>double v[] = { 2,4,4,4,5,5,7,9 };
int main() {
int i; StatObject so = NewStatObject( STDDEV );
for(i=0; i < sizeof(v)/sizeof(double) ; i++) printf("val: %lf std dev: %lf\n", v[i], stat_object_add(so, v[i]));
FREE_STAT_OBJECT(so); return 0;
}</lang>
C++
<lang cpp>#include <algorithm>
- include <iostream>
- include <iterator>
- include <cmath>
- include <vector>
- include <iterator>
- include <numeric>
template <typename Iterator> double standard_dev( Iterator begin , Iterator end ) {
double mean = std::accumulate( begin , end , 0 ) / std::distance( begin , end ) ; std::vector<double> squares ; for( Iterator vdi = begin ; vdi != end ; vdi++ ) squares.push_back( std::pow( *vdi - mean , 2 ) ) ; return std::sqrt( std::accumulate( squares.begin( ) , squares.end( ) , 0 ) / squares.size( ) ) ;
}
int main( ) {
double demoset[] = { 2 , 4 , 4 , 4 , 5 , 5 , 7 , 9 } ; int demosize = sizeof demoset / sizeof *demoset ; std::cout << "The standard deviation of\n" ; std::copy( demoset , demoset + demosize , std::ostream_iterator<double>( std::cout, " " ) ) ; std::cout << "\nis " << standard_dev( demoset , demoset + demosize ) << " !\n" ; return 0 ;
}</lang>
C#
<lang csharp>using System; using System.Collections.Generic; using System.Linq;
namespace standardDeviation {
class Program { static void Main(string[] args) { List<double> nums = new List<double> { 2, 4, 4, 4, 5, 5, 7, 9 }; for (int i = 1; i <= nums.Count; i++) Console.WriteLine(sdev(nums.GetRange(0, i))); }
static double sdev(List<double> nums) { List<double> store = new List<double>(); foreach (double n in nums) store.Add((n - nums.Average()) * (n - nums.Average()));
return Math.Sqrt(store.Sum() / store.Count); } }
}</lang>
0 1 0,942809041582063 0,866025403784439 0,979795897113271 1 1,39970842444753 2
Clojure
<lang lisp> (defn std-dev [samples]
(let [n (count samples)
mean (/ (reduce + samples) n) intermediate (map #(Math/pow (- %1 mean) 2) samples)]
(Math/sqrt (/ (reduce + intermediate) n))))
(println (std-dev [2 4 4 4 5 5 7 9])) ;;2.0
</lang>
Common Lisp
Based on some googled web site; written ages ago.
<lang lisp>(defun arithmetic-average (samples)
(/ (reduce #'+ samples) (length samples)))
(defun standard-deviation (samples)
(let ((mean (arithmetic-average samples))) (sqrt (* (/ 1.0d0 (length samples)) (reduce #'+ samples :key (lambda (x) (expt (- x mean) 2)))))))
(defun make-deviator ()
(let ((numbers '())) (lambda (x) (push x numbers) (standard-deviation numbers))))</lang>
<lang lisp>CL-USER> (loop with deviator = (make-deviator)
for i in '(2 4 4 4 5 5 7 9) collect (list i (funcall deviator i))) ==>
((2 0.0d0)
(4 1.0d0) (4 0.9428090415820634d0) (4 0.8660254037844386d0) (5 0.9797958971132713d0) (5 1.0d0) (7 1.3997084244475304d0) (9 2.0d0))</lang>
D
<lang d>import std.math; import std.stdio; class StdDev {
real values = 0; real sum = 0; real sqsum = 0; void addNumber(real input) { values++; sum += input; sqsum += input*input; } void addNumbers(real[]input) { foreach(num;input) { addNumber(num); } } real getStdDev() { if(!values) return 0; real mean = sum/values; return sqrt(sqsum/values - mean*mean); }
} void main() {
real[]elements = [2,4,4,4,5,5,7,9]; auto stdev = new StdDev; foreach(ele;elements) { stdev.addNumber(ele); writefln("%e",stdev.getStdDev); }
}</lang>
E
This implementation produces two (function) objects sharing state. It is idiomatic in E to separate input from output (read from write) rather than combining them into one object.
The algorithm is
and the results were checked against #Python.
<lang e>def makeRunningStdDev() {
var sum := 0.0 var sumSquares := 0.0 var count := 0.0 def insert(v) { sum += v sumSquares += v ** 2 count += 1 } /** Returns the standard deviation of the inputs so far, or null if there have been no inputs. */ def stddev() { if (count > 0) { def meanSquares := sumSquares/count def mean := sum/count def variance := meanSquares - mean**2 return variance.sqrt() } } return [insert, stddev]
}</lang>
<lang e>? def [insert, stddev] := makeRunningStdDev()
- value: <insert>, <stddev>
? [stddev()]
- value: [null]
? for value in [2,4,4,4,5,5,7,9] { > insert(value) > println(stddev()) > } 0.0 1.0 0.9428090415820626 0.8660254037844386 0.9797958971132716 1.0 1.3997084244475297 2.0</lang>
Factor
<lang factor>USING: accessors io kernel math math.functions math.parser sequences ; IN: standard-deviator
TUPLE: standard-deviator sum sum^2 n ;
- <standard-deviator> ( -- standard-deviator )
0.0 0.0 0 standard-deviator boa ;
- current-std ( standard-deviator -- std )
[ [ sum^2>> ] [ n>> ] bi / ] [ [ sum>> ] [ n>> ] bi / sq ] bi - sqrt ;
- add-value ( value standard-deviator -- )
[ nip [ 1 + ] change-n drop ] [ [ + ] change-sum drop ] [ [ [ sq ] dip + ] change-sum^2 drop ] 2tri ;
- main ( -- )
{ 2 4 4 4 5 5 7 9 } <standard-deviator> [ [ add-value ] curry each ] keep current-std number>string print ;</lang>
Forth
<lang forth>: f+! ( x addr -- ) dup f@ f+ f! ;
- st-count ( stats -- n ) f@ ;
- st-sum ( stats -- sum ) float+ f@ ;
- st-sumsq ( stats -- sum*sum ) 2 floats + f@ ;
- st-add ( fnum stats -- )
1e dup f+! float+ fdup dup f+! float+ fdup f* f+! ;
- st-mean ( stats -- mean )
dup st-sum st-count f/ ;
- st-variance ( stats -- var )
dup st-sumsq dup st-mean fdup f* dup st-count f* f- st-count f/ ;
- st-stddev ( stats -- stddev )
st-variance fsqrt ;</lang>
This variation is more numerically stable when there are large numbers of samples or large sample ranges. <lang forth>: st-count ( stats -- n ) f@ ;
- st-mean ( stats -- mean ) float+ f@ ;
- st-nvar ( stats -- n*var ) 2 floats + f@ ;
- st-variance ( stats -- var ) dup st-nvar st-count f/ ;
- st-stddev ( stats -- stddev ) st-variance fsqrt ;
- st-add ( x stats -- )
1e dup f+! \ update count fdup dup st-mean f- fswap ( delta x ) fover dup st-count f/ ( delta x delta/n ) float+ dup f+! \ update mean ( delta x ) dup f@ f- f* float+ f+! ; \ update nvar</lang>
<lang forth>create stats 0e f, 0e f, 0e f,
2e stats st-add 4e stats st-add 4e stats st-add 4e stats st-add 5e stats st-add 5e stats st-add 7e stats st-add 9e stats st-add
stats st-stddev f. \ 2.</lang>
Fortran
This one imitates C and suffers the same problems: the function is not thread-safe and must be used to compute the stddev for one set per time.
<lang fortran>program Test_Stddev
implicit none
real, dimension(8) :: v = (/ 2,4,4,4,5,5,7,9 /) integer :: i real :: sd
do i = 1, size(v) sd = stat_object(v(i)) end do
print *, "std dev = ", sd
contains
recursive function stat_object(a, cmd) result(stddev) real :: stddev real, intent(in) :: a character(len=*), intent(in), optional :: cmd
real, save :: summa = 0.0, summa2 = 0.0 integer, save :: num = 0
real :: m
if ( .not. present(cmd) ) then num = num + 1 summa = summa + a summa2 = summa2 + a*a stddev = stat_object(0.0, "stddev") else select case(cmd) case("stddev") stddev = sqrt(stat_object(0.0, "variance")) case("variance") m = stat_object(0.0, "mean") if ( num > 0 ) then stddev = summa2/real(num) - m*m else stddev = 0.0 end if case("count") stddev = real(num) case("mean") if ( num > 0 ) then stddev = summa/real(num) else stddev = 0.0 end if case("reset") summa = 0.0 summa2 = 0.0 num = 0 case default stddev = 0.0 end select end if
end function stat_object
end program Test_Stddev</lang>
Using built-in array awareness
This uses Fortran's built-in array features (which aren't available in C)
<lang fortran> program stats
implicit none
integer, parameter :: N = 8 integer :: data(N) real(8) :: mean real(8) :: std_dev1, std_dev2
! Set the data data = [2,4,4,4,5,5,7,9] ! Strictly this is a Fortran 2003 construct
! Use intrinsic function 'sum' to calculate the mean mean = sum(data)/N
! Method1: ! Calculate the standard deviation directly from the definition std_dev1 = sqrt(sum((data - mean)**2)/N)
! Method 2: ! Use the alternative version that is less susceptible to rounding error std_dev2 = sqrt(sum(data**2)/N - mean**2)
write(*,'(a,8i2)') 'Data = ',data write(*,'(a,f3.1)') 'Mean = ',mean write(*,'(a,f3.1)') 'Standard deviation (method 1) = ',std_dev1 write(*,'(a,f3.1)') 'Standard deviation (method 2) = ',std_dev2
end program stats </lang>
Haskell
We store the state in the ST
monad using an STRef
.
<lang haskell>import Data.List (genericLength) import Data.STRef import Control.Monad.ST
sd :: [Double] -> Double sd l = sqrt $ sum (map ((^2) . subtract mean) l) / n
where n = genericLength l mean = sum l / n
sdAccum :: ST s (Double -> ST s Double) sdAccum = do
accum <- newSTRef [] return $ \x -> do modifySTRef accum (x:) list <- readSTRef accum return $ sd list
main = mapM_ print results
where results = runST $ do runningSD <- sdAccum mapM runningSD [2, 4, 4, 4, 5, 5, 7, 9]</lang>
HicEst
<lang HicEst>REAL :: n=8, set(n), sum=0, sum2=0
set = (2,4,4,4,5,5,7,9)
DO k = 1, n
WRITE() 'Adding ' // set(k) // 'stdev = ' // stdev(set(k))
ENDDO
END ! end of "main"
FUNCTION stdev(x)
USE : sum, sum2, k sum = sum + x sum2 = sum2 + x*x stdev = ( sum2/k - (sum/k)^2) ^ 0.5 END</lang>
Adding 2 stdev = 0 Adding 4 stdev = 1 Adding 4 stdev = 0.9428090416 Adding 4 stdev = 0.8660254038 Adding 5 stdev = 0.9797958971 Adding 5 stdev = 1 Adding 7 stdev = 1.399708424 Adding 9 stdev = 2
J
J is block-oriented; it expresses algorithms with the semantics of all the data being available at once. It does not have native lexical closure or coroutine semantics. It is possible to implement these semantics in J; see Moving Average for an example. We will not reprise that here. <lang j> mean=: +/ % #
dev=: - mean stddevP=: [: %:@mean *:@dev NB. A) 3 equivalent defs for stddevP stddevP=: [: mean&.:*: dev NB. B) uses Under (&.:) to apply inverse of *: after mean stddevP=: %:@(mean@:*: - *:@mean) NB. C) sqrt of ((mean of squares) - (square of mean))
stddevP\ 2 4 4 4 5 5 7 9
0 1 0.942809 0.866025 0.979796 1 1.39971 2</lang>
Alternatives:
Using verbose names for J primitives.
<lang j> of =: @:
sqrt =: %: sum =: +/ squares=: *: data =: ] mean =: sum % #
stddevP=: sqrt of mean of squares of (data-mean)
stddevP\ 2 4 4 4 5 5 7 9
0 1 0.942809 0.866025 0.979796 1 1.39971 2</lang>
Or we could take a cue from the R implementation and reverse the Bessel correction to stddev:
<lang j> require'stats'
(%:@:(%~<:)@:# * stddev)\ 2 4 4 4 5 5 7 9
0 1 0.942809 0.866025 0.979796 1 1.39971 2</lang>
Java
<lang java5>import java.util.LinkedList; public class StdDev {
LinkedList<Double> nums; public StdDev() { nums = new LinkedList<Double>(); } public static void main(String[] args) { double[] testData = {2,4,4,4,5,5,7,9}; StdDev sd = new StdDev(); for (double x : testData) { sd.newNum(x); System.out.println(sd.getSD()); } } public void newNum(double num) { nums.add(num); } public double getAvg() { if (nums.isEmpty()) return 0; double ret = 0; double sum = 0; for (double num : nums) { sum += num; } return sum / nums.size(); } public double getSD() { double sqDiffs = 0; double avg = getAvg(); for (double num : nums) { sqDiffs += (num - avg) * (num - avg); } return Math.sqrt(sqDiffs / nums.size()); }
}</lang>
JavaScript
Uses a closure. <lang javascript>function running_stddev() {
var n = 0; var sum = 0.0; var sum_sq = 0.0; return function(num) { n++; sum += num; sum_sq += num*num; return Math.sqrt( (sum_sq / n) - Math.pow(sum / n, 2) ); }
}
var sd = running_stddev(); var nums = [2,4,4,4,5,5,7,9]; var stddev = []; for (var i in nums)
stddev.push( sd(nums[i]) );
// using WSH WScript.Echo(stddev.join(', ');</lang>
output:
0, 1, 0.942809041582063, 0.866025403784439, 0.979795897113273, 1, 1.39970842444753, 2
lua
Uses a closure. Translation of JavaScript. <lang lua>function stdev()
local sum, sumsq, k = 0,0,0 return function(n) sum, sumsq, k = sum + n, sumsq + n^2, k+1 return math.sqrt((sumsq / k) - (sum/k)^2) end
end
ldev = stdev() for i, v in ipairs{2,4,4,4,5,5,7,9} do
print(ldev(v))
end</lang>
Objective-C
<lang objc>#import <stdio.h>
- import <math.h>
- import <objc/Object.h>
@interface SDAccum : Object {
double sum, sum2; unsigned int num;
} -(id)init; -(double)value: (double)v; -(unsigned int)count; -(double)mean; -(double)variance; -(double)stddev; @end
@implementation SDAccum -(id)init {
sum = sum2 = 0.0; num = 0; return self;
} -(double)value: (double)v {
sum = sum + v; sum2 = sum2 + v*v; num++; return [self stddev];
} -(unsigned int)count {
return num;
} -(double)mean {
return (num>0) ? sum/(double)num : 0.0;
} -(double)variance {
double m = [self mean]; return (num>0) ? (sum2/(double)num - m*m) : 0.0;
} -(double)stddev {
return sqrt([self variance]);
} @end</lang>
<lang objc>double v[] = { 2,4,4,4,5,5,7,9 };
int main() {
int i; double sd;
id sdacc = [SDAccum new];
for(i=0; i < sizeof(v)/sizeof(double) ; i++) sd = [sdacc value: v[i]];
printf("std dev = %lf\n", sd);
return 0;
}</lang>
OCaml
<lang ocaml>let sqr x = x *. x
let stddev l =
let n, sx, sx2 = List.fold_left (fun (n, sx, sx2) x -> succ n, sx +. x, sx2 +. sqr x) (0, 0., 0.) l in sqrt ((sx2 -. sqr sx /. float n) /. float n)
let _ =
let l = [ 2.;4.;4.;4.;5.;5.;7.;9. ] in Printf.printf "List: "; List.iter (Printf.printf "%g ") l; Printf.printf "\nStandard deviation: %g\n" (stddev l)</lang>
Sample output:
List: 2 4 4 4 5 5 7 9 Standard deviation: 2
Perl
<lang perl>{
package SDAccum; sub new {
my $class = shift; my $self = {}; $self->{sum} = 0.0; $self->{sum2} = 0.0; $self->{num} = 0; bless $self, $class; return $self;
} sub count {
my $self = shift; return $self->{num};
} sub mean {
my $self = shift; return ($self->{num}>0) ? $self->{sum}/$self->{num} : 0.0;
} sub variance {
my $self = shift; my $m = $self->mean; return ($self->{num}>0) ? $self->{sum2}/$self->{num} - $m * $m : 0.0;
} sub stddev {
my $self = shift; return sqrt($self->variance);
} sub value {
my $self = shift; my $v = shift; $self->{sum} += $v; $self->{sum2} += $v * $v; $self->{num}++; return $self->stddev;
}
}</lang>
<lang perl>my $sdacc = SDAccum->new; my $sd;
foreach my $v ( 2,4,4,4,5,5,7,9 ) {
$sd = $sdacc->value($v);
} print "std dev = $sd\n";</lang>
Perl 6
<lang perl6>sub sd (@a) {
my $mean = ([+] @a) / @a; sqrt ([+] map { ($^x - $mean)**2 }, @a) / @a;
}
sub sdaccum {
my @a; return { push @a, $^x; sd @a; };
};
&f = sdaccum; say f $_ for 2, 4, 4, 4, 5, 5, 7, 9;</lang>
PL/I
<lang PL/I> declare A(200) float; declare ap fixed binary; declare i fixed binary;
ap = 0; do i = 1 to 10;
ap = ap + 1; get list ( A(ap) ); put skip list ( std_dev (a, ap) );
end;
std_dev: procedure (A, ap) returns (float);
declare A(*) float, ap fixed binary nonassignable; declare i fixed binary; declare B(ap) float, average float;
do i = 1 to ap; B(i) = A(i); end; average = sum(A) /ap;
return ( sqrt (sum(B**2)/ap - average**2) );
end std_dev; </lang>
PicoLisp
<lang PicoLisp>(scl 2)
(de stdDev ()
(let Data NIL (curry (Data) (N) (push 'Data N) (let (Len (length Data) M (*/ (apply + Data) Len)) (sqrt (*/ (sum '((N) (*/ (- N M) (- N M) 1.0)) Data ) 1.0 Len ) T ) ) ) ) )
(let Fun (stdDev)
(for N (2.0 4.0 4.0 4.0 5.0 5.0 7.0 9.0) (prinl (format N *Scl) " -> " (format (Fun N) *Scl)) ) )</lang>
Output:
2.00 -> 0.00 4.00 -> 1.00 4.00 -> 0.94 4.00 -> 0.87 5.00 -> 0.98 5.00 -> 1.00 7.00 -> 1.40 9.00 -> 2.00
PowerShell
This implementation takes the form of an advanced function which can act like a cmdlet and receive input from the pipeline. <lang powershell>function Get-StandardDeviation {
begin { $avg = 0 $nums = @() } process { $nums += $_ $avg = ($nums | Measure-Object -Average).Average $sum = 0; $nums | ForEach-Object { $sum += ($avg - $_) * ($avg - $_) } [Math]::Sqrt($sum / $nums.Length) }
}</lang> Usage as follows:
PS> 2,4,4,4,5,5,7,9 | Get-StandardDeviation 0 1 0.942809041582063 0.866025403784439 0.979795897113271 1 1.39970842444753 2
PureBasic
<lang PureBasic>;Define our Standard deviation function Declare.d Standard_deviation(x)
- Main program
If OpenConsole()
Define i, x Restore MyList For i=1 To 8 Read.i x PrintN(StrD(Standard_deviation(x))) Next i Print(#CRLF$+"Press ENTER to exit"): Input()
EndIf
- Calculation procedure, with memory
Procedure.d Standard_deviation(In)
Static in_summa, antal Static in_kvadrater.q in_summa+in in_kvadrater+in*in antal+1 ProcedureReturn Pow((in_kvadrater/antal)-Pow(in_summa/antal,2),0.50)
EndProcedure
- data section
DataSection MyList:
Data.i 2,4,4,4,5,5,7,9
EndDataSection</lang>
Outputs
0.0000000000 1.0000000000 0.9428090416 0.8660254038 0.9797958971 1.0000000000 1.3997084244 2.0000000000
Python
Using a function with attached properties
The program should work with Python 2.x and 3.x, although the output would not be a tuple in 3.x <lang python>>>> from math import sqrt >>> def sd(x):
sd.sum += x sd.sum2 += x*x sd.n += 1.0 sum, sum2, n = sd.sum, sd.sum2, sd.n return sqrt(sum2/n - sum*sum/n/n)
>>> sd.sum = sd.sum2 = sd.n = 0 >>> for value in (2,4,4,4,5,5,7,9):
print (value, sd(value))
(2, 0.0)
(4, 1.0)
(4, 0.94280904158206258)
(4, 0.8660254037844386)
(5, 0.97979589711327075)
(5, 1.0)
(7, 1.3997084244475311)
(9, 2.0)
>>></lang>
Using a class instance
<lang python>>>> class SD(object): # Plain () for python 3.x def __init__(self): self.sum, self.sum2, self.n = (0,0,0) def sd(self, x): self.sum += x self.sum2 += x*x self.n += 1.0 sum, sum2, n = self.sum, self.sum2, self.n return sqrt(sum2/n - sum*sum/n/n)
>>> sd_inst = SD() >>> for value in (2,4,4,4,5,5,7,9): print (value, sd_inst.sd(value))</lang>
Using a Closure
<lang python>>>> from math import sqrt >>> def sdcreator(): sum = sum2 = n = 0 def sd(x): nonlocal sum, sum2, n
sum += x sum2 += x*x n += 1.0 return sqrt(sum2/n - sum*sum/n/n) return sd
>>> sd = sdcreator() >>> for value in (2,4,4,4,5,5,7,9): print (value, sd(value))
2 0.0
4 1.0
4 0.942809041582
4 0.866025403784
5 0.979795897113
5 1.0
7 1.39970842445
9 2.0</lang>
R
Built-in Std Dev fn
<lang R>#The built-in standard deviation function applies the Bessel correction. To reverse this, we can apply an uncorrection.
- If na.rm is true, missing data points (NA values) are removed.
reverseBesselCorrection <- function(x, na.rm=FALSE) { if(na.rm) x <- x[!is.na(x)] len <- length(x) if(len < 2) stop("2 or more data points required") sqrt((len-1)/len) } testdata <- c(2,4,4,4,5,5,7,9) reverseBesselCorrection(testdata)*sd(testdata) #2</lang>
From scratch
<lang R>#Again, if na.rm is true, missing data points (NA values) are removed.
uncorrectedsd <- function(x, na.rm=FALSE) { len <- length(x) if(len < 2) stop("2 or more data points required") mu <- mean(x, na.rm=na.rm) ssq <- sum((x - mu)^2, na.rm=na.rm) usd <- sqrt(ssq/len) usd } uncorrectedsd(testdata) #2</lang>
REXX
This is indeed Object REXX.
<lang rexx>sdacc = .SDAccum~new x = .array~of(2,4,4,4,5,5,7,9) sd = 0 do i = 1 to x~size
sd = sdacc~value(x[i])
end
say "std dev = "sd
- class SDAccum
- method sum attribute
- method sum2 attribute
- method count attribute
- method init
self~sum = 0.0 self~sum2 = 0.0 self~count = 0
- method value
expose sum sum2 count parse arg x sum = sum + x sum2 = sum2 + x*x count = count + 1 return self~stddev
- method mean
expose sum count return sum/count
- method variance
expose sum2 count m = self~mean return sum2/count - m*m
- method stddev
return self~sqrt(self~variance)
- method sqrt
arg n if n = 0 then return 0 ans = n / 2 prev = n do until prev = ans prev = ans ans = ( prev + ( n / prev ) ) / 2 end return ans</lang>
Ruby
Object
Uses an object to keep state.
"Simplification of the formula [...] for standard deviation [...] can be memorized as taking the square root of (the average of the squares less the square of the average)." c.f. wikipedia.
<lang ruby>class StdDevAccumulator
def initialize @n, @sum, @sumofsquares = 0, 0.0, 0.0 end def <<(num) # return self to make this possible: sd << 1 << 2 << 3 # => 0.816496580927726 @n += 1 @sum += num @sumofsquares += num**2 self end def stddev Math.sqrt( (@sumofsquares / @n) - (@sum / @n)**2 ) end def to_s stddev.to_s end
end
sd = StdDevAccumulator.new i = 0 [2,4,4,4,5,5,7,9].each {|n| puts "adding #{n}: stddev of #{i+=1} samples is #{sd << n}" }</lang>
adding 2: stddev of 1 samples is 0.0 adding 4: stddev of 2 samples is 1.0 adding 4: stddev of 3 samples is 0.942809041582063 adding 4: stddev of 4 samples is 0.866025403784439 adding 5: stddev of 5 samples is 0.979795897113272 adding 5: stddev of 6 samples is 1.0 adding 7: stddev of 7 samples is 1.39970842444753 adding 9: stddev of 8 samples is 2.0
Closure
<lang ruby>def sdaccum
n, sum, sum2 = 0, 0.0, 0.0 lambda do |num| n += 1 sum += num sum2 += num**2 Math.sqrt( (sum2 / n) - (sum / n)**2 ) end
end
sd = sdaccum [2,4,4,4,5,5,7,9].each {|n| print sd.call(n), ", "}</lang>
0.0, 1.0, 0.942809041582063, 0.866025403784439, 0.979795897113272, 1.0, 1.39970842444753, 2.0,
Scheme
<lang scheme> (define ((running-stddev . nums) num)
(set! nums (cons num nums)) (sqrt (- (/ (apply + (map (lambda (i) (* i i)) nums)) (length nums)) (expt (/ (apply + nums) (length nums)) 2))))
</lang>
Smalltalk
<lang smalltalk>Object subclass: SDAccum [
|sum sum2 num| SDAccum class >> new [ |o| o := super basicNew. ^ o init. ] init [ sum := 0. sum2 := 0. num := 0 ] value: aValue [ sum := sum + aValue. sum2 := sum2 + ( aValue * aValue ). num := num + 1. ^ self stddev ] count [ ^ num ] mean [ num>0 ifTrue: [^ sum / num] ifFalse: [ ^ 0.0 ] ] variance [ |m| m := self mean. num>0 ifTrue: [^ (sum2/num) - (m*m) ] ifFalse: [ ^ 0.0 ] ] stddev [ ^ (self variance) sqrt ]
].</lang>
<lang smalltalk>|sdacc sd| sdacc := SDAccum new.
- ( 2 4 4 4 5 5 7 9 ) do: [ :v | sd := sdacc value: v ].
('std dev = %1' % { sd }) displayNl.</lang>
Tcl
With a Class
<lang tcl>oo::class create SDAccum {
variable sum sum2 num constructor {} { set sum 0.0 set sum2 0.0 set num 0 } method value {x} { set sum2 [expr {$sum2 + $x**2}] set sum [expr {$sum + $x}] incr num return [my stddev] } method count {} { return $num } method mean {} { expr {$sum / $num} } method variance {} { expr {$sum2/$num - [my mean]**2} } method stddev {} { expr {sqrt([my variance])} }
}
- Demonstration
set sdacc [SDAccum new] foreach val {2 4 4 4 5 5 7 9} {
set sd [$sdacc value $val]
} puts "the standard deviation is: $sd"</lang> which produces the output:
the standard deviation is: 2.0
With a Coroutine
<lang tcl># Make a coroutine out of a lambda application coroutine sd apply {{} {
set sum 0.0 set sum2 0.0 set sd {} # Keep processing argument values until told not to... while {[set val [yield $sd]] ne "stop"} { incr n set sum [expr {$sum + $val}] set sum2 [expr {$sum2 + $val**2}] set sd [expr {sqrt($sum2/$n - ($sum/$n)**2)}] }
}}
- Demonstration
foreach val {2 4 4 4 5 5 7 9} {
set sd [sd $val]
} sd stop puts "the standard deviation is: $sd"</lang>