使用 MapReduce 查找大整数集的中值
是否有一种快速算法可以在 MapReduce 框架上运行以从巨大的整数集中找到中位数？
Is there a fast algorithm to run on MapReduce framework to find the Median from a huge Integer set?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我就是这样做的。这是顺序快速选择的一种并行版本。 （某些映射/归约工具可能无法让您轻松完成任务...）
选择输入集中的一个任意小块。按顺序对此进行排序。我们将并行地将它们用作一整套枢轴。将此数组称为
pivots，并使其大小为k。按如下方式执行映射/归约：对于输入集中的每个值
x，进行二分搜索以查找x相对于pivots的位置;将此位置称为bucket(x)。这是0和k之间的整数。 reduce步骤是统计每个bucket中元素的数量；将bucket[b]定义为x的数量，其中bucket(x) = b。中位数必须位于“中位数桶”中。选出该中值桶中的所有值，并使用传统的顺序选择算法来查找具有正确索引的元素。
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 bek.Perform a map/reduce as follows: for each value
xin the input set, binary-search to findx's position relative topivots; call this positionbucket(x). This is an integer between0andk. The reduce step is to count the number of elements in each bucket; definebucket[b]to be the number ofxwithbucket(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.