用10000台電腦找中位數

看板Programming作者 (陳揚和)時間12年前 (2012/05/09 14:31), 編輯推噓3(3推 0噓 19→)
留言22則, 6人參與, 最新討論串1/2 (看更多)
其實這個Mapper/Reducer的問題 給定很多很大的檔, 每個檔各有1TB個數(memory 放不下) 如何用10000個Mapper+Reducer 找所有數的中位數呢? 我自己是想先讓每台若用selection method在Mapper 把每個檔的數分成兩堆 一堆比較大的數 一堆比較小的數, 可能分堆用pivot的個數算第三堆 但在reducer階段要怎麼靠這些訊息找中位數呢 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 207.151.93.199
推
05/10 08:57, , 1F
總資料量已知?未知?還在變動中?
05/10 08:57, 1F
推
05/10 21:05, , 2F
若先把資料範圍分成若干組, 各電腦統計自
05/10 21:05, 2F
→
05/10 21:05, , 3F
己的資料在各組的範圍的個數, 就可以得知
05/10 21:05, 3F
→
05/10 21:05, , 4F
中位數落在那一組, 重複做起次就可能把資
05/10 21:05, 4F
→
05/10 21:05, , 5F
料縮小到好處理的範圍了
05/10 21:05, 5F
→
05/11 00:02, , 6F
樓上這樣是否意味有個mapper是從各電腦送到
05/11 00:02, 6F
→
05/11 00:03, , 7F
要比對範圍的該電腦,套到每筆資料比對一下?
05/11 00:03, 7F
→
05/11 00:06, , 8F
可是如果各電腦沒有統計不在其他各組範圍的
05/11 00:06, 8F
→
05/11 00:06, , 9F
數字是多少個大,多少個少,要怎麼定位範圍及
05/11 00:06, 9F
→
05/11 00:06, , 10F
中位數落在哪一組?
05/11 00:06, 10F
→
05/11 07:04, , 11F
謝謝諸位大師, 總量想成已知,固定
05/11 07:04, 11F
→
05/11 07:20, , 12F
請問實計上要怎麼好的"分組"呢
05/11 07:20, 12F
→
05/11 07:20, , 13F
其實我只有寫過一輪mapper/reducer
05/11 07:20, 13F
→
05/11 07:21, , 14F
要怎麼把上個mapper/reducer的結果
05/11 07:21, 14F
→
05/11 07:21, , 15F
送到下個mapper/reducer用呢?
05/11 07:21, 15F
→
05/11 07:21, , 16F
output檔案嗎?
05/11 07:21, 16F
→
05/11 19:21, , 17F
不敢,你有實務經驗,你才是前輩.
05/11 19:21, 17F
→
05/12 11:09, , 18F
看手冊,只看到output有檔案方式......
05/12 11:09, 18F
→
05/14 04:34, , 19F
要排序後才知道吧？中位的中位不是中位
05/14 04:34, 19F
推
05/15 20:01, , 20F
是要精準的中位數, 還是能夠容許誤差?
05/15 20:01, 20F
→
05/18 07:30, , 21F
精準的中位應該比較難, 但selection
05/18 07:30, 21F
→
05/18 07:30, , 22F
應該不用排完吧
05/18 07:30, 22F
‣ 更多 sorryChen 的文章
文章代碼(AID): #1FgWz3CQ (Programming)
‣ 更多 sorryChen 的文章
文章代碼(AID): #1FgWz3CQ (Programming)