2

N 個の整数があるとします。ここで、N は巨大になる可能性がありますが、各 int は 0 からキャップ M の間であることが保証されています。ここで、M は符号付き 32 ビット フィールドに簡単に収まります。

これらの N 個の整数の平均を計算したい場合、それらすべてを同じ符号付き 32 ビット空間で常に合計および除算することはできません。N が大きすぎると、分子がオーバーフローする危険性があります。この問題の 1 つの解決策は、計算に 64 ビット フィールドを使用してより大きな N を保持することですが、この解決策はスケーリングしません。代わりに M が大きな 64 ビット整数である場合、同じ問題が発生します。

同じビット空間で正の整数のリストの平均を計算できるアルゴリズム (できれば O(N)) を知っている人はいますか? 2 つの整数を使用してより大きな整数をシミュレートするような安価なことはしません。

4

2 に答える 2

5

最初に知っていると仮定するとM、2 つの変数を保持できます。1 つはこれまでの答えを M で割ったもので、もう 1 つは剰余です。

たとえば、C++ では次のようになります。

int ans = 0, remainder = 0;
for (int i=0;i<N;i++) {
  remainder += input[i]; // update remainder so far
  ans += remainder/N; // move what we can from remainder into ans
  remainder%=N; // calculate what's left of remainder
}

ループの終わりに、答えは にありans、残りは にremainderあります (切り捨て以外の丸め方法が必要な場合)。

この例は、最大入力数 M+N が 32 ビットの int に収まる場合に機能します。

/C++ では、演算子は除算演算子であり、%実際には剰余演算子 (モジュロ演算子ではない)であるため、これは正および負の整数に対して機能することに注意してください。

于 2013-04-19T23:25:45.387 に答える
1

移動平均を計算できます。要素の平均AがありN、別の要素を追加するとE、新しい平均は になり(A*N+E)/(N+1)ます。足し算に対する割り算の分配特性により、これは に相当し(A*N)/(N+1) + E/(N+1)ます。ただし、A*Nオーバーフローした場合は、乗算と除算の結合プロパティを使用して、最初の項を に変換できますA*(N/N+1)

したがって、アルゴリズムは次のとおりです。

n = 0
avg = 0
for each i in list
  avg = avg*(n/(n+1)) + i/(n+1)
  n = n+1
于 2013-04-19T23:32:38.180 に答える