并行查找中位数 [英] Find a median in parallel

问题描述

如果您有大量数字和一百台计算机， 您将如何找到这些数字的中位数?

If you have one huge amount of numbers and one hundred computers, How would you find the median of the numbers?

推荐答案

使用选择算法.

1. 将数字数组拆分为100个分区.
2. 每个处理器都应使用通用支点将阵列分为两组(左/右)
3. 然后每个处理器都应将这两个组的大小发送给组长
4. 领导者应计算出哪个小组较小，并广播一条消息以摆脱那些小组中的一个.
5. 返回第2步，直到找到中位数

此解决方案的平均运行时间为O(n) 为了使其成为O(n)的渐近运行时间，每个处理器应将数字分成5个元素的组，找到每个组的中位数 (使用插入排序)并将这些中位数返回给领导者，领导者将选择这些中位数的中位数(使用相同的算法)， 将成为枢纽

this solution has an avg runtime of O(n) in order to make it asymptotic runtime of O(n), each processor should split the numbers to groups of 5 elements find the median of each group (using insertion sort) and send those medians back to the leader, the leader will choose the median of those medians (using the same algo) and that will be the pivot

阅读Wiki文章- http://en.wikipedia.org/wiki/Selection_algorithm

这篇关于并行查找中位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！