5

編集：このリンク先の元の質問を誰も読んでいないように見えるので、ここでその概要を紹介しましょう。

他の誰かが尋ねたように、元の問題は、合計がデータ型が保持するものを超える多数の値が与えられた場合、Doubleそれらの値の平均をどのように計算できるかということでした。

50 個と 50 個の数値を取り、それらのセット内の平均を計算し、最後にそれらすべてのセットの平均を取り、それらを組み合わせて最終的な平均値を取得するなど、セットで計算するといういくつかの回答がありました。

私の立場は、これらすべての値を同じサイズのセットに分割できることを保証できない限り、このアプローチは使用できないというものでした。答えを提供するために、誰かが私にここで質問することを敢えてしたので、ここにあります。

基本的に、任意の数の値が与えられると、次のようになります。

  • 値の数は事前に知っています (しかし、もしそうでなければ、あなたの答えはどのように変化しますか?`)
  • すべての数値を集めることも、それらを合計することもできません (合計は、プログラミング言語の通常のデータ型には大きすぎます)。

どうすれば平均を計算できますか？

ここでの質問の残りの部分では、同じサイズのセットに分割する方法とその問題の概要を説明していますが、どうすればそれができるかを知りたいだけです.

私は、数学理論の用語で、 の合計を計算すると平均が得られることを十分に理解していることに注意してください。A[1..N]/N単純ではない理由があると仮定して、ワークロードを分割する必要があります。また、値の数が必ずしも 3、7、50、1000 などで割り切れるわけではありません。

言い換えれば、私が求めている解決策は一般的でなければなりません。

この質問から：

私の立場は、これらのセットのサイズが等しいことを保証できない限り、作業負荷をセットに分割することは良くないというものでした。

編集: 元の質問は、特定のデータ型が保持できる上限に関するものでした。彼は多くの数値を合計していたため (例として与えられたカウントは 10^9 でした)、データ型は合計を保持できませんでした。これは元のソリューションの問題だったので、数字が大きすぎて意味のある答えが得られないと思います (これは私の質問の前提条件です。それを逃して申し訳ありません)。

したがって、値の総数で直接除算することはできません。通常の SUM/COUNT ソリューションが存在しない元の理由は、SUM がオーバーフローすることでしたが、この質問では、SET-SET/SET-SIZE がアンダーフローするなどと仮定しましょう。

重要な点は、単純に合計したり、合計値の数で単純に割ったりすることはできないということです。それができない場合、私のアプローチはうまくいくでしょうか?それを修正するにはどうすればよいでしょうか?

問題の概要を説明しましょう。

1 から 6 までの数値の平均を計算しようとしていると仮定しましょう。ただし、(何らかの理由で) 数値を合計し、数値を数え、合計をカウントで割ることによって計算することはできません。つまり、単純に (1+2+3+4+5+6)/6 を実行することはできません。

つまりSUM(1..6)/COUNT(1..6)アウトです。ここでは、NULL (データベースの NULL と同様) は考慮していません。

その質問に対するいくつかの回答は、平均化される数値をセット (たとえば 3、50、または 1000 の数値) に分割し、その数値を計算し、最後にそれらの値を組み合わせて最終的な平均を取得できることをほのめかしています。

私の立場は、これは一般的なケースでは不可能だということです.これは、すべての数字を均等に分割できない限り、最終的なセットに表示される数字の価値が、以前のセットのすべての数字よりも多かれ少なかれ価値があるためです.サイズのセット。

たとえば、1 ～ 6 の平均を計算するには、次のように 3 つの数字のセットに分割できます。

/ 1   2   3 \   / 4   5   6 \
| - + - + - | + | - + - + - |
\ 3   3   3 /   \ 3   3   3 /  <-- 3 because 3 numbers in the set
 ----------      -----------
      2               2        <-- 2 because 2 equally sized groups

これにより、次のようになります。

      2               5
      -       +       - = 3.5
      2               2

(注: (1+2+3+4+5+6)/6 = 3.5 なので、ここでは正しい)

ただし、私のポイントは、値の数を同じサイズのセットに分割できなくなると、この方法は失敗するということです。たとえば、値の素数を含むシーケンス 1 ～ 7 はどうでしょうか。

すべての値を合計せず、すべての値を一度にカウントする同様のアプローチは機能しますか?

それで、そのようなアプローチはありますか？以下が当てはまる任意の数の値の平均を計算するにはどうすればよいですか。

  1. 何らかの理由で、通常の合計/カウントアプローチを実行できません
  2. 値の数は事前にわかっています (わからない場合、答えは変わりますか?)
4

8 に答える 8

8

3 つの数を足して 3 で割った後、2 つの数を足して 2 で割ったとします。これらから平均を出すことはできますか？

x = (a + b + c) / 3
y = (d + e) / 2
z = (f + g) / 2

そして、あなたがしたい

r = (a + b + c + d + e + f + g) / 7

それは等しい

r = (3 * (a + b + c) / 3 + 2 * (d + e) / 2 + 2 * (f + g) / 2) / 7
r = (3 * x + 2 * y + 2 * z) / 7

もちろん、上記の両方の行はオーバーフローしますが、除算は分配であるため、

r = (3.0 / 7.0) * x + (2.0 / 7.0) * y + (2.0 / 7.0) * z

x、y、z を 1 未満の分数で乗算しているため、オーバーフローしないことが保証されます。

ここが基本的なポイントです。すべての数値を事前に合計数で除算することも、オーバーフローを超えることもありません。

したがって...アキュムレータに追加し続け、追加した数を追跡し、次の数がオーバーフローを引き起こすかどうかを常にテストすると、部分平均を取得して最終平均を計算できます。

いいえ、事前に値がわからない場合は、何も変更されません (合計するときに値を数えることができる場合)。

これを行う Scala 関数を次に示します。これは慣用的な Scala ではないため、より簡単に理解できます。

def avg(input: List[Double]): Double = {
  var partialAverages: List[(Double, Int)] = Nil
  var inputLength = 0
  var currentSum = 0.0
  var currentCount = 0
  var numbers = input

  while (numbers.nonEmpty) {
    val number = numbers.head
    val rest = numbers.tail
    if (number > 0 && currentSum > 0 && Double.MaxValue - currentSum < number) {
      partialAverages = (currentSum / currentCount, currentCount) :: partialAverages
      currentSum = 0
      currentCount = 0
    } else if (number < 0 && currentSum < 0 && Double.MinValue - currentSum > number) {
      partialAverages = (currentSum / currentCount, currentCount) :: partialAverages
      currentSum = 0
      currentCount = 0
    }
    currentSum += number
    currentCount += 1
    inputLength += 1
    numbers = rest
  }
  partialAverages = (currentSum / currentCount, currentCount) :: partialAverages

  var result = 0.0
  while (partialAverages.nonEmpty) {
    val ((partialSum, partialCount) :: rest) = partialAverages
    result += partialSum * (partialCount.toDouble / inputLength)
    partialAverages = rest
  }

  result
}

編集: 2 と 3 を乗算しないと、「データ型によってサポートされていない」の範囲に戻りますか?

いいえ。最後に 7 でダイビングしていた場合は、絶対に。しかし、ここでは合計の各ステップで割っています。実際のケースでも、重み (2/7および3/7) は扱いやすい数値 (例: 1/10~ 1/10000) の範囲内であり、体重 (つまり ) と比べて大きな違いはありません1。

PS：担当者を獲得できる場所で私のものを書くのではなく、なぜこの回答に取り組んでいるのか疑問に思います:-)

于 2009-12-19T00:08:57.670 に答える
4

値の数が事前にわかっている場合 (たとえば)、値があったと仮定して etc をN追加するだけです。これを好きな数の計算に分割して、結果を合計するだけです。精度がわずかに低下する可能性がありますが、非常に正確な結果が必要でない限り、これは問題になりません。1/N + 2/N + 3/N1, 2, 3

アイテムの数が事前にわからない場合は、もっと工夫する必要があるかもしれません。しかし、繰り返しますが、段階的に行うことができます。リストが であるとし1, 2, 3, 4ます。から始めmean = 1ます。それからmean = mean*(1/2) + 2*(1/2)。それからmean = mean*(2/3) + 3*(1/3)。次にmean = mean*(3/4) + 4*(1/4)、一般化するのは簡単です。オーバーフローを防ぐために、ブラケットで囲まれた数量が事前に計算されていることを確認する必要があります。

もちろん、極端な精度 (たとえば、0.001% 以上の精度) が必要な場合は、これよりも少し注意が必要になる場合がありますが、それ以外の場合は問題ありません。

于 2009-12-19T00:06:13.200 に答える
3

Xあなたのサンプルセットになりましょう。Aそれを 2 つのセットに分割しB、好きな方法で分割します。がセットの平均を表すdelta = m_B - m_A場所を定義します。それでm_SS

m_X = m_A + delta * |B| / |X|

ここで|S|、 はセットのカーディナリティを示しSます。これを繰り返し適用して分割し、平均を計算できます。

なぜこれが真実なのですか？s = 1 / |A|とt = 1 / |B|とu = 1 / |X|(表記の便宜上) と ととは、それぞれ との要素の和を表すaSigmaので、次のようになります。bSigmaAB

  m_A + delta * |B| / |X|
= s * aSigma + u * |B| * (t * bSigma - s * aSigma)
= s * aSigma + u * (bSigma - |B| * s * aSigma)
= s * aSigma + u * bSigma - u * |B| * s * aSigma
= s * aSigma * (1 - u * |B|) + u * bSigma
= s * aSigma * (u * |X| - u * |B|) + u * bSigma
= s * u * aSigma * (|X| - |B|) + u * bSigma
= s * u * aSigma * |A| + u * bSigma
= u * aSigma + u * bSigma
= u * (aSigma + bSigma)
= u * (xSigma)
= xSigma / |X|
= m_X

証明は完了です。

ここから、これを使用して再帰的に平均を計算する方法 (たとえば、セットを繰り返し半分に分割することによって)、またはこれを使用してセットの平均の計算を並列化する方法は明らかです。

平均を計算するためのよく知られたオンライン アルゴリズムは、この特殊なケースにすぎません。mこれは、が の平均である場合、 の{x_1, x_2, ... , x_n}平均は であるというアルゴリズム{x_1, x_2, ..., x_n, x_(n+1)}ですm + ((x_(n+1) - m)) / (n + 1)。したがって、X = {x_1, x_2, ..., x_(n+1)}、A = {x_(n+1)}、およびB = {x_1, x_2, ..., x_n}オンライン アルゴリズムを復元します。

于 2009-12-19T17:10:27.950 に答える
1

固定観念にとらわれない考え方:代わりに中央値を使用してください。計算ははるかに簡単です - そこにはたくさんのアルゴリズムがあり (例: キューを使用)、多くの場合、データセットにとってより意味のある理由 (極端な値による影響が少ないなど) について適切な議論を構築することができ、問題はありません。数値精度。それは速くて効率的です。さらに、大規模なデータセット (あなたが持っているように聞こえます) の場合、分布が本当に奇妙でない限り、平均値と中央値の値は似ています。

于 2009-12-19T00:21:05.387 に答える
0

別のアプローチがあります。あるソースから1つずつ数値を「受信」していますが、各ステップで平均を追跡できます。

まず、ステップで平均の式を書きますn+1。

mean[n+1] = mean[n] - (mean[n] - x[n+1]) / (n+1)

初期条件で：

mean[0] = x[0]

（インデックスはゼロから始まります）。

最初の方程式は次のように簡略化できます。

mean[n+1] = n * mean[n] / (n+1) + x[n+1]/(n+1)

アイデアは、平均を追跡し、シーケンス内の次の値を「受信」したときに、現在の平均からのオフセットを計算し、n+1これまでに見たサンプル間で均等に分割し、それに応じて平均を調整することです。 。数値に大きな分散がない場合は、新しい数値nが大きくなるにつれて、移動平均をわずかに調整する必要があります。

明らかに、この方法は、開始時に値の総数がわからなくても機能します。現在の平均値を常に知っているという追加の利点があります。私が考えることができる1つの欠点は、おそらく最初に見られる数値により多くの「重み」を与えることです（厳密な数学的意味ではなく、浮動小数点表現のため）。

最後に、十分に注意しないと、そのような計算はすべて浮動小数点の「エラー」に遭遇することになります。浮動小数点計算の問題のいくつかと潜在的な問題をテストする方法については、別の質問に対する私の回答を参照してください。

テストとして、N=100000平均がゼロで分散が1の正規分布の乱数を生成しました。次に、3つの方法でそれらの平均を計算しました。

  1. sum（numbers）/ N、それをm 1と呼びます、
  2. 上記の私のメソッド、それをm 2と呼びます、
  3. 番号を並べ替えてから、上記の方法を使用して、 m3と呼びます。

私が見つけたものは次のとおりです。m1−  m 2〜  −4.6×10 −17、m 1  − m 3〜 − 3  ×10 −15、m 2  − m 3〜  −3×10 −15。したがって、数値が並べ替えられている場合、エラーは十分に小さくない可能性があります。（ただし、最悪のエラーでさえ、100000個の数値に対して1で10 -15の部分であるため、とにかく十分である可能性があることに注意してください。）

于 2009-12-19T17:01:52.810 に答える
0

ここでの数学的解のいくつかは非常に優れています。これが簡単な技術的解決策です。

より大きなデータ型を使用してください。これは、次の 2 つの可能性に分けられます。

  1. 高精度浮動小数点ライブラリを使用します。10 億の数値を平均化する必要がある人は、おそらく 128 ビット (またはそれ以上) の浮動小数点ライブラリを購入するためのリソース、または書き込むための頭脳を持っています。

    ここの欠点は理解しています。組み込み型を使用するよりも確かに遅くなります。値の数が増えすぎると、オーバーフロー/アンダーフローが発生する可能性があります。ヤダヤダ。

  2. 値が整数であるか、整数に簡単にスケーリングできる場合は、合計を整数のリストに保持します。オーバーフローしたら、別の整数を追加するだけです。これは基本的に、最初のオプションの単純化された実装です。C# での単純な(テストされていない)例は次のとおりです。

class BigMeanSet{
    List<uint> list = new List<uint>();

    public double GetAverage(IEnumerable<uint> values){
        list.Clear();
        list.Add(0);

        uint count = 0;

        foreach(uint value in values){
            Add(0, value);
            count++;
        }

        return DivideBy(count);
    }

    void Add(int listIndex, uint value){
        if((list[listIndex] += value) < value){ // then overflow has ocurred
            if(list.Count == listIndex + 1)
                list.Add(0);
            Add(listIndex + 1, 1);
        }
    }

    double DivideBy(uint count){
        const double shift = 4.0 * 1024 * 1024 * 1024;

        double rtn       = 0;
        long   remainder = 0;

        for(int i = list.Count - 1; i >= 0; i--){
            rtn *= shift;
            remainder <<= 32;
            rtn += Math.DivRem(remainder + list[i], count, out remainder);
        }

        rtn += remainder / (double)count;

        return rtn;
    }
}

私が言ったように、これはテストされていません.10億の値を本当に平均したいわけではありません.そのため、特にDivideBy関数で1つまたは2つの間違いを犯した可能性がありますが、一般的なアイデアを示すはずです.

これは、double が表すことができるのと同じくらいの精度を提供し、2 32 - 1 までの任意の数の 32 ビット要素に対して機能する必要があります。さらに多くの要素が必要な場合は、count変数を拡張する必要があり、DivideBy関数の複雑さが増します。 、しかし、それは読者の演習として残しておきます。

効率の点では、リストを 1 回反復するだけで済み、1 つの除算演算 (まあ、それらの 1 つのセット) しか実行せず、ほとんどの作業を整数で行うため、ここでの他のどの手法よりも高速である必要があります。 . ただし、最適化はしていません。必要に応じて、さらに高速化できると確信しています。再帰的な関数呼び出しとリストのインデックス作成をやめることは、良い出発点です。繰り返しますが、読者のための演習です。コードは理解しやすいように意図されています。

現時点で私よりもやる気のある人が、コードの正確性を検証し、問題があればそれを修正したいと思っている場合は、私のゲストになってください。

私は今、このコードをテストし、いくつかの小さな修正を加えました (List<uint>コンストラクター呼び出しでの括弧のペアの欠落と、関数の最後の分割での不正確な除数DivideBy)。

最初に、ランダムな整数 (0 から 2 32 - 1の範囲) で満たされたランダムな長さ (1 から 1000 の範囲) の 1000 セットを実行してテストしました。これらは、正準平均も実行することで、簡単かつ迅速に精度を検証できるセットでした。

次に、10 5から 10 9の間のランダムな長さで、100 *の大きなシリーズでテストしました。これらのシリーズの下限と上限もランダムに選択され、シリーズが 32 ビット整数の範囲内に収まるように制約されています。どのシリーズでも、結果は として簡単に検証できます。(lowerbound + upperbound) / 2

*わかりました、それはちょっとしたうそです。約 20 回または 30 回の実行が成功した後、大規模なシリーズのテストを中止しました。一連の長さ 10 9を私のマシンで実行するのに 1 分半弱かかるので、このルーチンをテストするのに 30 分程度で十分でした。

興味のある方のために、私のテストコードは以下のとおりです。

static IEnumerable<uint> GetSeries(uint lowerbound, uint upperbound){
    for(uint i = lowerbound; i <= upperbound; i++)
        yield return i;
}

static void Test(){
    Console.BufferHeight = 1200;
    Random rnd = new Random();

    for(int i = 0; i < 1000; i++){
        uint[] numbers = new uint[rnd.Next(1, 1000)];
        for(int j = 0; j < numbers.Length; j++)
            numbers[j] = (uint)rnd.Next();

        double sum = 0;
        foreach(uint n in numbers)
            sum += n;

        double avg = sum / numbers.Length;
        double ans = new BigMeanSet().GetAverage(numbers);

        Console.WriteLine("{0}: {1} - {2} = {3}", numbers.Length, avg, ans, avg - ans);

        if(avg != ans)
            Debugger.Break();
    }

    for(int i = 0; i < 100; i++){
        uint length     = (uint)rnd.Next(100000, 1000000001);
        uint lowerbound = (uint)rnd.Next(int.MaxValue - (int)length);
        uint upperbound = lowerbound + length;

        double avg = ((double)lowerbound + upperbound) / 2;
        double ans = new BigMeanSet().GetAverage(GetSeries(lowerbound, upperbound));

        Console.WriteLine("{0}: {1} - {2} = {3}", length, avg, ans, avg - ans);

        if(avg != ans)
            Debugger.Break();
    }
}
于 2009-12-19T02:41:08.253 に答える
0

数字をセットに分割すると、合計数で割るだけですか、それとも何か不足していますか?

あなたはそれを次のように書いています

/ 1   2   3 \   / 4   5   6 \
| - + - + - | + | - + - + - |
\ 3   3   3 /   \ 3   3   3 /
 ----------      -----------
      2               2

しかし、それはただ

/ 1   2   3 \   / 4   5   6 \
| - + - + - | + | - + - + - |
\ 6   6   6 /   \ 6   6   6 /

したがって、1 から 7 までの数字の 1 つの可能なグループ化は、

/ 1   2   3 \   / 4   5   6 \   / 7 \
| - + - + - | + | - + - + - | + | - |
\ 7   7   7 /   \ 7   7   7 /   \ 7 /
于 2009-12-19T00:06:15.177 に答える
0

 

Average of x_1 .. x_N
    = (Sum(i=1,N,x_i)) / N
    = (Sum(i=1,M,x_i) + Sum(i=M+1,N,x_i)) / N
    = (Sum(i=1,M,x_i)) / N + (Sum(i=M+1,N,x_i)) / N

これは繰り返し適用でき、合計のサイズが等しいかどうかに関係なく当てはまります。そう：

  • 次の両方になるまで用語を追加し続けます。
    • 別のものを追加するとオーバーフローします（または精度が失われます）
    • N で除算するとアンダーフローしません
  • 合計を N で割る
  • 結果をこれまでの平均に追加します

明らかに厄介なケースが 1 つあります。それは、シーケンスの最後にいくつかの非常に小さな項があり、「N で除算してもアンダーフローしない」という条件を満たす前に値が不足する場合です。その場合、それらの値を破棄するだけです。平均への寄与を浮動小数点型で表すことができない場合、特に平均の精度よりも小さくなります。したがって、これらの用語を含めても含めなくても、結果に違いはありません。

個々の合計の精度が失われるという、あまり目立たない厄介なケースもあります。たとえば、値の平均は次のとおりです。

10^100, 1, -10^100

数学では 1 と言われますが、浮動小数点演算では項を足し合わせる順序に依存し、6 つの可能性のうち 4 つでは 0 です。なぜなら (10^100) + 1 = 10^100 だからです。しかし、浮動小数点演算の非可換性は、この質問とは異なり、より一般的な問題だと思います。入力の並べ替えが問題外である場合、さまざまな大きさのアキュムレータを多数維持し、それぞれの新しい値をそれらのいずれかが最高の精度を与えるものに追加する場合にできることがあると思います。しかし、私は本当に知りません。

于 2009-12-19T00:43:55.247 に答える