快速的方法来计算均匀数集的或不一致 [英] Quick way to calculate uniformity or discrepancy of number set

问题描述

您好 假设我有一组数字我想快速计算均匀性的一些措施。 我知道这个变化是最明显的答案，但我怕天真的算法的复杂度太高 任何人有什么建议？

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?

推荐答案

直观的算法来计算方差，通常患有一种或两种以下内容：

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

1. 使用两个循环（一个用于计算平均值，其他为方差）
2. 是不是数值稳定

有一个很好的算法，只有一个回路，数值稳定是由于 D.克努特（一如既往）。

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

维基百科：

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

您应该调用calculate_online_variance（x）的每一个点，并返回到目前为止计算出的差异。

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

这篇关于快速的方法来计算均匀数集的或不一致的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！