Python Quicksort 运行时错误：在 cmp 中超出了最大递归深度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/25105541/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Python Quicksort Runtime Error: Maximum Recursion Depth Exceeded in cmp
提问by DarkPotatoKing
I'm writing a program that will read a text file containing 5,163 names. (text file can be seen here)
我正在编写一个程序，它将读取一个包含 5,163 个名字的文本文件。（文本文件可以在这里看到）
Then I want to store the names into a list called 'names', afterwards, I sort the list based on how many letters the name contains, shorter names are at the start of the list and the longer ones are at the end.
然后我想将名称存储到一个名为“名称”的列表中，之后，我根据名称包含的字母数对列表进行排序，较短的名称在列表的开头，较长的在结尾。
I used quicksort to sort the list, but when I run it, it shows this error:
我使用快速排序对列表进行排序，但是当我运行它时，它显示了这个错误：
C:\Python27\python.exe C:/Users/Lenovo/Desktop/Anagrams/Main.py
Traceback (most recent call last):
File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 25, in <module>
names = quicksort(names)
File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 8, in quicksort
greater = quicksort([x for x in list[1:] if not lessThan(x, pivot)])
File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 7, in quicksort
lesser = quicksort([x for x in list[1:] if lessThan(x, pivot)])
File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 8, in quicksort
greater = quicksort([x for x in list[1:] if not lessThan(x, pivot)])
File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 7, in quicksort
lesser = quicksort([x for x in list[1:] if lessThan(x, pivot)])
# [.... many lines elided ...]
File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 8, in quicksort
greater = quicksort([x for x in list[1:] if not lessThan(x, pivot)])
File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 8, in quicksort
greater = quicksort([x for x in list[1:] if not lessThan(x, pivot)])
File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 7, in quicksort
lesser = quicksort([x for x in list[1:] if lessThan(x, pivot)])
File "C:/Users/Lenovo/Desktop/Anagrams/Main.py", line 3, in quicksort
if list == []:
RuntimeError: maximum recursion depth exceeded in cmp
The full traceback is available as a pastie.
完整的回溯可作为馅饼使用。
I've tested the quicksort function and it works for ordinary lists (ex: list = ['Alice','Bob,'Carl','Derp']), but it doesn't work if I try to sort 'names'
我已经测试了快速排序功能，它适用于普通列表（例如：list = ['Alice','Bob,'Carl','Derp']），但如果我尝试对“姓名”进行排序则不起作用
Here's my code
这是我的代码
def quicksort(list):
"""Quicksort using list comprehensions"""
if list == []:
return []
else:
pivot = list[0]
lesser = quicksort([x for x in list[1:] if lessThan(x, pivot)])
greater = quicksort([x for x in list[1:] if not lessThan(x, pivot)])
return lesser + [pivot] + greater
def lessThan(a, b):
return len(a) < len(b)
#'''
input = open('Names.txt', 'r')
output = open('Names Arranged By Length.txt', 'w')
names = []
for line in input:
line = line.translate(None, '\n')
names.append(line)
names = quicksort(names)
for i in names:
print i
output.write(i)
output.write('\n')
print 'Count: ', len(names)
input.close()
output.close()
#'''
What's wrong with my code and how do I fix it?
我的代码有什么问题，我该如何解决？
采纳答案by Martijn Pieters
You have simply hit the recursion limits. Your list of names is too large for Python's limited recursion capabilities. Your Quicksort works just fine otherwise.
您只是达到了递归限制。您的名称列表对于 Python 有限的递归功能来说太大了。否则，您的 Quicksort 工作正常。
You couldraise the recursion limit by setting the limit higher with sys.setrecursionlimit(). You can set it a fair amount higher, but you do so at your own risk.
您可以通过使用 将限制设置得更高来提高递归限制sys.setrecursionlimit()。您可以将其设置得更高一些，但风险自负。
A better option is to use the built-in Python sort; the TimSort algorithmis far superior and won't hit a recursion limit:
更好的选择是使用内置的 Python 排序；该TimSort算法远远优于并不会打一个递归限制：
names = sorted(names, key=len)
This sorts the names by their length, shortest names first.
这会按名称的长度对名称进行排序，最短的名称在前。
回答by Harun ERGUL
You exceed python default recursion size. The default recursion limit is 1000. You can increase recursion limit but it is not recommended. Here is how to do
您超过了 python 默认递归大小。默认递归限制为 1000。您可以增加递归限制，但不建议这样做。这是怎么做的
import sys
sys.setrecursionlimit(1500)
Suggestion
My suggestion is use numpy.argsort()method which is already prepared for many sorting algorithms. Here is simple examle for how to do quicksort algorith by using numpy library.
建议
我的建议是使用numpy.argsort()方法，该方法已经为许多排序算法准备好了。这是如何使用 numpy 库进行快速排序算法的简单示例。
