※ 引述《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