0

我有一个二维字节数组，如下所示：

int n = 100000;
int d = 128;
byte[][] samples = new byte[n][d]
/* proceed to fill samples with some delicious data */
byte[] mean = new byte[d];
findMean(mean,samples);

我的 findMean 函数继续填充均值，使得：

mean[k] = mean(samples[:][k])

到目前为止很简单。问题是，由于溢出问题，这个平均函数不能简单地求和和除。所以我目前的尝试是计算一个运行平均值，它的主力看起来像这样：

for(int i = 0; i < samples.length; i++){
    byte diff = samples[i][k] - mean[k]
    mean[k] = (byte)((double)mean[k] + (Math.round( (double) ( diff ) / (double) (i + 1) )))

现在这根本不起作用，每一轮精度损失都会导致平均值与正确值相差甚远，我已经在 1000 个随机样本的小（因此可计算）集上验证了这一点。

此外，由于我首先试图通过使用字节数组来避免内存问题，因此分配一个大的代理浮点数组来计算真正的平均值，然后再转换为一个字节是完全不可能的。

以块的形式加载这些数据......好吧，这是可能的，但我正在考虑我的最终选择，无论如何，这只是将问题转移到块大小？

无论如何，使用运行算法准确计算字节数组的平均值以避免溢出问题。这里有好的解决方案吗？

干杯

4

3 回答 3

2

您可以使用更大的整数类型（long / bigInt），甚至是任意精度的算术，来计算总和。在这种情况下，您实际上并不需要在线算法，尽管保留它除了使计算变慢之外不会产生任何影响。

当您将总和除以计数来计算平均值时，您当然会受到您使用的浮点类型的精度的限制，因此请记住这一点。如果您沿着 APA 路线走，这将不是问题。

于 2010-09-02T17:14:22.377 回答
0

正确的。所以我决定我必须至少持有一个 double 来计算任何给定维度的平均值。

问题是我通过以下方式解决了这个问题：

for each sample, get the array it is to update
    for each dimension in that array, calculate it's running mean given the new sample

这样做的问题是必须持有一个 double[][] 来保存要更新的每个元素的每个维度的当前运行平均值。因此，我现在重新安排了我的循环，看起来更像这样：

for each array to be updated
    for each sample that will update this array
        for each dimension in the array to be updated calculate the running mean

这种方式需要一些预处理，我需要遍历所有样本以查找哪些样本将更新哪些数组（单个索引数组），但我的总体节省是我现在可以持有一个为每个样本更新的 SINGLE double它为该样本的给定维度更新给定数组。

然后可以将这个双精度转换为适当的低精度类型，在我的例子中是一个字节。

我最初打算在存储空间方面的总体节省是：

用字节替换整数（花费 4*128*numberOfSamples）（花费 1*128*numberOfSamples）

那没有用，但我现在制定了一个解决方案，其成本如下：（128 * numberOfSamples + numberOfSamples）。节省 127*numberOfSamples。在我最坏的情况下，内存接近 15Gb :-)

所以，是的，我们走了，睡一觉，我回答了我自己的问题。

感谢各位大侠的帮助！

于 2010-09-03T12:52:58.957 回答
0

如果你计算 128 意味着你不能分配 128 双打（dmean[] 说）来持有它们，使用

双差异 = 样本[i][k] - dmean[k];

dmean[k] = dmean[k] + diff/(i+1) ;

更新是什么意思？

于 2010-09-02T17:23:07.347 回答