作者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