Подтвердить что ты не робот

Ошибка выполнения Quicksort Python: максимальная глубина рекурсии превышена в cmp

Я пишу программу, которая будет читать текстовый файл, содержащий 5,163 имени. (текстовый файл можно увидеть здесь)

Затем я хочу сохранить имена в списке с именем "имена", после чего сортирую список, исходя из того, сколько букв содержит имя, более короткие имена находятся в начале списка, а более длинные - в конце.

Я использовал quicksort для сортировки списка, но когда я его запускаю, он показывает эту ошибку:

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

Полная трассировка доступна как пастель.

Я тестировал функцию quicksort, и она работает для обычных списков (например: list = ['Alice', 'Bob,' Carl ',' Derp ']), но это не работает, если я пытаюсь сортировать 'имена'

Здесь мой код

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()
#'''

Что не так с моим кодом и как его исправить?

4b9b3361

Ответ 1

Вы просто попали в пределы рекурсии. Список имен слишком велик для возможностей ограниченной рекурсии Python. Ваш QuickSort работает просто отлично.

Вы можете повысить предел рекурсии, установив лимит выше sys.setrecursionlimit(). Вы можете установить его на сумму выше, но вы делаете это на свой страх и риск.

Лучшим вариантом является использование встроенной сортировки Python; алгоритм TimSort намного превосходит и не будет превышать предел рекурсии:

names = sorted(names, key=len)

Сначала сортирует имена по их длине, кратчайшим именам.

Ответ 2

Вы превышаете размер рекурсии по умолчанию python. Предел рекурсии по умолчанию - 1000. Вы можете увеличить предел рекурсии, но это не рекомендуется. Вот как это сделать

import sys
sys.setrecursionlimit(1500)

Предложение
Мое предложение - использовать метод numpy.argsort(), который уже подготовлен для многих алгоритмов сортировки. Вот простой пример о том, как выполнить quicksort-алгоритм с помощью библиотеки numpy.