我想这也是个经典问题，这个问题都问烂了。数据量如果放在一台机器上不合适，那么很多人都会想到，可以map-reduce啊，每台机器上进行map运算都求出最大的k个，然后汇总到一台机器上去reduce求出最终的第k个（如果机器很多，这个汇总过程可以是多级汇总）。
可是，这个回答无意之中假定了一个条件，让问题变得好处理很多。这个条件就是——k不大。
假如这堆数很多，因此放在若干台机器上，但是如果这个k也非常大呢？即便要想把这k个数放到一台机器上去找也不可行。
这时候问题就有点复杂了，也有不同的处理方法。一种办法是，通过某种排序方法（比如基于不断归并的外排序），给每台机器上的数据都排好序，然后从中找一个（猜一个可能为所求的数）数作为pivot，并且在每台机器上这些有序数里面都明确这个pivot的位置。假设machine[i]表示第i台机器上，pivot这个数所处的序列，那么把这些machine[i]累加起来，得到的数sum去和k比较：
- 如果sum==k，那这个数就找到了；
- 如果sum<k，说明这个数在每台机器上machine[i]往后，直到结尾的这一段数中；
- 如果sum>k，说明这个数在每台机器上machine[i]往前，直到开头的这一段数中。
如是递归求解。
当然这个方法依然有许多地方可以改进，比如这个预先进行的外排序，未必要完全进行，是可以通过稳重介绍的理论优化掉或者部分优化掉的。
Read full article from 求第K个数的问题 | 四火的唠叨
No comments:
Post a Comment