Re: 用10000台電腦找中位數
※ 引述《sorryChen (陳揚和)》之銘言：
: 其實這個Mapper/Reducer的問題
: 給定很多很大的檔, 每個檔各有1TB個數(memory 放不下)
: 如何用10000個Mapper+Reducer 找所有數的中位數呢?
: 我自己是想先讓每台若用selection method在Mapper 把每個檔的數分成兩堆
: 一堆比較大的數 一堆比較小的數, 可能分堆用pivot的個數算第三堆
: 但在reducer階段要怎麼靠這些訊息找中位數呢
哇嗚,10000台電腦,應該是很好的技術工作環境吧.
我是這樣想,如果mapper function做排序,也就是拿到一列數字,把數字排好之後,
丟出去. 然後另外有幾個mapper function做附加資訊的整理,拿到一列排好的數字,
就把數列的長度和前,後邊界丟出來,
面對一大堆排好的數列, reducer function會很像是 merge-sort function.
先有一個reducer function把全部的長度加起來,這樣就知道中位數落在哪幾個數列中.
也許另外有些mapper function把中位數落入的陣列保留下來,丟掉其他陣列,
而中位數的offset需要適度更改.
然後有個reducer function給每個排序好的數列在全體數目中下定位,定位一個數列
是在全體數目的前段,中段或是後段. 前段的資料較先讓以下的reducers取值.然後
有一些reducer開始用merge sort的手段工作,拿到幾個排序好而且比較靠近所以可以
合併的數列,並且知道目標要在收集多少個數字之後認定中位數,就開始用merge sort
慢慢把幾個數列消化掉, 如果有很多個reducers分別合併幾個有序數列,後來還可以
有幾個reducers把合併後的數列再合併.等收集到中位數之後,reducing就可以停.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.112.228.21
討論串 (同標題文章)
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
