0

最近、多数 (約 800,000,000) の double の平均と標準偏差を計算する必要があります。double が 8 バイトかかることを考慮すると、すべての double が RAM に読み込まれる場合、約 6 GB かかります。C++ やその他の高級言語で分割統治法を使用できると思いますが、それは面倒です。R、Scilab、Octave などの高級言語でこれを一度に行う方法はありますか? ありがとう。

4

3 に答える 3

1

R-Grid や Hadoop をうまく利用できるようです。

もちろん、すべての値をメモリに読み込まなくても、平均偏差と標準偏差の両方を簡単に計算できることがわかります。この Java クラスのように、現在の合計を維持するだけです。必要なのは総和、二乗総和、点数だけです。最小値と最大値を無料で保持します。

これにより、map-reduce がどのように機能するかも明確になります。Statistics のいくつかのインスタンスをインスタンス化し、それぞれに合計、平方和、および 800M ポイントの部分のポイント数を保持させます。次に、reduce ステップでそれらを結合し、同じ式を使用して最終結果を取得します。

import org.apache.commons.lang3.StringUtils;

import java.util.Collection;

/**
 * Statistics accumulates simple statistics for a given quantity "on the fly" - no array needed.
 * Resets back to zero when adding a value will overflow the sum of squares.
 * @author mduffy
 * @since 9/19/12 8:16 AM
 */
public class Statistics {
    private String quantityName;
    private int numValues;
    private double x;
    private double xsq;
    private double xmin;
    private double xmax;

    /**
     * Constructor
     */
    public Statistics() {
        this(null);
    }

    /**
     * Constructor
     * @param quantityName to describe the quantity (e.g. "heap size")
     */
    public Statistics(String quantityName) {
        this.quantityName = (StringUtils.isBlank(quantityName) ? "x" : quantityName);
        this.reset();
    }

    /**
     * Reset the object in the event of overflow by the sum of squares
     */
    public synchronized void reset() {
        this.numValues = 0;
        this.x = 0.0;
        this.xsq = 0.0;
        this.xmin = Double.MAX_VALUE;
        this.xmax = -Double.MAX_VALUE;
    }

    /**
     * Add a List of values
     * @param values to add to the statistics
     */
    public synchronized void addAll(Collection<Double> values) {
        for (Double value : values) {
            add(value);
        }
    }

    /**
     * Add an array of values
     * @param values to add to the statistics
     */
    public synchronized void allAll(double [] values) {
        for (double value : values) {
            add(value);
        }
    }

    /**
     * Add a value to current statistics
     * @param value to add for this quantity
     */
    public synchronized void add(double value) {
        double vsq = value*value;
        ++this.numValues;
        this.x += value;
        this.xsq += vsq; // TODO: how to detect overflow in Java?
        if (value < this.xmin) {
            this.xmin = value;
        }
        if (value > this.xmax) {
            this.xmax = value;
        }
    }

    /**
     * Get the current value of the mean or average
     * @return mean or average if one or more values have been added or zero for no values added
     */
    public synchronized double getMean() {
        double mean = 0.0;
        if (this.numValues > 0) {
            mean = this.x/this.numValues;
        }
        return mean;
    }

    /**
     * Get the current min value
     * @return current min value or Double.MAX_VALUE if no values added
     */
    public synchronized double getMin() {
        return this.xmin;
    }

    /**
     * Get the current max value
     * @return current max value or Double.MIN_VALUE if no values added
     */
    public synchronized double getMax() {
        return this.xmax;
    }

    /**
     * Get the current standard deviation
     * @return standard deviation for (N-1) dof or zero if one or fewer values added
     */
    public synchronized double getStdDev() {
        double stdDev = 0.0;
        if (this.numValues > 1) {
            stdDev = Math.sqrt((this.xsq-this.x*this.x/this.numValues)/(this.numValues-1));
        }
        return stdDev;
    }

    /**
     * Get the current number of values added
     * @return current number of values added or zero if overflow condition is encountered
     */
    public synchronized int getNumValues() {
        return this.numValues;
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder();
        sb.append("Statistics");
        sb.append("{quantityName='").append(quantityName).append('\'');
        sb.append(", numValues=").append(numValues);
        sb.append(", xmin=").append(xmin);
        sb.append(", mean=").append(this.getMean());
        sb.append(", std dev=").append(this.getStdDev());
        sb.append(", xmax=").append(xmax);
        sb.append('}');
        return sb.toString();
    }
}

そして、これが機能していることを証明する JUnit テストです。

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

import java.util.Arrays;
import java.util.List;

/**
 * StatisticsTest
 * @author mduffy
 * @since 9/19/12 11:21 AM
 */
public class StatisticsTest {
    public static final double TOLERANCE = 1.0e-4;

    @Test
    public void testAddAll() {
        // The test uses a full array, but it's obvious that you could read them from a file one at a time and process until you're done.
        List<Double> values = Arrays.asList( 2.0, 4.0, 4.0, 4.0, 5.0, 5.0, 7.0, 9.0 );
        Statistics stats = new Statistics();
        stats.addAll(values);
        Assert.assertEquals(8, stats.getNumValues());
        Assert.assertEquals(2.0, stats.getMin(), TOLERANCE);
        Assert.assertEquals(9.0, stats.getMax(), TOLERANCE);
        Assert.assertEquals(5.0, stats.getMean(), TOLERANCE);
        Assert.assertEquals(2.138089935299395, stats.getStdDev(), TOLERANCE);
    }
}
于 2012-10-03T16:31:22.487 に答える
1

これが最適であるとは主張していませんが、python (numpy および numexpr モジュールを使用) では、次のことは簡単です (8G RAM マシン上):

import numpy, numpy as np, numexpr
x = np.random.uniform(0, 1, size=8e8)

print x.mean(), (numexpr.evaluate('sum(x*x)')/len(x)-
                (numexpr.evaluate('sum(x)')/len(x))**2)**.5
>>> 0.499991593345 0.288682001731

これは、元の配列より多くのメモリを消費しません。

于 2012-10-03T17:23:03.257 に答える
0

これは素晴らしい挑戦のように見えます。微調整したマージソートで同様のものを作成できませんか? ただのアイデア。ただし、これは動的プログラミングのように見えますが、複数の PC を使用して処理を高速化できます。

于 2012-10-03T16:30:41.630 に答える