分散・標準偏差の1ループ計算法

一般

分散・標準偏差を計算するために一般にはつぎの2つのループが必要である。

1. 平均を求めるループ
2. 二乗和を求めるループ

double sdNormal(long long int n) {
    double average = 0.0;
    for (long long int i=0; i<n; i++) {
        average += i;
    }
    average = average / n;

    double sd = 0.0;
    for (long long int i=0; i<n; i++) {
        sd += (i - average)*(i - average);
    }
    return sqrt(sd/n);
}

１ループ計算法

しかし次のように分散・標準偏差の式を変形するとループは1つで済む。

$$\begin{aligned} \sigma &= \sqrt{\frac{1}{n}\sum_{i=1}^{n}(x_i-\bar{x})^2} = \sqrt{\frac{1}{n}\sum_{i=1}^{n}x_i^2-(\frac{1}{n}\sum_{i=1}^{n}x_i)^2}\\ \\ \because \sigma^2 &= \frac{1}{n}\sum_{i=1}^{n}(x_i-\bar{x})^2\\ &= \frac{1}{n}\sum_{i=1}^{n}(x_i^2-2x_i\bar{x}+\bar{x}^2)\\ &= \frac{1}{n}\sum_{i-1}^{n}x_i^2 - 2\bar{x}\frac{1}{n}\sum_{i=1}^{n}x_i + \frac{1}{n}\sum_{i=1}^{n}\bar{x}^2\\ &= (\frac{1}{n}\sum_{i=1}^{n}x_i^2)-2\bar{x}^2+\bar{x}^2\\ &= (\frac{1}{n}\sum_{i=1}^{n}x_i^2)-\bar{x}^2\\ &= \frac{1}{n}\sum_{i=1}^{n}x_i^2-(\frac{1}{n}\sum_{i=1}^{n}x_i)^2\\ \end{aligned}$$

double sdNew(long long int n) {
    double sum = 0.0;   
    double sum2 = 0.0;

    for (long long int i=0; i<n; i++) {
        sum += i;
        sum2 += i*i;
    }   
    return sqrt(sum2/n - (sum/n)*(sum/n));
}

参考

sdNormal()の処理時間を1.0とするとsdNew()は約0.9となった。
コンパイラで最適化を指定するとsdNormal()の1.0に対し約0.5となった。

🌏 Map

same layer	lower layer