Don't Re-add the Elements: The Arithmetic Mean in a Running Average Should Be Efficient

mean.txt

Don't Re-add all the Elements: The Arithmetic Mean in a Running Average Can Be Efficient
----------------------------------------------------------------------------------------

The arithmetic mean of a set is the sum of the set's elements, divided by the set's cardinality.

We observe this definition as a formula: A = 1/n * (a1 + a2 + ... + an), where n is the number of elements.

To demonstrate, we compute the arithmetic mean of the set (1, 2):

A(1, 2) = 1/2 * (1 + 2)
        = 1/2 * (3)
        = 3/2

An extension of that set is (1,2,7), we compute its arithmetic mean as well:

A(1, 2, 7) = 1/3 * (1 + 2 + 7)
        = 1/3 * (10)
        = 10/3

An expensive developer mistake is recalculating the arithmetic mean when totaling a running average.

To compute the arithmetic mean of (1, 2, 7), we can either apply the original formula or reuse the existing 
calculation to save computational power.

Consider the first set (1, 2), with arithmetic mean 3/2. 

The cardinal difference between (1, 2) and (1, 2, 7) is +1. 
The set has expended by +1 element with a value of 7.

If we divide A(1, 2) by the 2 (cardinality of that set) we restore its arithmetic summation from the mean:

A(1, 2) = 3/2
        = 3/2 * 2 
        = 3
        = (1 + 2)

Now that we have restored the summation without redoing the work, we can compute A(1, 2, 7) without
adding (1, 2). Instead add the missing element and divide by the new cardinality. 

Let S = (1, 2) denote the memoized work to illustrate the point.

A(1, 2, 7) = 1/3 * (1 + 2 + 7)
           = 1/3 * (S + 7)
           = 1/3 * (10)
           = 10/3

This saves us a summation operation for computing a running average. 
Further optimizations are left as an exercise.