来一道很难的算法题

小疯纸一枚

以往我们求均值， 一般做法是， 出一堆数的sum 以及 这一堆数的个数n , 然后 sum / n  。
现在问题来了， n 已经超出了机器的表示范围，long , double 来表示n都呈负数，更不用说sum 了。
如何求这一堆的数的均值？？？（假设这一堆数可以一个个读取）

zouquan

咋读取啊？long和double都不行，用string？

那也不用啥算法了，写个方法可以计算string代表的数值求均值，结果还得存到string中。

典型的map reduce啊，把字符串分散到各台节点上，求均值后汇总再求均值。

小疯纸一枚

zouquan 发表于 2015-1-7 08:40
咋读取啊？long和double都不行，用string？

那也不用啥算法了，写个方法可以计算string代表的数值求均值 ...

读取只能一条条读取，就是来一个数读一个数。
分块求均值有一个问题：
2，4，6，8，4，2（假设总数目6在计算机中不可存，2 可以）这样两个分成一块然后求均值是没有问题的
第一步求出，3，7，3，然后汇总求 13/3 , 答案正确。
但是，如果出现一个尾巴，2，4，6，8，4，2，3 （按照两个分块的时候）
第一步求均值 3，7，3，3， 最后的结果是不对的。
也就是说分组每组个数需要一样，但是总数n又不可存。

zouquan

小疯纸一枚 发表于 2015-1-7 13:11
读取只能一条条读取，就是来一个数读一个数。
分块求均值有一个问题：
2，4，6，8，4，2（假设总数目 ...

哦，你是说每一个数都可存，比如可以是int，但是总数n太多，是吧？

那确实有点问题.没想好有啥办法。比如long如果最大可以2的32次方，而n实际要是比2的100次方还大，那基本就是无解了吧。。。

小疯纸一枚

zouquan 发表于 2015-1-7 15:06
哦，你是说每一个数都可存，比如可以是int，但是总数n太多，是吧？

那确实有点问题.没想好有啥办法。 ...

每个数都可存，并且都是int ， 但是总数n 太多。

想了两个： 1 ，首先扫一遍整个数据集，获得n的个数，n用string来保存。
                2， 然后对n 做因子分解， 弄出( m * h ) , 大整数除法（需要多次）
                3、 然后再扫一遍数据集，每 m 为一块，共h 块
              缺点，扫两边数据集， 大整数除法要运算多次，而且因子分解不一定能成。
另一个：
           1； 随意分块，假设10000个数分一块求均值， 然后剩下一个尾巴总和为W ,长度为wl ，同时用string保存总数 n ;
           2； 前面均匀分块的数用mapreduce的可以求出均值avg1 ,
           3； 实际要的均值
                               Avg = (avg1*(n-wl)+W) / n
                                     = (avg1*n - avg1*wl +W)/n
                                     =agv1 + ((W-avg1*wl)/n)
           上面， avg1 ， W， wl , W-avg1*wl 都是可求，唯一不可求的是n , 求出（W-avg1*wl）用string 保存，然后与保存 n 的string 做大整数除法。这样就只需要计算一次大整数。
         
                             

xmubingo

我觉得当实际问题升级到这种层面，用MapReduce分而治之求解近似值就可以了。这又是哪家公司的变态面试题。

Mr.Vege求好运

赞同师兄，这种显然近似值就足够了，当总数非常多的时候，一个数的值并不能改变整体均值的趋势

小疯纸一枚

Mr.Vege求好运 发表于 2015-1-9 16:58
赞同师兄，这种显然近似值就足够了，当总数非常多的时候，一个数的值并不能改变整体均值的趋势

算法嘛，重点是培养考虑问题的全面性和解决问题的能力， 实际问题近似满足以及高精度要求都是有可能遇到