多线程合并排序

这是怎么得到在Ruby中实现？特别是，产生的线程的结果如何返回到主线程？多线程合并排序

def merge_sort(array) 
    return array if base_case?(array) 

    first_half, second_half = split_into_halves(array) 

    # spawn recursive calls 
    first_spawn = Thread.new { 
    sorted_first_half = merge_sort(first_half) 
    } 

    second_spawn = Thread.new { 
    sorted_second_half = merge_sort(second_half) 
    } 

    # sync 
    first_spawn.join 
    second_spawn.join 

    merge(sorted_first_half, sorted_second_half) 
end

来源

2016-04-15 Trajanson

我不知道Ruby，但它似乎最后的语句应该是返回合并（...），或数组=合并（...），然后返回数组。我还假设base_case表示数组大小<2。 – rcgldr

是的，base_case表示array.size <2.我的想法是#join是Ruby尝试合并线程。 Ruby代码的最后一行是自动返回的，@rcgldr – Trajanson

最后的语法看起来很奇怪。没有为merge（...）指定返回数组，为什么它应该返回数组中的结果？ merge_sort函数只是返回，不像函数明确返回数组的开始位置。 – rcgldr

这是我在Ruby中并行执行的merge sort。在Ruby 2.3.x中测试过。

module ParallelMergeSort 

    def merge_sorted 
    return self if size <= 1 

    split = size/2 

    # Divide into sub-threads 
    part_a, part_b = [ 
     Thread.new { self.slice(0, split).merge_sorted }, 
     Thread.new { self.slice(split, self.size - split).merge_sorted } 
    ].map(&:join).map(&:value) 

    # Conquer and return 
    array = self.class.new 
    off_a, off_b = [0, 0] 

    while off_a < part_a.size && off_b < part_b.size 
     a, b = part_a[off_a], part_b[off_b] 

     if a <= b 
     array << a 
     off_a += 1 
     else 
     array << b 
     off_b += 1 
     end 
    end 

    while off_a < part_a.size 
     array << part_a[off_a] 
     off_a += 1 
    end 

    while off_b < part_b.size 
     array << part_b[off_b] 
     off_b += 1 
    end 

    array 
    end 
end

因为它是为Ruby的模块来实现，可以将其包括对Array类：

Array.send(:include, ParallelMergeSort) 


[1, 2, 5, 6, 8, 10, 33, 4, 33, 44, 1, 100, 87].merge_sorted #=> [1, 1, 2, 4, 5, 6, 8, 10, 33, 33, 44, 87, 100]

回到你的问题。如果仔细看线提线。我在里面新建了两个新的Threads，在里面做计算，然后我把它们从#value()里面串起来。由于Array中总是有两个线程，因此我可以将结果解压缩到变量part_a和part_b。

来源

2016-04-21 08:21:14

请记住，这不是最终的解决方案。在现实世界中，您无法创建无限的新[线程]（http://ruby-doc.org/core-2.3.0/Thread.html）。在现实世界中，您必须向您的解决方案中引入诸如[Queue]（http://ruby-doc.org/core-2.3.0/Queue.html）之类的内容，并可能需要等待某些线程在创建新线程之前完成执行。还有[Ruby的GIL限制]（https://en.wikipedia.org/wiki/Global_interpreter_lock），你最终可能会遇到 - 但这完全是另一章。 :) –

多线程合并排序

回答

相关问题