(5) Distributed Algorithms: What is the distributed algorithm to determine the median of arrays of integers located on different computers? - Quora
Suppose you have a master node (or are able to use a consensus protocol to elect a master from among your servers). The master first queries the servers for the size of their sets of data, call this n, so that it knows to look for the k = n/2 largest element.
The master then selects a random server and queries it for a random element from the elements on that server. The master broadcasts this element to each server, and each server partitions its elements into those larger than or equal to the broadcasted element and those smaller than the broadcasted element.
Each server returns to the master the size of the larger-than partition, call this m. If the sum of these sizes is greater than k, the master indicates to each server to disregard the less-than set for the remainder of the algorithm. If it is less than k, then the master indicates to disregard the larger-than sets and updates k = k - m. If it is exactly k, the algorithm terminates and the value returned is the pivot selected at the beginning of the iteration.
If the algorithm does not terminate, recurse beginning with selecting a new random pivot from the remaining elements.
http://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html
http://matpalm.com/median/distributing.html
X. guess=min+max/2, then loop ?
http://blog.csdn.net/jiyanfeng1/article/details/8083730
2. 举例归纳。确立问题的边界。
1 4 5 6 15 44 55
3 7 11 12 13 18 35
总的顺序为 1 3 4 5 6 7 11 12 13 15 18 35 44 55.
总共 14个数，中值为 11 12 。
直白的想法，这是归并排序吗，带宽不允许。
当然，如果题目变成了，求任意个位置的数值，那么归并排序就是一个完全的解空间。
现在题目很特殊，就是一个中值，我们要充分利用这个内涵。
3. 发掘约束，削减解空间。
观察样本，利用直觉，第一排中间是6，第二是12，小于6的全部抛弃， 大于12的全部抛弃。
中值在 6 15 44 55， 3 7 11 12中寻找，可以吗？
答案好像是可以的，假设中值在问号位置，
* ？ * 6 15 44 55
3 7 11 12 13 18 35
那么 ？ < 6 <12, 那么 ？ 排在整个序列中，那么它后面还有 4+4> (14/2)了，所以它的位置肯定不为中间，那么同样道理，中值也不肯出现在 下一排的 比较大的那部分，
反证法证完毕。
我们可以通过传送一个值，一下排除一半的数据，同样道理，我们继续总剩下的序列中，通过这个方式，
递归地排除好多数据，最后夹逼到中值，有点类似求极限，呵呵。
http://blog.csdn.net/zdl1016/article/details/4676882
查找N个元素中的第K个小的元素，假设内存受限，仅能容下K/4个元素。分趟查找，
第一趟，用堆方法查找最小的K/4个小的元素，同时记录剩下的N-K/4个元素到外部文件。
第二趟，用堆方法从第一趟筛选出的N-K/4个元素中查找K/4个小的元素，同时记录剩下的N-K/2个元素到外部文件。
。。。
第四趟，用堆方法从第一趟筛选出的N-K/3个元素中查找K/4个小的元素，这是的第K/4小的元素即使所求。
Read full article from (5) Distributed Algorithms: What is the distributed algorithm to determine the median of arrays of integers located on different computers? - Quora
Suppose you have a master node (or are able to use a consensus protocol to elect a master from among your servers). The master first queries the servers for the size of their sets of data, call this n, so that it knows to look for the k = n/2 largest element.
The master then selects a random server and queries it for a random element from the elements on that server. The master broadcasts this element to each server, and each server partitions its elements into those larger than or equal to the broadcasted element and those smaller than the broadcasted element.
Each server returns to the master the size of the larger-than partition, call this m. If the sum of these sizes is greater than k, the master indicates to each server to disregard the less-than set for the remainder of the algorithm. If it is less than k, then the master indicates to disregard the larger-than sets and updates k = k - m. If it is exactly k, the algorithm terminates and the value returned is the pivot selected at the beginning of the iteration.
If the algorithm does not terminate, recurse beginning with selecting a new random pivot from the remaining elements.
http://www.fusu.us/2013/07/median-in-large-set-across-1000-servers.html
http://matpalm.com/median/distributing.html
X. guess=min+max/2, then loop ?
http://blog.csdn.net/jiyanfeng1/article/details/8083730
2. 举例归纳。确立问题的边界。
1 4 5 6 15 44 55
3 7 11 12 13 18 35
总的顺序为 1 3 4 5 6 7 11 12 13 15 18 35 44 55.
总共 14个数，中值为 11 12 。
直白的想法，这是归并排序吗，带宽不允许。
当然，如果题目变成了，求任意个位置的数值，那么归并排序就是一个完全的解空间。
现在题目很特殊，就是一个中值，我们要充分利用这个内涵。
3. 发掘约束，削减解空间。
观察样本，利用直觉，第一排中间是6，第二是12，小于6的全部抛弃， 大于12的全部抛弃。
中值在 6 15 44 55， 3 7 11 12中寻找，可以吗？
答案好像是可以的，假设中值在问号位置，
* ？ * 6 15 44 55
3 7 11 12 13 18 35
那么 ？ < 6 <12, 那么 ？ 排在整个序列中，那么它后面还有 4+4> (14/2)了，所以它的位置肯定不为中间，那么同样道理，中值也不肯出现在 下一排的 比较大的那部分，
反证法证完毕。
我们可以通过传送一个值，一下排除一半的数据，同样道理，我们继续总剩下的序列中，通过这个方式，
递归地排除好多数据，最后夹逼到中值，有点类似求极限，呵呵。
http://blog.csdn.net/zdl1016/article/details/4676882
查找N个元素中的第K个小的元素，假设内存受限，仅能容下K/4个元素。分趟查找，
第一趟，用堆方法查找最小的K/4个小的元素，同时记录剩下的N-K/4个元素到外部文件。
第二趟，用堆方法从第一趟筛选出的N-K/4个元素中查找K/4个小的元素，同时记录剩下的N-K/2个元素到外部文件。
。。。
第四趟，用堆方法从第一趟筛选出的N-K/3个元素中查找K/4个小的元素，这是的第K/4小的元素即使所求。
Read full article from (5) Distributed Algorithms: What is the distributed algorithm to determine the median of arrays of integers located on different computers? - Quora
