python多线程“最大递归深度超过" [英] python multithread "maximum recursion depth exceed"

问题描述

我使用Python多线程来实现Quicksort. Quicksort是一个功能强大的工具.这是一个递归函数. 每个线程都调用Quicksort对其数组进行排序.每个线程都有其自己的数组，用于存储需要排序的数字. 如果阵列尺寸较小(＜10,000).运行正常. 但是，如果数组大小较大，则会显示最大递归深度超过". 因此，我使用setrecursionlimit()函数将递归深度重置为1500.但是程序直接崩溃了... 以下是quicksort代码.如果不在多线程环境中，它将很好地工作. 似乎多线程是递归深度问题的原因.

I use Python multithread to realize Quicksort. Quicksort is implement in a function. It is a recursive function. Each thread calls Quicksort to sort the array it has. Each thread has its own array that stores the numbers needs to be sorted. If the array size is smaller (<10,000). It runs ok. However, if the array size is larger, it shows the "maximum recursion depth exceed". So, I use setrecursionlimit () function to reset the recursion depth to 1500. But the program crash directly... The following is quicksort code. It works well if not in multi-thread environment. It seems multiple threads is the cause of recursion depth problem.

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)

推荐答案

听起来您真正的问题是为什么使用线程时递归深度会更短"?我将尝试回答这个问题.

It sounds like your real question is "Why is the recursion depth shorter when using threads"? I will try to answer that question.

首先，背景.递归的每个级别都存储一个称为堆栈的内存区域.不幸的是，系统必须预先分配堆栈空间，并且它不预先知道程序可能需要多少堆栈空间.这就是为什么过多的递归会导致最大递归深度"错误的原因:您的程序已经用完了所有的堆栈空间.

First, background. Each level of recursion is stored an area of memory known as the stack. Unfortunately, the system has to allocate the stack space in advance and it doesn't know in advance how much stack space your program might need. That's why too much recursion causes a "maximum recursion depth" error: your program has used up all of that stack space.

每个线程都需要自己的堆栈来存储该线程中当前正在执行的功能列表.在单线程程序中，系统可以为该线程提供大量的内存给堆栈.在多线程程序中，系统必须更保守一些，并且每个线程只提供很小的堆栈.否则，具有多个线程的程序可能会很快耗尽所有系统内存，而仅占用堆栈空间(其中绝大部分不会使用).

Each thread needs its own stack to store the list of functions that are currently executing in that thread. In a single threaded program, the system can afford to give a big chunk of memory to the stack for that one thread. In a multi-threaded program, the system has to be a bit more conservative and it gives only a small stack to each thread. Otherwise, a program with many threads could quickly use up all system memory just with stack space (most of which won't be used).

所有这些操作都是由操作系统和/或C库(Python(更确切地说是CPython)在其上运行)完成的. Python尽力阻止您使用整个C堆栈，因为这会导致严重的崩溃，而不仅仅是一个异常.您可以告诉Python如何使用setrecursionlimit函数运行，但这不会更改 actual 可用堆栈空间量.

All of this is done by the operating system and/or by the C library, which Python (more precisely, CPython) runs on top of. Python tries hard to prevent you from using the entire C stack, because that would cause a hard crash rather than simply an exception. You can tell Python how to behave with the setrecursionlimit function, but that doesn't change the actual amount of stack space available.

在带有bash shell的unix-ish系统上，您可以使用ulimit -s命令更改堆栈大小.在您的bash shell提示符下键入help ulimit以获取更多信息.

On a unix-ish system with a bash shell, you may be able to change the stack size with the ulimit -s command. Type help ulimit at your bash shell prompt for more information.

这篇关于python多线程“最大递归深度超过"的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！