Single-pass standard deviation in PHP
I recently had a need for a standard deviation function for a project. It wasn’t until after I’d already implemented it that I discovered the existence of a virtually-undocumented stats_standard_deviation() in PHP’s Statistics package.
Anyway, I did some research and found Don Knuth’s on-line, single-pass standard deviation function and implemented it in PHP.
<?php
function stddev($array){
//Don Knuth is the $deity of algorithms
//http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#III._On-line_algorithm
$n = 0;
$mean = 0;
$M2 = 0;
foreach($array as $x){
$n++;
$delta = $x - $mean;
$mean = $mean + $delta/$n;
$M2 = $M2 + $delta*($x - $mean);
}
$variance = $M2/($n - 1);
return sqrt($variance);
}
?>Please note that there are more efficient ways of doing this if you have have written a mean() or variance() function, as you should. There’s also a stats_variance() function in PHP.
I think I might do some serious benchmarking with PHP’s implementation of stddev and mine and see which is faster. I’ll be that the PHP one is faster because it’s written in C and mine’s being interpreted at runtime.
Update 19:40 stats is undocumented because it’s a PECL extension which isn’t included by default, and it’s not terribly clear to install. Install php-dev then use pecl install stats to get it. Don’t forget to sudo if you need to.
Update 2009/11/02 14:52 I had a missing -1 on the variance calculation for nearly a year and finally someone caught it. Thanks, Shane.
