平均と分散を漸化式を使って爆速で求める

前書き

Databaseの情報から平均と分散を計算するAPIを建てようと考えていた. その時に平均と分散の計算量がo(n)なのを現在の平均分散をキャッシュしておけば早くなることに気づいたので計算をしました.

しかし, そもそも考えているアプリのnが大きくないという条件から素直にDBの関数を使ったほうが保守性が良いということでボツになりました.

この記事はそんな悲しみを供養する記事です.

平均

$$\begin{align*} \bar{x}_n &= \frac{1}{n} \sum x_i \\ &= \big( \frac{1}{n} \sum_{i=1}^{n-1} x_i \big) + \frac{1}{n} x_n \\ &= \big( \frac{n-1}{n-1} \frac{1}{n} \sum_{i=1}^{n-1} x_i \big) + \frac{1}{n} x_n \\ &= \big( \frac{n-1}{n} \frac{1}{n-1} \sum_{i=1}^{n-1} x_i \big) + \frac{1}{n} x_n \\ &= \big( \frac{n-1}{n} \bar{x}_{n-1} \big) + \frac{1}{n} x_n \\ &= \frac{1}{n} \bigg( (n-1)\bar{x}_{n-1}+ x_n \bigg) \end{align*}$$

分散

$$\begin{align*} s^2_n &= \mathbb{E}(X^2) - \mathbb{E}(X)^2 \\ &= \frac{1}{n}\sum x_i^2 - (\frac{1}{n} \sum x_i)^2 \\ &= \frac{1}{n} x_n^2 + \frac{1}{n}\sum_{i=1}^{n-1} x_i^2 - \bar{x}_n^2 \\ &= \frac{1}{n} x_n^2 + \frac{n-1}{n-1}\frac{1}{n}\sum_{i=1}^{n-1} x_i^2 - \bar{x}_n^2 \\ &= \frac{1}{n} x_n^2 + \frac{n-1}{n}\frac{1}{n-1}\sum_{i=1}^{n-1} x_i^2 - \bar{x}_n^2 \\ &= \frac{1}{n} x_n^2 + \frac{n-1}{n}\bigg( s_{n-1}^2 + \bar{x}_{n-1}^2 \bigg) - \bar{x}_n^2 \\ &= \frac{1}{n} x_n^2 + \frac{n-1}{n} s_{n-1}^2 - \frac{n-1-n}{n} \bar{x}_n^2 \\ &= \frac{1}{n} x_n^2 + \frac{n-1}{n} s_{n-1}^2 + \frac{1}{n} \bar{x}_n^2 \end{align*}$$

• 分散の公式を用いて解くことに注意
• $\bar{x}_n$ には先ほど求めた平均を入力する

実際どれぐらいから遅くなるのかPythonで実験

使用したコード

import random
import time


def calc_without_cache(x: list):
    mean_n = (1/len(x)) * sum(x)
    var_n = (1/len(x)) * sum([ (x_ - mean_n)**2 for x_ in x ])

if __name__ == '__main__':
    for i in range(1,11):
        print("+---------------------------+")
        print("n = 10^{}".format(i))
        x = [random.randint(0, 100) for _ in range(10**i)]

        start = time.time()
        calc_without_cache(x)
        end = time.time()
        print(f'Without cache: {round(end - start, 4)}')

実験結果

• $10^6$ あたりから計算が遅い

+---------------------------+
n = 10^1
Without cache: 0.0
+---------------------------+
n = 10^2
Without cache: 0.0
+---------------------------+
n = 10^3
Without cache: 0.0001
+---------------------------+
n = 10^4
Without cache: 0.0009
+---------------------------+
n = 10^5
Without cache: 0.0069
+---------------------------+
n = 10^6
Without cache: 0.0698
+---------------------------+
n = 10^7
Without cache: 0.6968
+---------------------------+
n = 10^8
Without cache: 8.5611
+---------------------------+
...