Python Multithread「最大再帰深さを超える」
https://stackoverflow.com/questions/2711036
-
01-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
Python MultiThreadを使用してクイックソートを実現します。 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)
解決
あなたの本当の質問は、「スレッドを使用するときに再帰深さが短いのはなぜですか」ということです。私はその質問に答えようとします。
まず、背景。再帰の各レベルには、スタックとして知られるメモリの領域が保存されます。残念ながら、システムはスタックスペースを事前に割り当てる必要があり、プログラムが必要なスタックスペースの量を事前に知りません。そのため、再帰が多すぎると「最大再帰深度」エラーが発生します。プログラムはそのスタックスペースをすべて使い果たしました。
各スレッドには、現在そのスレッドで実行されている関数のリストを保存するために、独自のスタックが必要です。単一のスレッドプログラムでは、システムはその1つのスレッドのスタックに大きなメモリの塊を与える余裕があります。マルチスレッドプログラムでは、システムはもう少し保守的でなければならず、各スレッドに小さなスタックのみを提供します。それ以外の場合、多くのスレッドを備えたプログラムは、スタックスペースだけですべてのシステムメモリをすばやく使用できます（そのほとんどは使用されません）。
これらはすべて、オペレーティングシステムおよび/またはCライブラリによって行われます。これは、Python（より正確には、Cpython）が上に実行されます。 Pythonは、Cスタック全体を使用しないようにしようとします。これは、単なる例外ではなく、ハードクラッシュを引き起こすためです。 Pythonにどのように振る舞うかを伝えることができます setrecursionlimit 機能ですが、それは変わりません 実際 利用可能なスタックスペースの量。
バッシュシェルを備えたUnix-っぽいシステムでは、スタックサイズをで変更できる場合があります。 ulimit -s 指図。タイプ help ulimit バッシュシェルで詳細を求めてください。
他のヒント
クイックソートの再帰実装を使用しています。 代わりに、イテレーションを使用してQuickSortを実装します。
再帰は、Pythonではスケーラブルではありません（少なくともCpythonで）ため、より大きな入力では失敗します。再帰制限を増やすことができますが、これにより、実装を本当に拡張するのではなく、より広い範囲にわたってスケーリングできます。また、再帰が多すぎる場合、SegFaultの可能性を許可する犠牲を払っています。このアプローチは、マルチスレッドコードでも機能します（または実際には機能しません）。各スレッドの再帰制限が低くなるため、さらに実行する必要があります。全体として、それは負けた提案です：代わりに反復を使用します。
スレッド（または計画）を使用していますが、これは通常悪い兆候です。スレッドは混乱し、危険で硬いです。さらに、Pythonのスレッドは、それがあなたが期待していたものであれば、並行した実行を与えません。特にPythonでのクイックソート実装にスレッドを使用すると、おそらく理想よりも少ないことが証明されます。 （あなたがそれをする必要がある場合、あなたは少なくとも一歩下がって、それが最良のアプローチではないかもしれないことを理解する必要があります。）
なぜあなたはあなた自身のクイックソートルーチンを書いているのですか？この宿題ですか？
そうでない場合は、組み込みのソートメカニズムを使用することをお勧めします。それらは大多数のケースにとって非常に良いことであり、再帰深度の問題に悩まされていません。非常に大きなデータセットを見ている場合は、ScipyとNumpyから利用可能なさまざまなコンテナとアルゴリズムを見ることをお勧めします。
マルセロがコメントで示唆しているように、ルーチンを実装するという好奇心の純粋な場合は、コードを見る必要があります。
あなたが抱えている問題は、再帰関数がメモリを使用し、多数の要素、したがって多数の再帰があることで、メモリが不足しています。これは、再帰制限を上げるとプログラムがクラッシュする理由を説明しています。あなたが持っているよりも多くの記憶を求めています。
たくさんの要素にQuickSortを実際に実装したい場合は、読みたいと思うでしょう これ QuickSortを使用したメモリ使用に関するウィキペディアに関する記事。そうでなければ、ネイサンが示唆したように、Pythonはすでに組み込まれています sorted() 働き。これが宿題や好奇心でない限り、私はそれを使用することを強くお勧めします。
これが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"
