Sim*_*mon 40 java algorithm statistics
我需要计算一组非常大的双精度(10 ^ 9值)的平均值.这些值的总和超过了double的上限,那么是否有人知道用于计算平均值的任何巧妙的小技巧,也不需要计算总和？
我使用的是Java 1.5.
mar*_*nus 167
您可以迭代计算平均值.这个算法简单,快速,你只需要处理每个值一次,变量永远不会大于集合中的最大值,所以你不会得到溢出.
double mean(double[] ary) {
double avg = 0;
int t = 1;
for (double x : ary) {
avg += (x - avg) / t;
++t;
}
return avg;
}
循环内部avg始终是到目前为止处理的所有值的平均值.换句话说,如果所有值都是有限的,则不应该溢出.
Dav*_*ide 12
恕我直言,解决你的问题最强大的方法是
这种方法的一个好处是它可以很好地扩展,如果你有很多元素可以求和 - 并且有大量的处理器/机器用来做数学
ang*_*son 12
我想问你的第一个问题是:
如果没有,那么你别无选择,只能求和,计算,除以平均值.如果Double没有足够高的精度来处理这个,那么运气不好,你不能使用Double,你需要找到一个可以处理它的数据类型.
如果,另一方面,你不知道值的数量事先,你可以看看你真的在做什么和改变如何你做到这一点,但保持了整体效果.
存储在某个集合A中的N值的平均值是:
A[0] A[1] A[2] A[3] A[N-1] A[N]
---- + ---- + ---- + ---- + .... + ------ + ----
N N N N N N
要计算此结果的子集,可以将计算拆分为大小相等的集合,这样就可以对3值集合执行此操作(假设值的数量可以除以3,否则需要使用不同的除数)
/ A[0] A[1] A[2] \ / A[3] A[4] A[5] \ // A[N-1] A[N] \
| ---- + ---- + ---- | | ---- + ---- + ---- | \\ + ------ + ---- |
\ 3 3 3 / \ 3 3 3 / // 3 3 /
--------------------- + -------------------- + \\ --------------
N N N
--- --- ---
3 3 3
请注意,您需要具有相同大小的集合,否则最后一组中的数字与之前的所有集合相比没有足够的值,将对最终结果产生更大的影响.
按顺序考虑数字1-7,如果你选择3的设置大小,你将得到这个结果:
/ 1 2 3 \ / 4 5 6 \ / 7 \
| - + - + - | + | - + - + - | + | - |
\ 3 3 3 / \ 3 3 3 / \ 3 /
----------- ----------- ---
y y y
这使:
2 5 7/3
- + - + ---
y y y
如果所有集合的y为3,则得到以下结果:
2 5 7/3
- + - + ---
3 3 3
这使:
2*3 5*3 7
--- + --- + ---
9 9 9
这是:
6 15 7
- + -- + -
9 9 9
总计:
28
-- ~ 3,1111111111111111111111.........1111111.........
9
1-7的平均值是4.显然这不起作用.请注意,如果您使用数字1,2,3,4,5,6,7,0,0执行上述练习(请注意那里的两个零),那么您将获得上述结果.
换句话说,如果你不能将值的数量分成相同大小的集合,那么最后一个集合将被计为好像它具有与它之前的所有集合相同的值的数量,但它将用零填充为零所有缺失的值.
所以,你需要同样大小的套装.如果您的原始输入集包含素数值,那就太好了.
我在这里担心的是失去精确度.Double如果它最初不能保持整个值的总和,我不完全确定在这种情况下会给你足够的精度.
Boz*_*zho 11
除了使用已建议的更好方法之外,您还可以使用BigDecimal进行计算.(请记住它是不可变的)
Aln*_*tak 10
请澄清值的潜在范围.
假设double具有范围〜= +/- 10 ^ 308,并且您将10 ^ 9值相加,则您的问题中建议的表观范围是10 ^ 299的数量级.
这似乎有点,不太可能......
如果你的价值观真的是那么大,然后用正常的两倍你只拿到了17显著十进制数字一起玩,所以你会扔掉约280位值得的信息之前,你甚至可以考虑一下平均的值.
对于任何一组数字,我也会注意到(因为没有其他人有)X:
mean(X) = sum(X[i] - c) + c
-------------
N
任何常数c.
在这个特定问题中,设置c = min(X) 可能会大大降低求和期间溢出的风险.
我谦卑地建议问题陈述不完整......？
双精度可以除以2的幂而不会损失精度.因此,如果您唯一的问题是,如果总和的绝对大小,您可以在汇总它们之前预先缩放您的数字.但是对于这样大小的数据集,仍然存在这样的风险:您将遇到向较大的数字添加小数字的情况,并且小数字最终将被大部分(或完全)忽略.
例如,当你添加2.2e-20到9.0e20时,结果是9.0e20,因为一旦调整了比例以便它们的数字可以加在一起,较小的数字就是0.双打只能容纳大约17位,你会需要超过40位才能将这两个数字加在一起而不会丢失.
因此,根据您的数据集和您可以承受的精度数字,您可能需要做其他事情.将数据分成集将有所帮助,但保持精度的更好方法可能是确定粗略平均值(您可能已经知道这个数字).然后在求和之前从粗略平均值中减去每个值.这样你就可以将距离与平均距离相加,所以你的总和永远不会变得非常大.
然后取平均增量,并将其加到粗略的总和中,得到正确的平均值.跟踪最小和最大增量也将告诉您在求和过程中丢失了多少精度.如果你有很多时间并且需要非常准确的结果,你可以迭代.
| 归档时间： |
|
| 查看次数： |
24781 次 |
| 最近记录： |