計算量オーダーと漸化式とキャッシュ化

　都度変化していく値について統計を取る必要がある場合があります。例えば、リアルタイムに変化していく平均値を表示する場合です。この時、よくある全体を元にした式を使ってプログラムを作ると尋常でない遅さを生みやすいです。
　計算量オーダーは大雑把に言えば計算量の増え方を表した概念です。例えば、総数に比例した計算回数を持つ処理（平均など。平均は対象の(総数-1)回の足し算をする必要があります）をO(n)、総数の二乗に比例した計算回数を持つ処理をO(n^2)と表します。詳しくは次の記事がわかりやすいです。
　計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 – Qiita
　計算量オーダーを測るとボトルネックになる処理の予測がつきます。ソースコード的にも多重ループの様な格段に重くなりやすい処理などのボトルネックになりやすそうな処理の計算量オーダーは大きくなります。
　計算量オーダーを減らす方法の一つに漸化式を作る方法があります。プログラミング的にいえばキャッシュを作る感じです。例えば　要素が増えるたびに平均を毎回計算する処理を考えます。愚直に記述すれば次の様な処理になるでしょう。

let currentAverage = null;
const inputs = [];
function updateAverage(x) {
    inputs.push(x);
    const sum = inputs.reduce((a, b) => a + b, 0);
    currentAverage = sum / inputs.length;
}
updateAverage(2);
updateAverage(3);
updateAverage(5);
updateAverage(10);

　この処理は”要素が増えた時点の要素数回の足し算を要素が増えた回数”行うことになります。要素数が増えるにつれて計算回数は n * logn に近づきます。要するに計算回数がかなりの勢いで増えるので行いたくない処理ということです。
　そういった時、計算の簡略化を考えます。この時は漸化式への変換とキャッシュ化が有効です。
　例えば、平均を漸化式に変換すると次の様にできます。なぜこうなるかは「平均 漸化式」でググるとでてきます。よくある統計処理に関しては大体漸化式を考えた人がいるので似たような感じでググると楽です。

平均_(n+1) = (n * 平均_n + 要素_(n+1)) / (n+1)

これをコードに書き起こすと次の様になります。

let currentAverage = 0;
const inputs = [];
function updateAverage(x) {
    currentAverage = (inputs.length * currentAverage + x) / (inputs.length + 1);
    inputs.push(x);
}
updateAverage(2);
updateAverage(3);
updateAverage(5);
updateAverage(10);

　足し算の数がグッと減りました。要素数が増えた時の計算量の増加が最初の処理より抑えられます。
　中間処理や使いまわす値を変数に残すキャッシュの考え方も有効です。最初のコードでは一々合計をまっさらな状態から計算していましたがそんな必要はありません。

let currentAverage = 0;
let currentSum = 0;
const inputs = [];
function updateAverage(x) {
    inputs.push(x);
    currentSum = currentSum + x;
    currentAverage = currentSum / inputs.length;
}
updateAverage(2);
updateAverage(3);
updateAverage(5);
updateAverage(10);

　今回の合計 = 前回の合計 + 今回の入力要素の値 としました。前回の合計を残しておくことで要素全体の合計を計算する中間処理を飛ばせます。
　これらの様に計算量の多い処理があった時は処理の過程を変えることでわりと高速化できたりします。