多線程合併排序

這是怎麼得到在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），你最終可能會遇到 - 但這完全是另一章。 :) –

多線程合併排序

回答

相關問題