问题描述
(Python 2.7.8 Windows)
(Python 2.7.8 Windows)
我正在比较不同的排序算法(快速，冒泡和插入)，并且大多数情况都按预期进行，使用长列表时，快速排序要快得多；使用短列表和经过排序的排序时，气泡和插入要快得多
I'm doing a comparison between different sorting algorithms (Quick, bubble and insertion), and mostly it's going as expected, Quick sort is considerably faster with long lists and bubble and insertion are faster with very short lists and alredy sorted ones.
引起问题的是快速排序以及前面提到的已排序"列表.我什至可以排序100000个项目的列表，而不会出现问题，但是使用0 ... n的整数列表时，限制似乎要低得多. 0 ... 500可以工作，但即使0 ... 1000也可以:
What's raising a problem is Quick Sort and the before mentioned "already sorted" lists. I can sort lists of even 100000 items without problems with this, but with lists of integers from 0...n the limit seems to be considerably lower. 0...500 works but even 0...1000 gives:
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
代码是否有问题，或者我缺少什么?
Is there something wrong with the code, or am I missing something?
推荐答案
发生了两件事.
首先，Python故意将递归限制为固定深度.不像Scheme这样，它会一直为递归调用分配帧，直到内存用完为止，而Python(至少是最流行的实现，CPython)只会分配 sys.getrecursionlimit() 帧(默认为1000)，然后再失败.这是有原因的，*但实际上，这与这里无关.事实就是您需要知道的.
First, Python intentionally limits recursion to a fixed depth. Unlike, say, Scheme, which will keep allocating frames for recursive calls until you run out of memory, Python (at least the most popular implementation, CPython) will only allocate sys.getrecursionlimit() frames (defaulting to 1000) before failing. There are reasons for that,* but really, that isn't relevant here; just the fact that it does this is what you need to know about.
第二，您可能已经知道，虽然QuickSort是O(N log N)且包含最多列表，但它的情况最糟的是O(N^2)-特别是(使用标准数据透视规则)具有-排序列表.发生这种情况时，您的堆栈深度最终可能为O(N).因此，如果您有1000个元素(以最坏情况的顺序排列)，并且已经是堆栈中的一帧，那么您将溢出.
Second, as you may already know, while QuickSort is O(N log N) with most lists, it has a worst case of O(N^2)—in particular (using the standard pivot rules) with already-sorted lists. And when this happens, your stack depth can end up being O(N). So, if you have 1000 elements, arranged in worst-case order, and you're already one frame into the stack, you're going to overflow.
您可以通过以下几种方法解决此问题:
You can work around this in a few ways:
- 使用显式堆栈将代码重写为迭代式的，因此您仅受堆内存的限制，而不受堆栈深度的限制.
- 确保始终先递归到较短的一侧，而不是左侧.这意味着即使在
O(N^2)情况下，您的堆栈深度仍为O(log N).但前提是您已经完成了上一步.** - 使用随机，三位数中位数或其他枢轴规则，使常见情况不像已经排序的最坏情况. (当然，仍然有人可以有意地对您的代码进行DoS；使用quicksort确实无法避免这种情况.) Wikipedia文章对此进行了一些讨论，并链接到经典的Sedgewick和Knuth论文.
- 使用具有无限堆栈的Python实现.***
-
sys.setrecursionlimit(max(sys.getrecursionlimit(), len(myList)+CONSTANT)).这样，如果您无法腾出足够的空间，您将立即因为明显的原因而失败，否则通常不会失败. (但是，您可能会-您可能已经在堆栈深900步之内开始排序了……)但这不是一个好主意.此外，您必须找出正确的CONSTANT，这通常是不可能的.*****
- Rewrite the code to be iterative, with an explicit stack, so you're only limited by heap memory instead of stack depth.
- Make sure to always recurse into the shorter side first, rather than the left side. This means that even in the
O(N^2)case, your stack depth is stillO(log N). But only if you've already done the previous step.** - Use a random, median-of-three, or other pivot rule that makes common cases not like already-sorted worst-case. (Of course someone can still intentionally DoS your code; there's really no way to avoid that with quicksort.) The Wikipedia article has some discussion on this, and links to the classic Sedgewick and Knuth papers.
- Use a Python implementation with an unlimited stack.***
sys.setrecursionlimit(max(sys.getrecursionlimit(), len(myList)+CONSTANT)). This way, you'll fail right off the bat for an obvious reason if you can't make enough space, and usually won't fail otherwise. (But you might—you could be starting the sort already 900 steps deep in the stack…) But this is a bad idea.****. Besides, you have to figure out the rightCONSTANT, which is impossible in general.*****
这篇关于Python QuickSort最大递归深度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！