Multi-Threaded Merge Sortieren

Question

Wie wird dies implementiert in Ruby? Insbesondere, wie werden die Ergebnisse der erzeugten Threads zum Hauptthread zurückgegeben?

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 

Answer 1

Dies ist meine Implementierung von parallel merge sort in Ruby. Getestet in 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 

Da es als Ruby-Modul implementiert ist, können Sie es in Array-Klasse umfassen:

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] 

Zurück zu Ihrer Frage. Schauen Sie sich die Zeile mit den Threads genauer an. Ich erstelle zwei neue Threads innerhalb neue Array, tun Berechnung in ihnen dann I #join() Threads zusammen und retrive #value() von ihnen. Da es in Array immer zwei Threads gibt, kann ich die Ergebnisse dann in die Variablen part_a und part_b entpacken.