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

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

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

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

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

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

于 2010-04-26T04:36:14.823 回答
1

为什么要编写自己的快速排序例程？这是作业吗？

如果没有，我建议使用内置的排序机制；它们对于绝大多数情况都非常好，并且不会遇到递归深度问题。如果您正在查看非常大的数据集，我建议您查看 scipy 和 numpy 提供的各种容器和算法。

如果纯粹是为了实现例程的好奇心，正如 Marcelo 在评论中建议的那样，我们将需要查看代码。

于 2010-04-26T03:56:43.247 回答
1

  • 您正在使用快速排序的递归实现。您想改为使用迭代来实现快速排序。

    递归在 Python 中不可扩展（至少在 CPython 中），因此对于较大的输入，它将失败。您可以增加递归限制，但这只会让您在更大的范围内扩展，而不是让您的实现真正扩展。如果递归过多，它也会以允许出现段错误为代价。这种方法对多线程代码也有效（或者说实际上并不有效），您只需要做更多，因为每个线程的递归限制会更低。总而言之，这是一个失败的提议：改用迭代。

  • 您正在使用线程（或计划使用），这通常是一个不好的迹象。线程令人困惑、危险和困难。更重要的是，Python 中的线程不会为您提供并行执行，如果这是您所期望的。使用线程来实现快速排序，尤其是在 Python 中，可能证明不太理想。（如果你被要求这样做，你至少应该退后一步，明白这可能不是最好的方法。）

于 2010-04-26T04:48:15.793 回答
0

您遇到的问题是递归函数使用内存，并且由于大量元素以及大量递归，您的内存不足。这就解释了为什么提高递归限制会使你的程序崩溃——你要求的内存比你拥有的更多。

如果您真的想为大量元素实现快速排序，您将需要阅读Wikipedia 上的这篇文章，了解专门使用快速排序的内存使用情况。否则，正如 Nathan 建议的那样，Python 已经有一个内置sorted()函数。除非这是家庭作业或好奇心，否则我强烈建议使用它。

于 2010-04-26T04:02:22.610 回答
0

这是快速排序的迭代代码

    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 回答