Python 快速排序运行错误：递归深度超过了 cmp 的最大值。

Question

我正在编写一个程序，将会读取一个包含5,163个名字的文本文件（可以在这里看到该文本文件）。

然后我想把这些名字存储到一个名为“names”的列表中，之后，我将根据名字包含的字母数量对列表进行排序，较短的名字位于列表的开头，较长的名字位于列表的末尾。

我使用快速排序算法对列表进行排序，但运行程序时出现了以下错误:

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

完整的回溯信息可以在pastie中获得。

我已经测试了快速排序函数，对于普通列表（例如：list = ['Alice'，'Bob，'Carl'，'Derp']），它可以工作，但是如果我尝试对“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()
#'''

我的代码有什么问题，我该如何修复？

- DarkPotatoKing

---

len(names) 是什么？ - jonrsharpe

@MartijnPieters，是的，我知道len（names）做什么！我的意思是：名字列表有多长？ - jonrsharpe

@jonrsharpe：啊，我明白你的意思了；你想知道要产生那种堆栈跟踪需要多深的兔子洞。 - Martijn Pieters

jonrsharpe是正确的：您可能正试图对过大的列表进行排序。 - Martijn Pieters

设置例如 key=len - 请参见 https://wiki.python.org/moin/HowTo/Sorting#Key_Functions - jonrsharpe

Answer 1

你只是遇到了递归限制问题。你的名字列表太大，超出了Python有限的递归能力。否则，你的Quicksort运行得很好。

你可以通过使用sys.setrecursionlimit()将限制设置得更高来提高递归深度。你可以将其设置得更高一些，但自担风险。

更好的选择是使用内置的Python排序；TimSort算法要优秀得多，不会受到递归限制的影响：

names = sorted(names, key=len)

这将按照名称长度进行排序，最短的名称排在第一位。

- Martijn Pieters

---

sys.setrecursionlimit() 的合理值是多少？ - dhill

@dhill：默认情况下是明智的。如果您需要提高它，请仔细考虑算法，也许可以避免使用递归解决问题？ - Martijn Pieters

Answer 2

您超过了Python默认的递归深度限制。默认的递归深度限制是1000。您可以增加递归深度限制，但这并不推荐。以下是如何做：

import sys
sys.setrecursionlimit(1500)

建议
我的建议是使用numpy.argsort()方法，该方法已经准备好了许多排序算法。这里有一个简单的例子，展示了如何使用numpy库进行快速排序算法。点击此处查看。

- Harun ERGUL