首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
darouwan
V2EX  ›  算法

昨天面的一道题目,大家一起讨论下

  •  1
     
  •   darouwan · 2018-11-18 10:26:13 +08:00 · 3383 次点击
    这是一个创建于 425 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目是分布式排序 已知有 n 个节点,每个节点有长度为 m 的数组。m<<n

    现在对这 m*n 个数据进行排序。

    我一开始用归并排序,但考官说不行。大家有什么好的解决方案?

    14 回复  |  直到 2018-11-19 17:54:41 +08:00
    AFuture
        1
    AFuture   2018-11-18 10:33:06 +08:00 via iPhone
    先来一波置换选择,再来一波最佳归并。以上仅一个菜鸡本科学生的观点。
    ytmsdy
        2
    ytmsdy   2018-11-18 10:40:09 +08:00
    m<<n
    这个表达的意思是不是 M 远远小于 N
    如果是这样的话,需要先把所有的数都拿出来,然后在做排序。
    简单一点说就是我要对 1w 个数字进行排序,但是每个数组里面只有 2 到 3 个元素,这种情况下,归并排序并不适合。
    ytmsdy
        3
    ytmsdy   2018-11-18 10:40:41 +08:00
    1w 个数字进行排序=====> fix 1w 个数组
    darouwan
        4
    darouwan   2018-11-18 10:41:37 +08:00 via Android
    @ytmsdy 是的,m 远小于 n,所以不能频繁遍历 n
    darouwan
        5
    darouwan   2018-11-18 10:42:28 +08:00 via Android
    @ytmsdy 要求不能一次性吧所有数字取出来,空间不够的。
    ksco
        6
    ksco   2018-11-18 11:11:04 +08:00 via Android   ♥ 4
    在楼主的已知条件之上做一些假设。

    假设每台机器都有一个固定的编号:1, 2, ..., n。
    排序完成后,我们的目标是可以产生一个有序的“流”,因为内存装不下。

    方案如下:
    首先给每个节点的数组排序,这个没啥好说的。
    然后维护一个最小堆,堆的元素是 (节点编号, 当前下标, 具体数值) 这样的一个三元组,当然堆的排序依据是“具体数值”。

    排序的方法是,每次从堆里面弹出一个最小的元素,放入流中,再把这个元素的当前下标步进 1,取该下标的值,生成新的三元组放回堆中,然后循环。


    ===
    最后无耻一下:我做了个公众号“每天一道编程题”,欢迎关注~
    ksco
        7
    ksco   2018-11-18 11:17:47 +08:00
    补充一下,这个方法应该叫 k-way merge

    https://en.wikipedia.org/wiki/K-way_merge_algorithm
    zjxlim
        8
    zjxlim   2018-11-18 11:27:12 +08:00
    @ksco 败者树?
    shidenggui
        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 为节点数。
    vansl
        10
    vansl   2018-11-18 13:17:01 +08:00 via iPhone
    vegito2002
        11
    vegito2002   2018-11-18 13:37:51 +08:00
    k-merge. map reduce 和 sstable 的实现里面我记得都有用到这个原理
    binux
        12
    binux   2018-11-18 13:40:06 +08:00 via Android
    啊,归并排序为什么要遍历 n ?即使是两路归并你还不是要记录现在的左右值,难道去遍历吗?和所谓的 k-way merge 有什么区别?
    多路也一样啊,即使不建堆,比起节点读取速度,插入排序也没什么嘛。我还以为面试官要求 n 的读取呢
    darouwan
        13
    darouwan   2018-11-19 17:43:23 +08:00
    @ksco 有一个地方没看懂, 为什么是"再把这个元素的当前下标步进 1,取该下标的值"?
    比如说 我现在 2 个节点 数据分别是
    1 5 6
    2 3 4
    第一轮 1,2 最小构成堆, 弹出 1, 那下一个岂不是 5?
    darouwan
        14
    darouwan   2018-11-19 17:54:41 +08:00   ♥ 1
    @ksco 哦~看了下懂了 等于说输出最小值之后, 次小值要么在以构建的堆里, 要么在最小值所在的节点里
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2197 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 28ms · UTC 16:08 · PVG 00:08 · LAX 08:08 · JFK 11:08
    ♥ Do have faith in what you're doing.