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.
Gene McKenna:
On line 14 you have
22 November 2008, 2:07 pm$variance = $MS/$n;
shouldn’t $MS be $M2?
Colin Dean:
You are correct, Gene. That’s what I get for retyping it instead of copy and pasting. Thanks. I fixed it.
22 November 2008, 2:35 pmShane:
I believe (and Excel seems to confirm) that
$variance = $M2/$n
Should be:
$variance = $M2/($n-1);
Std Deviation is the square root of the sum divided by ONE LESS than the count.
30 October 2009, 2:14 pmColin Dean:
Blah. You’re right. I’ve modified it.
2 November 2009, 1:51 pm