这是一个创建于 2199 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目是分布式排序 已知有 n 个节点，每个节点有长度为 m 的数组。m<<n
现在对这 m*n 个数据进行排序。
我一开始用归并排序，但考官说不行。大家有什么好的解决方案？
 |
1
AFuture 2018-11-18 10:33:06 +08:00 via iPhone
先来一波置换选择，再来一波最佳归并。以上仅一个菜鸡本科学生的观点。
|
 |
2
ytmsdy 2018-11-18 10:40:09 +08:00
m<<n
这个表达的意思是不是 M 远远小于 N 如果是这样的话，需要先把所有的数都拿出来，然后在做排序。 简单一点说就是我要对 1w 个数字进行排序，但是每个数组里面只有 2 到 3 个元素，这种情况下，归并排序并不适合。 |
|
3
ytmsdy 2018-11-18 10:40:41 +08:00
1w 个数字进行排序=====> fix 1w 个数组
|
 |
6
ksco 2018-11-18 11:11:04 +08:00 via Android  4
在楼主的已知条件之上做一些假设。
假设每台机器都有一个固定的编号：1, 2, ..., n。 排序完成后，我们的目标是可以产生一个有序的“流”，因为内存装不下。 方案如下： 首先给每个节点的数组排序，这个没啥好说的。 然后维护一个最小堆，堆的元素是 (节点编号, 当前下标, 具体数值) 这样的一个三元组，当然堆的排序依据是“具体数值”。 排序的方法是，每次从堆里面弹出一个最小的元素，放入流中，再把这个元素的当前下标步进 1，取该下标的值，生成新的三元组放回堆中，然后循环。 === 最后无耻一下：我做了个公众号“每天一道编程题”，欢迎关注～ |
|
7
ksco 2018-11-18 11:17:47 +08:00
|
 |
9
shidenggui 2018-11-18 12:23:08 +08:00 4
这个应该是属于 external sorting 里面的 k-way merge。下面的算法来自《 Data Structures and Algorithm Analysis in C 》:
首先令 N = m * n 表示所有需要排序的量，M 表示内存能容纳的最大数据量。 然后在内存中维护一个最小堆，第一次读 M / m 个节点，将最小堆填充满，然后每次 pop 一个最小的值依序写入到对应的节点中，这时内存中会多出一个空位，此时可以继续读取数据，如果读取的值大于 pop 出的最小值，则将其加入最小堆参与这一轮的排序，否则将其留在 pop 出最小值后留下的 dead space 中，等待下一轮排序。 这里有一个问题是每个节点应该写入多少次排序好的数组呢？比如都写入一次，则需要读取的节点数太多了。根据书上的方法，根据 N / M 估计第一次排序产生的数组数量，然后计算 kth order 斐波那契数列。比如有 N / M 为 34，两个节点，则第一个节点写入 21 组，第二个节点写入 13 组。 然后按照同样的逻辑不断归并，最后就可以得到一个有序数组。 整体算法复杂度为 O(Log_k{N/M})，k 为节点数。 |
 |
10
vansl 2018-11-18 13:17:01 +08:00 via iPhone
堆
|
 |
11
vegito2002 2018-11-18 13:37:51 +08:00
k-merge. map reduce 和 sstable 的实现里面我记得都有用到这个原理
|
 |
12
binux 2018-11-18 13:40:06 +08:00 via Android
啊，归并排序为什么要遍历 n ？即使是两路归并你还不是要记录现在的左右值，难道去遍历吗？和所谓的 k-way merge 有什么区别？
多路也一样啊，即使不建堆，比起节点读取速度，插入排序也没什么嘛。我还以为面试官要求 n 的读取呢 |
Select Language