4

次のようなデータセットの平均値を計算したいとします。

class Averager {
   float total;
   size_t count;
   float addData (float value) {
       this->total += value;
       return this->total / ++this->count;
   }
}

遅かれ早かれortotal値countがオーバーフローするので、合計値を記憶しないようにします。

class Averager {
   float currentAverage;
   size_t count;
   float addData (float value) {
       this->currentAverage = (this->currentAverage*count + value) / ++count;
       return this->currentAverage;
   }
}

それらはより長くオーバーフローするようですが、との間の乗算はオーバーフローの問題averageにcountつながるため、次の解決策は次のとおりです。

class Averager {
   float currentAverage;
   size_t count;
   float addData (float value) {
       this->currentAverage += (value - this->currentAverage) / ++count;
       return this->currentAverage;
   }
}

次の問題はcountオーバーフローを防ぐ方法ですか？

4

6 に答える 6

7

集約されたバケット。

squareRoot（MAXINT）よりも快適に小さいバケットサイズを選択します。簡単にするために、10を選びましょう。

新しい値はそれぞれ現在のバケットに追加され、移動平均は説明どおりに計算できます。

バケットがいっぱいになったら、新しいバケットを開始し、いっぱいになったバケットの平均を記憶します。フルバケットと現在の部分バケットの平均を組み合わせることで、全体の平均を安全に計算できます。フルバケットが10個になると、容量100のより大きなバケットが作成されます。

合計平均を計算するには、最初に「10」の平均を計算し、次にそれを「100」と組み合わせます。このパターンは、「1,000s」「10,000s」などで繰り返されます。各段階で、前のレベルより10倍大きい2つのレベルを考慮するだけで済みます。

于 2010-07-23T08:07:46.847 に答える
2

を使用しdouble total; unsigned long long count;ます。精度についてはまだ心配する必要がありますが、。よりも問題ははるかに少なくなりますfloat。

于 2010-07-23T07:58:50.250 に答える
1

任意精度演算を使用するのはどうですか？

ウィキペディアで使用できるライブラリのリストがあります：http：//en.wikipedia.org/wiki/Bignum#Libraries

ほとんどの任意精度の算術ライブラリは、格納されている桁数が使用可能なメモリを満たすまでオーバーフローしません（これはほとんどありません）。

于 2010-07-23T08:15:37.537 に答える
1

カハンの加算アルゴリズムを使用したい場合：

http://en.wikipedia.org/wiki/Kahan_summation_algorithm

「すべてのコンピューター科学者が浮動小数点演算について知っておくべきこと」の合計のエラーに関するセクションも参照してください。

http://docs.sun.com/source/806-3568/ncg_goldberg.html#1262

于 2010-07-23T08:49:32.007 に答える
0

これらの特別なデータ型を使用すると、RAMがいっぱいになるまで整数が無限に大きくなる可能性があります。

于 2010-07-23T08:14:07.197 に答える
0

これも考えていました。この解決策は、「針を動かす」という新しい価値の観点から機能すると思います。これは、これまでの平均に寄与した以前の値の数の係数（プラス1）だけ移動します。入力が増えると精度が低下しますが、平均して実際には許容できるはずです。動作しているように見えるJavaコードを次に示します。ここではfloatとintを使用して、これらの制限で機能することを示しましたが、doubleを使用して精度を上げることができます。これは、最大に近い整数の配列を平均化する方法を理解するためのものです。入力の総数と現在の平均を追跡する必要がありますが、入力の合計を追跡する必要はありません。入力の総数がMAX_INTに近づくと、これは最終的には機能しないため、上記のバケットの提案を使用する必要があります。

    public float calcAverageContinuous(int[] integers)
{
    float ave = 0;
    for (int i = 0; i < integers.length; i++) {
        ave += (((float)integers[i] - ave) / (float)(i + 1));
    }
    return ave;
}
于 2019-08-17T20:35:39.197 に答える