Python Quicksort 运行时错误:在 cmp 中超出了最大递归深度 [英] Python Quicksort Runtime Error: Maximum Recursion Depth Exceeded in cmp

问题描述

我正在编写一个程序，它将读取一个包含 5,163 个名字的文本文件.(可以在此处查看文本文件)

I'm writing a program that will read a text file containing 5,163 names. (text file can be seen here)

然后我想将名称存储到一个名为names"的列表中，之后，我根据名称包含的字母数对列表进行排序，较短的名称在列表的开头，较长的在结尾.

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.

我使用quicksort对列表进行排序，但是当我运行它时，它显示了这个错误:

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

完整的回溯可作为馅饼.

我已经测试了快速排序功能，它适用于普通列表(例如:list = ['Alice','Bob,'Carl','Derp'])，但是如果我尝试排序它不起作用'名字'

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'

这是我的代码

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?

推荐答案

您只是达到了递归限制.您的名称列表对于 Python 有限的递归功能来说太大了.否则，您的 Quicksort 工作正常.

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.

您可以通过使用设置更高的限制来提高递归限制sys.setrecursionlimit().您可以将其设置得更高一些，但风险自负.

You could raise 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.

更好的选择是使用内置的 Python 排序；TimSort 算法要好得多，而且不会达到递归限制:

A better option is to use the built-in Python sort; the TimSort algorithm is far superior and won't hit a recursion limit:

names = sorted(names, key=len)

这会按名称的长度对名称进行排序，最短的名称在前.

This sorts the names by their length, shortest names first.

这篇关于Python Quicksort 运行时错误:在 cmp 中超出了最大递归深度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！