Content deleted Content added
→Algorithms for variance: new section |
|||
Line 20:
:: A very slightly more complicated example is computing an average. You can keep track of a sum and a count and can combine two partial results by adding the sum and the count. A more complicated example is computing the standard deviation of a bunch of numbers. It is definately possible to compute this as an online algorithm, as shown in [[Algorithms for calculating variance]]. The internal state of that algorithm is a count, the current mean, and the current sample variance. From that page, though, it isn't clear how you would combine partial results. Obviously it's easy to combine the sum and means, but it isn't obvious how you'd combine the variances.
:: In general I'm just interested in ''O''(''N'') algorithms that have ''O''(1) internal state but where the internal state for partial results can be combined so each of ''m'' processors could compute a partial result in ''O''(''N''/''m'') time and those results could then be combined quickly to get the full solution. [[User:BenFrantzDale|—Ben FrantzDale]] 05:01, 7 December 2006 (UTC)
== Algorithms for variance ==
I had added "[[Algorithms_for_calculating_variance#On-line_algorithm|Online algorithms for calculating mean and variance]]" to the see-also section but it got removed with a comment that "streaming algorithm" was a more appropriate place for it. While I'm not 100% clear on the difference between a streaming and an online algorithm, computing the mean and standard deviation of a sequence in a single pass seems like an ideal simple example of an online algorithm. At first glance it is obvious that the mean can be computed in a single pass with O(1) storage, but that isn't obvious about the variance. Could someone explain why these are better examples of [[streaming algorithm]]s than of online algorithms? [[User:BenFrantzDale|—Ben FrantzDale]] ([[User talk:BenFrantzDale|talk]]) 20:58, 30 April 2009 (UTC)
| |||