From: Olivier <o.renaud@...>
Date: 2006-12-03T05:55:34+09:00
Subject: Re: [OT] calculations on lists of numbers

Le samedi 02 d�cembre 2006 21:07, Joel VanderWerf a �crit�:
> Olivier wrote:
> ...
>
> > 	I'm currently coding a ruby program for processing images. One of the
> > class I wrote is intended to compute some stats about the luminance of a
> > channel, but in fact it can be used on any set of numerical datas. The
> > stats are : - an histogram
> >  - the mean
> >  - the variance
> >  - the deviation
> >  - the median
> >  - the skewness
> >  - the kurtosis
> >
> > 	It is very fast, since it uses no memory : the values are not stored
> > internally, just the sub-results (so, a list of 2 values will use the
> > same amount of memory than a list of a billion values), and also because
> > the method that adds a value is generated depending of what stats you
> > want to compute.
>
> What's the secret to computing stdev in bounded space? The formulas I
> know (I am not much of a statistician) require you to know the mean in
> advance.
>
> Do you do it in two passes through the data, first getting the mean and
> then the stdev? (But this would not work if you are reading data from
> stdin and don't want to cache the data in memory.)

Yes, to compute the standard deviation I need the mean. I fact, there are 
dependancies between the data to compute :
-stddev needs variance
-variance needs the mean, the nb of values, and the sum of the squared values
-mean needs the sum of the values and the nb of values.

here is the hash I use for this (the nb of values are always computed) :

DEPENDANCIES = {
  :histogram =>     [:table],
  :mean =>      [:sum],
  :variance =>  [:sum, :square],
  :deviation => [:sum, :square],
  :median =>    [:table],
  :skewness =>  [:sum, :square, :cube],
  :kurtosis =>  [:sum, :square, :cube, :quad],
} # :nodoc:

Then the method which adds a value is generated to compute these data each 
time one is added.
in this case, the generated method would be :

def add_pixel(value)
  @nb_px += 1
  @lum_sum += value
  @lum_square_sum += value**2'
  return self
end

and the mean, variance and deviation methods are avalaible at any time :

    def mean
      return 0 if @lum_sum.zero?
      return @lum_sum / @nb_px.to_f
    end

    def variance
      return 0 if @lum_sum.zero?
      return @lum_square_sum / @nb_px.to_f - self.mean**2
    end

    def deviation
      return Math.sqrt(variance)
    end

for each value v, we can compute any stat by computing the sum of v, v**2, 
v**3 and v**4 (kurtosis needs all of them, for example)

Et voila :)