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