机器学习和生物信息学实验室联盟

标题: 来一道很难的算法题 [打印本页]

作者: 小疯纸一枚 时间: 2015-1-6 23:45
标题: 来一道很难的算法题
以往我们求均值，一般做法是，出一堆数的sum 以及这一堆数的个数n , 然后 sum / n 。
现在问题来了， n 已经超出了机器的表示范围，long , double 来表示n都呈负数，更不用说sum 了。
如何求这一堆的数的均值？？？（假设这一堆数可以一个个读取）

作者: zouquan 时间: 2015-1-7 08:40
咋读取啊？long和double都不行，用string？

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

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

作者: 小疯纸一枚 时间: 2015-1-7 13:11
本帖最后由小疯纸一枚于 2015-1-7 13:14 编辑

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 15:06

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

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

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

作者: 小疯纸一枚 时间: 2015-1-7 16:37

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 时间: 2015-1-7 21:53
我觉得当实际问题升级到这种层面，用MapReduce分而治之求解近似值就可以了。这又是哪家公司的变态面试题。

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

作者: 小疯纸一枚 时间: 2015-1-9 17:25

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

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

欢迎光临机器学习和生物信息学实验室联盟 (http://123.57.240.48/)