Quick way to calculate uniformity or discrepancy of number set

Question

Hello Assume I have the set of numbers I want a quick to calculate some measure of uniformity. I know the variance is the most obvious answer but i am afraid the complexity of naive algorithm is too high Anyone have any suggestions?

Answer 1

"Intuitive" algorithms for calculating variance usually suffer one or both of the following:

1. Use two loops (one for calculating the mean, the other for the variance)
2. Are not numerically stable

A good algorithm, with only one loop and numerically stable is due to D. Knuth (as always).

From Wikipedia:

n = 0
mean = 0
M2 = 0
 def calculate_online_variance(x):
    n = n + 1
    delta = x - mean
    mean = mean + delta/n
    M2 = M2 + delta*(x - mean)  # This expression uses the new value of mean

    variance_n = M2/n
    variance = M2/(n - 1) #note on the first pass with n=1 this will fail (should return Inf)
    return variance

You should invoke calculate_online_variance(x) for each point, and it returns the variance calculated so far.