Python QuickSort最大递归深度

Question

(Python 2.7.8 Windows)

我正在对不同的排序算法(快速,气泡和插入)进行比较,并且大多数情况正如预期的那样,快速排序相当快,长列表和气泡和插入更快,非常短的列表和alredy排序的.

引发问题的是Quick Sort和之前提到的"已排序"列表.我可以排序甚至100000个项目的列表没有问题,但是从0 ... n的整数列表,限制似乎相当低.0 ... 500工作,但即使0 ... 1000给出:

RuntimeError: maximum recursion depth exceeded in cmp

快速排序:

def quickSort(myList):
    if myList == []:
        return []
    else:
        pivot = myList[0]
        lesser = quickSort([x for x in myList[1:] if x < pivot])
        greater = quickSort([x for x in myList[1:] if x >= pivot])
        myList = lesser + [pivot] + greater
        return myList

代码有什么问题,或者我错过了什么？

Answer 1

有两件事情在发生.

首先,Python故意将递归限制为固定深度.与Scheme不同,它将继续为递归调用分配帧,直到内存不足为止,Python(至少是最流行的实现,CPython)只会sys.getrecursionlimit()在失败之前分配帧(默认为1000).有理由,*但实际上,这与此无关; 只是这样做的事实是你需要知道的.

其次,正如您可能已经知道的那样,虽然QuickSort O(N log N)具有大多数列表,但它具有最坏的情况O(N^2)- 特别是(使用标准的枢轴规则)已经排序的列表.当发生这种情况时,您的堆栈深度可能会最终结束O(N).所以,如果你有1000个元素,以最坏情况顺序排列,并且你已经进入堆栈的一个帧,那么你将会溢出.

您可以通过以下几种方式解决此问题:

• 使用显式堆栈重写代码以进行迭代,因此您只受堆内存而非堆栈深度的限制.
• 确保始终首先递归到较短的一侧,而不是左侧.这意味着即使在这种O(N^2)情况下,您的堆栈深度仍然是O(log N).但前提是你已经完成了上一步.**
• 使用随机,三次中值或其他枢轴规则,使常见情况不像已排序的最坏情况.(当然有人仍然可以故意使用你的代码;使用quicksort确实无法避免这种情况.)维基百科文章对此有一些讨论,并链接到经典的Sedgewick和Knuth论文.
• 使用具有无限堆栈的Python实现.***
• sys.setrecursionlimit(max(sys.getrecursionlimit(), len(myList)+CONSTANT)).这样,如果你不能留出足够的空间,你就会立即失败,原因显而易见,通常也不会失败.(但是你可能 - 你可能已经开始在堆栈中已经深入900步......)但这是一个坏主意.****.此外,你必须找出正确的CONSTANT,这是不可能的.*****

_{*从历史上看,CPython解释器以递归方式调用自身进行递归Python函数调用.并且C堆栈的大小是固定的; 如果你超支结束,你可能会发生段错误,踩堆内存,或者各种其他问题.这可以改变 - 事实上,Stackless Python开始时基本上只是CPython这个改变.但核心开发人员故意选择不这样做,部分原因是他们不想鼓励人们编写深度递归代码.}

_{**或者,如果您的语言执行自动尾部调用消除,但Python不会这样做.但是,正如gnibbler指出的那样,你可以在小端编写一个混合解决方案 - recurse,然后在大端上手动解包尾递归 - 这不需要显式堆栈.}

_{***Stackless和PyPy都可以这样配置.}

_{****首先,你最终会崩溃C堆栈.}

_{*****常数不是真正的常数; 它取决于你已经在堆栈中的深度(通过走到sys._getframe()顶部可计算不可移动)以及比较函数需要多少松弛等等(根本不可计算,你只需要猜测).}