【C++】数値ストリームの平均値を効率的に求める方法

数値の平均とは、数値の合計をその個数で割った値のことです。

この問題では、数値のストリーム(連続して流れてくる数値列)が与えられ、数値が1つ追加されるたびに、その時点までの平均を出力していきます。

具体的な動作例を見てみましょう。

5つの数値からなるストリーム「24、76、29、63、88」を考えます。

各時点での平均は以下のようになります。

24、50、43、48、56

つまり、数値がストリームに追加されるたびに平均を計算する必要があります。具体的には、1個の数値の平均、2個の数値の平均、3個の数値の平均……と順番に求めていきます。このとき、毎回すべての数値を足し直すのではなく、直前の平均値を利用することで効率的に計算できます。

アルゴリズム

ステップ1:iを0からn(ストリームの長さ)まで繰り返す。
ステップ2:次の式で平均を求める。
    Average = (average × i + arr[i]) ÷ (i + 1)
ステップ3:平均を出力する。

この式のポイントは、「直前の平均 × 個数 = 直前の合計」という関係を利用している点です。新しい数値を加えた合計を、新しい個数で割り直すだけで平均が更新できます。

実装例

#include <iostream>
using namespace std;
int main(){
    int arr[] = { 24 , 76 , 29, 63 , 88 };
    int average = 0;
    int n = sizeof(arr) / sizeof(arr[0]);
    for(int i = 0 ; i < n ; i++){
        average = ((average * i) + arr[i]) / (i+1);
        cout << "ストリームの " << i+1 << " 個の数値の平均は " << average << endl;
    }
    return 0;
}

出力結果

ストリームの 1 個の数値の平均は 24
ストリームの 2 個の数値の平均は 50
ストリームの 3 個の数値の平均は 43
ストリームの 4 個の数値の平均は 48
ストリームの 5 個の数値の平均は 56

注意点

上記の実装例では平均を int 型で扱っているため、割り切れない場合は小数点以下が切り捨てられます。より正確な平均を求めたい場合は、average を double 型で宣言してください。

このアルゴリズムは int や double など、すべてのデータ型に適用可能で、ストリームの各時点における平均を毎回O(1)の計算量で効率的に求めることができます。