5

クイックソートを実現するために Python マルチスレッドを使用しています。クイックソートは関数に実装されています。再帰関数です。各スレッドは、Quicksort を呼び出して配列を並べ替えます。各スレッドには、並べ替える必要がある数値を格納する独自の配列があります。配列サイズが小さい場合 (<10,000)。正常に動作します。ただし、配列サイズが大きい場合は、「最大再帰深度超過」を示します。そこで、setrecursionlimit () 関数を使用して再帰の深さを 1500 にリセットします。しかし、プログラムはすぐにクラッシュします... 以下はクイックソート コードです。マルチスレッド環境でなければ問題なく動作します。複数のスレッドが再帰の深さの問題の原因であるようです。

def partition (array, p, r):
    x = array[r]
    i = (p-1)
    j = p
    while (1):
        if array[j] <= x:
            i = (i+1)
            temp = array[j]
            array[j] = array[i]
            array[i] = temp
        j+=1
        if j == r:
            break
    temp = array[i+1]
    array[i+1] = array[r]
    array[r] = temp
    return i+1

def quicksort (array, p, r):
    if p < r:
        q = partition (array, p, r)
        quicksort (array, p, q-1)
        quicksort (array, q+1, r)
4

5 に答える 5

8

あなたの本当の質問は、「スレッドを使用すると再帰の深さが短くなるのはなぜですか」のように聞こえますか? 私はその質問に答えようとします。

まずは背景。再帰の各レベルは、スタックと呼ばれるメモリ領域に格納されます。残念ながら、システムは事前にスタック スペースを割り当てる必要があり、プログラムが必要とするスタック スペースを事前に知ることはできません。そのため、再帰が多すぎると「最大再帰深度」エラーが発生します。プログラムはそのスタック領域をすべて使い果たしました。

各スレッドには、そのスレッドで現在実行中の関数のリストを格納するための独自のスタックが必要です。シングル スレッド プログラムでは、システムはその 1 つのスレッドのスタックに大量のメモリを割り当てることができます。マルチスレッド プログラムでは、システムをもう少し保守的にする必要があり、各スレッドに小さなスタックしか与えません。そうしないと、多くのスレッドを持つプログラムが、スタック スペースだけですべてのシステム メモリをすぐに使い果たしてしまう可能性があります (そのほとんどは使用されません)。

これらはすべて、オペレーティング システムおよび/または Python (より正確には CPython) がその上で実行される C ライブラリによって行われます。Python は、C スタック全体を使用しないように懸命に試みます。これは、単に例外ではなくハード クラッシュを引き起こすためです。関数でどのように動作するかを Python に指示できますが、使用可能なスタック スペースの実際の量はsetrecursionlimit変わりません。

bash シェルを使用する UNIX 系のシステムでは、コマンドでスタック サイズを変更できる場合がありますulimit -s。詳細については、bash シェルプロンプトhelp ulimitで入力してください。

于 2010-04-26T04:36:14.823 に答える
1

  • クイックソートの再帰的な実装を使用しています。代わりに反復を使用してクイックソートを実装したいと考えています。

    再帰は Python では (少なくとも CPython では) スケーラブルではないため、より大きな入力に対しては失敗します。再帰の制限を増やすことはできますが、これはより広い範囲でスケーリングすることしかできず、実装を実際にスケーリングすることはできません。また、再帰が多すぎる場合、セグメンテーション違反の可能性を許容するという代償も伴います。このアプローチは、マルチスレッド コードでも機能します (というか、実際には機能しません)。各スレッドの再帰制限が低くなるため、より多くのことを行う必要があります。全体として、それは負けの命題です。代わりに反復を使用してください。

  • スレッドを使用している (または計画している) 場合、これは通常悪い兆候です。スレッドは紛らわしく、危険で、難しいものです。さらに、Python のスレッドは並列実行を提供しません (それが期待されている場合)。特に Python では、クイックソートの実装にスレッドを使用することは、おそらく理想的とは言えません。(それを行う必要がある場合は、少なくとも一歩下がって、それが最善の方法ではない可能性があることを理解する必要があります。)

于 2010-04-26T04:48:15.793 に答える
1

なぜ独自のクイックソート ルーチンを作成しているのですか? これは宿題ですか？

そうでない場合は、組み込みの並べ替えメカニズムを使用することをお勧めします。それらは大多数の場合に非常に優れており、再帰の深さの問題に悩まされることはありません。非常に大きなデータセットを見ている場合は、scipy と numpy から入手できるさまざまなコンテナーとアルゴリズムを調べることをお勧めします。

Marcelo がコメントで示唆しているように、純粋にルーチンの実装に興味がある場合は、コードを確認する必要があります。

于 2010-04-26T03:56:43.247 に答える
0

あなたが抱えている問題は、再帰関数がメモリを使用し、多数の要素と多数の再帰があるため、メモリが不足していることです。これは、再帰制限を上げるとプログラムがクラッシュする理由を説明しています。つまり、持っているよりも多くのメモリを要求しているのです。

多数の要素に対してクイックソートを本当に実装したい場合は、特にクイックソートを使用したメモリ使用量に関するウィキペディアのこの記事を読むことをお勧めします。それ以外の場合、ネイサンが示唆したように、Python には既に組み込みsorted()関数があります。これが宿題や好奇心でない限り、それを使用することを強くお勧めします.

于 2010-04-26T04:02:22.610 に答える
0

QuickSort の反復コードは次のとおりです。

    import time
    import random

    stack = []

    def partition(data,p,q):
        global stack
        pivot = p
        pivotvalue = data[q]
        for index in range(p,q+1):
            if data[index] < pivotvalue:
                temp = data[index]
                data[index] = data[pivot]
                data[pivot] = temp
                pivot = pivot + 1
        temp = data[q]
        data[q] = data[pivot]
        data[pivot] = temp
        return pivot

    def qSort(data,p,q):
        global stack
        push(stack,p,q)
        while isEmpty(stack) == False:
            q = pop(stack)
            p = pop(stack)
            pivot = partition(data,p,q)
            if pivot-1 > p:
                push(stack,p,pivot-1)
            if pivot+1 < q:
                push(stack,pivot+1,q)


    def push(stack,p,q):
        stack.append(p)
        stack.append(q)

    def pop(stack):
        global top
        if(len(stack)==0):
            return -1
        element = stack.pop()
        return element

    def isEmpty(stack):
        return len(stack) == 0

    if __name__ == '__main__':
        start_time = time.time()
        data = (range(1000000,0,-1))
        random.shuffle(data)
        #print data
        qSort(data,0,len(data)-1)
        #print data
        print time.time() - start_time, "seconds"
于 2012-02-14T08:36:29.273 に答える