作者sorryChen (陈扬和)
看板Programming
标题用10000台电脑找中位数
时间Wed May 9 14:31:29 2012
其实这个Mapper/Reducer的问题
给定很多很大的档, 每个档各有1TB个数(memory 放不下)
如何用10000个Mapper+Reducer 找所有数的中位数呢?
我自己是想先让每台若用selection method在Mapper 把每个档的数分成两堆
一堆比较大的数 一堆比较小的数, 可能分堆用pivot的个数算第三堆
但在reducer阶段要怎麽靠这些讯息找中位数呢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 207.151.93.199
1F：推 Foremanytz:总资料量已知?未知?还在变动中? 163.15.40.185 05/10 08:57
2F：推 Wush978:若先把资料范围分成若干组, 各电脑统计自 220.137.1.162 05/10 21:05
3F：→ Wush978:己的资料在各组的范围的个数, 就可以得知 220.137.1.162 05/10 21:05
4F：→ Wush978:中位数落在那一组, 重复做起次就可能把资 220.137.1.162 05/10 21:05
5F：→ Wush978:料缩小到好处理的范围了 220.137.1.162 05/10 21:05
6F：→ yauhh:楼上这样是否意味有个mapper是从各电脑送到 59.112.227.163 05/11 00:02
7F：→ yauhh:要比对范围的该电脑,套到每笔资料比对一下? 59.112.227.163 05/11 00:03
8F：→ yauhh:可是如果各电脑没有统计不在其他各组范围的 59.112.227.163 05/11 00:06
9F：→ yauhh:数字是多少个大,多少个少,要怎麽定位范围及 59.112.227.163 05/11 00:06
10F：→ yauhh:中位数落在哪一组? 59.112.227.163 05/11 00:06
11F：→ sorryChen:谢谢诸位大师, 总量想成已知,固定 207.151.93.138 05/11 07:04
12F：→ sorryChen:请问实计上要怎麽好的"分组"呢 207.151.93.138 05/11 07:20
13F：→ sorryChen:其实我只有写过一轮mapper/reducer 207.151.93.138 05/11 07:20
14F：→ sorryChen:要怎麽把上个mapper/reducer的结果 207.151.93.138 05/11 07:21
15F：→ sorryChen:送到下个mapper/reducer用呢? 207.151.93.138 05/11 07:21
16F：→ sorryChen:output档案吗? 207.151.93.138 05/11 07:21
17F：→ yauhh:不敢,你有实务经验,你才是前辈. 59.112.227.77 05/11 19:21
18F：→ yauhh:看手册,只看到output有档案方式...... 59.112.227.77 05/12 11:09
19F：→ damody:要排序後才知道吧？中位的中位不是中位 140.118.175.35 05/14 04:34
20F：推 hilorrk:是要精准的中位数, 还是能够容许误差? 1.160.72.89 05/15 20:01
21F：→ sorryChen:精准的中位应该比较难, 但selection 108.94.138.88 05/18 07:30
22F：→ sorryChen:应该不用排完吧 108.94.138.88 05/18 07:30