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 回答