python 多线程 "maximum recursion depth exceed"

Question

我用Python多线程实现Quicksort。快速排序是在函数中实现的。它是一个递归函数。每个线程调用 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)

Answer 1

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

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

每个线程都需要自己的堆栈来存储当前在该线程中执行的函数列表。在单线程程序中，系统可以为该线程提供一大块内存给堆栈。在多线程程序中，系统必须更保守一点，它只给每个线程一个小堆栈。否则，具有许多线程的程序可能会很快用完所有系统内存，仅堆栈空间(其中大部分不会被使用)。

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

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