问题描述
Is there a fast algorithm to run on MapReduce framework to find the Median from a huge Integer set?
Here's how I would do it. This is a sort of parallel version of sequential quickselect. (Some map/reduce tools might not let you do things quite as easily...)
Pick a small, arbitrary chunk of the input set. Sort this sequentially. We're going to use these as a whole bunch of pivots, in parallel. Call this array pivots
, and let its size be k
.
Perform a map/reduce as follows: for each value x
in the input set, binary-search to find x
's position relative to pivots
; call this position bucket(x)
. This is an integer between 0
and k
. The reduce step is to count the number of elements in each bucket; define bucket[b]
to be the number of x
with bucket(x) = b
.
The median must be in the "median bucket." Pick out all the values in that median bucket, and use a traditional sequential selection algorithm to find the element with the correct index.
这篇关于使用 MapReduce 查找大整数集的中位数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!