3

通常、私はより技術的な問題を抱えていますが、ボールを数える例で簡単に説明します。

異なる色のボールと、各色用に予約された配列の 1 つのインデックス (すべて 0 に初期化) があるとします。ボールを選ぶたびに、対応するインデックスを 1 ずつ増やします。

ボールはランダムに選ばれ、一度に 1 つのボールしか選べません。私の唯一の目的は、ボールがなくなるまで、すべての色のボールの数を数えることです。

私はそれらを数えている間に、異なる色のボールの数の標準偏差を計算したいと思います. すべてのボールのカウントが完了した後、配列をもう一度反復する必要があるため、計算したくありません。

視覚化するには:

ランダムな順序のボール: BBGRRYYBBGGGGGGB(各文字は色の最初の文字を表します) 0 から 3 までの配列インデックスは、それぞれ B、G、R、Y の色に対応します。ボールの選択が完了すると、配列は次のようになり[5,7,2,2]ます。

最終的な配列を取得した後に標準偏差を計算するのは非常に簡単ですが、この配列を埋めている間に実行したいと思います。

Javaでやりたいのですが、約1000色あります。

それを実装する最も効率的な方法は何ですか？または、最終的な配列を手に入れる前にそれを行う方法さえありますか?

4

2 に答える 2

9

標準偏差を計算するために配列は必要ありません。

ポイント数、総和、総二乗和を記録するだけです。配列を保持しなくても、いつでも平均偏差と標準偏差を計算できます。

私があなたの要件を理解したら、色がキーであり、Statistics のインスタンスが値である Map が必要です。

これがあなたのためにそれを行うクラスです。 

package statistics;

/**
 * Statistics
 * @author Michael
 * @link http://stackoverflow.com/questions/11978667/online-algorithm-for-calculating-standrd-deviation/11978689#11978689
 * @since 8/15/12 7:34 PM
 */
public class Statistics {

    private int n;
    private double sum;
    private double sumsq;

    public void reset() {
        this.n = 0;
        this.sum = 0.0;
        this.sumsq = 0.0;
    }

    public synchronized void addValue(double x) {
        ++this.n;
        this.sum += x;
        this.sumsq += x*x;
    }

    public synchronized double calculateMean() {
        double mean = 0.0;
        if (this.n > 0) {
            mean = this.sum/this.n;
        }
        return mean;
    }

    public synchronized double calculateVariance() {
       double deviation = calculateStandardDeviation();
        return deviation*deviation;
    }

    public synchronized double calculateStandardDeviation() {
        double deviation = 0.0;
        if (this.n > 1) {
            deviation = Math.sqrt((this.sumsq - this.sum*this.sum/this.n)/(this.n-1));
        }
        return deviation;
    }
}

単体テストは次のとおりです。

package statistics;

import org.junit.Assert;
import org.junit.Test;

/**
 * StatisticsTest
 * @author Michael
 * @link http://www.wolframalpha.com/input/?i=variance%281%2C+2%2C+3%2C+4%2C+5%2C+6%29&a=*C.variance-_*Variance-
 * @since 8/15/12 7:42 PM
 */
public class StatisticsTest {

    private static final double TOLERANCE = 1.0E-9;

    @Test
    public void testCalculateMean() {
        double [] values = new double[] {
            1.0, 2.0, 3.0, 4.0, 5.0, 6.0
        };
        Statistics stats = new Statistics();
        for (double value : values) {
            stats.addValue(value);
        }
        double expected = 3.5;
        Assert.assertEquals(expected, stats.calculateMean(), TOLERANCE);
    }

    @Test
    public void testCalculateVariance() {
        double [] values = new double[] {
                1.0, 2.0, 3.0, 4.0, 5.0, 6.0
        };
        Statistics stats = new Statistics();
        for (double value : values) {
            stats.addValue(value);
        }
        double expected = 3.5;
        Assert.assertEquals(expected, stats.calculateVariance(), TOLERANCE);
    }


    @Test
    public void testCalculateStandardDeviation() {
        double [] values = new double[] {
                1.0, 2.0, 3.0, 4.0, 5.0, 6.0
        };
        Statistics stats = new Statistics();
        for (double value : values) {
            stats.addValue(value);
        }
        double expected = Math.sqrt(3.5);
        Assert.assertEquals(expected, stats.calculateStandardDeviation(), TOLERANCE);
    }

}
于 2012-08-15T23:24:17.740 に答える
1

平均と標準偏差は合計を使用して計算されるため、これらに適切なアキュムレータを簡単に実装できます。次に、実際の値が必要になったら、残りの計算 (特に除算) を終了します。

入力ごとに周波数の 1 つをインクリメントするため、二乗和は扱いにくい部分です。これに対処する 1 つの方法は、(適切なデータ構造を使用して) これまでに表示された各色のカウントを維持することです。次に、入力に色が表示されたら、前の正方形を差し引いて、新しい正方形を追加します (または、2 つの正方形の差をアキュムレータに追加することもできます)。

ここで説明するアルゴリズムの実装は読者に任せます。

于 2012-08-15T23:27:48.950 に答える