使用 MapReduce 查找大整数集的中位数 [英] Find median of a large integer set using MapReduce

问题描述

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 查找大整数集的中位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！