1

Python のプロセスについてもう少し学ぶために、複数のプロセスを使用してクイックソートを実装することにしました。〜21K要素未満のリストでは問題なく動作するようですが、それより大きいもの（たとえば25K要素）ではハングします。

import sys; sys.setrecursionlimit(2**30)私は無駄にトリックを試みました。これは単純に、Python が本当に深い再帰を好まないからですか? 興味深いことに、同じアルゴリズムが 5 万要素までの単一プロセスとして正常に機能します。

import random, multiprocessing, time

DESIRED_PROC_DEPTH = 2
proc_depth = 1 #start at one to count the parent process that kicks this all off

def main():
    import sys; sys.setrecursionlimit(2**30)
    num_elements = 20000
    list_of_numbers = [random.randint(0,num_elements) for num in range(num_elements)]
    # print list_of_numbers
    simple_start = time.time()
    simple_sorted = simple_qs(list_of_numbers)
    simple_total_time = time.time() - simple_start
    print "Using a single thread we sorted " + str(num_elements) + " elements in " + str(simple_total_time) + " seconds"
    the_q = multiprocessing.Queue()
    sorter = MTQuickSort(list_of_numbers, the_q)
    start = time.time()
    sorter.start()
    sorter.join()
    mt_total_time = time.time() - start
    sorted_list = the_q.get()
    # print sorted_list
    print "Sorted " + str(num_elements) + " elements in " + str(mt_total_time) + " seconds"


class MTQuickSort(multiprocessing.Process):

    def __init__(self, list_to_sort, queue):
        super(MTQuickSort, self).__init__()
        print self.name
        self.queue = queue
        self.list = list_to_sort

    def run(self):
        self.queue.put(self.quicksort(self.list))

    def quicksort(self, list):
        global proc_depth
        global DESIRED_PROC_DEPTH
        if len(list) is 0:
            # base case is that list is empty
            return []
        else:
            pivot = list[0]
            less = [x for x in list[1:] if x <= pivot]
            greater = [x for x in list[1:] if x > pivot]
            if proc_depth < DESIRED_PROC_DEPTH:
                proc_depth += 1
                # We create threads in blocks of two since we partition the list into two parts
                lessor_q = multiprocessing.Queue()
                greater_q = multiprocessing.Queue()
                qs_process1 = MTQuickSort(less, lessor_q)
                qs_process2 = MTQuickSort(greater, greater_q)
                qs_process1.start()
                qs_process2.start()
                qs_process1.join()
                qs_process2.join()
                return lessor_q.get() + [pivot] + greater_q.get()
            else:
                less_than_pivot = self.quicksort(less)
                greater_than_pivot = self.quicksort(greater)
                return less_than_pivot + [pivot] + greater_than_pivot

def simple_qs(list):
    if len(list) is 0:
        # base case is that list is empty
        return []
    else:
        pivot = list[0]
        return simple_qs([x for x in list[1:] if x <= pivot]) + [pivot] + simple_qs([x for x in list[1:] if x > pivot])



if __name__ == '__main__':
    main()
4

1 に答える 1

3

これは、キューから結果を get() する前にサブプロセスを join() することが原因です。どうやら、キューはサブプロセスから積極的にデータを読み取っていません。したがって、join() を呼び出すと、呼び出し元のプロセスはサブプロセスが終了するまで待機しますが、サブプロセス自体は、親プロセスへのパイプにデータを送信しようとして待機しています。

対応する get() の後にさまざまな join() を移動すると、機能します。

于 2012-09-17T09:32:37.790 に答える