0

我最近需要计算大量（约 800,000,000）双打的均值和标准差。考虑到一个 double 需要 8 个字节，如果所有的 double 都读入 ram，大约需要 6 GB。我想我可以对 C++ 或其他高级语言使用分而治之的方法，但这似乎很乏味。有没有一种方法可以让我使用 R、Scilab 或 Octave 等高级语言一次性完成所有这些操作？谢谢。

4

3 回答 3

1

听起来您可以充分利用 R-Grid 或 Hadoop。

当然，您意识到计算平均值和标准差很容易，而无需将所有值读入内存。只需保持一个运行总数，就像这个 Java 类一样。您所需要的只是总和、平方和和点数。我免费保留最小值和最大值。

这也清楚地说明了 map-reduce 是如何工作的。您将实例化几个统计实例，让它们中的每一个保持总和、平方和以及它们在 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 回答