Максимальная глубина рекурсии Python QuickSort

(Python 2.7.8 Windows)

Я делаю сравнение между различными алгоритмами сортировки (Quick, bubble и insertion), и в основном это происходит так, как ожидалось. Быстрая сортировка значительно быстрее с длинными списками и пузырьками, а вставка быстрее с очень короткими списками и отсортированными по alredy.

Что вызывает проблемы, это Quick Sort и ранее упомянутые «уже отсортированные» списки. Я могу сортировать списки из 100000 элементов без проблем с этим, но со списками целых чисел от 0 … n предел, по-видимому, значительно ниже. 0 … 500 работает, но даже 0 … 1000 дает:

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 

Что-то не так с кодом, или я чего-то не хватает?

3 Solutions collect form web for “Максимальная глубина рекурсии Python QuickSort”

Происходит две вещи.

Во-первых, Python преднамеренно ограничивает рекурсию на фиксированную глубину. В отличие, скажем, Scheme, которая будет продолжать выделять кадры для рекурсивных вызовов до тех пор, пока не закончится sys.getrecursionlimit() памяти, Python (по крайней мере, самая популярная реализация, CPython) будет выделять только sys.getrecursionlimit() (по умолчанию до 1000) до сбоя. Есть причины для этого *, но на самом деле это не имеет значения здесь; просто то, что он делает, это то, о чем вам нужно знать.

Во-вторых, как вы уже знаете, в то время как QuickSort является O(N log N) с большинством списков, он имеет наихудший случай O(N^2) – в частности (с использованием стандартных правил поворота) с уже отсортированными списками. И когда это произойдет, ваша глубина стека может оказаться O(N) . Итак, если у вас есть 1000 элементов, упорядоченных в худшем порядке, и вы уже один кадр в стек, вы собираетесь переполняться.

Вы можете обойти это несколькими способами:

  • Перепишите код, чтобы быть итеративным, с явным стекем, так что вы ограничены только памятью кучи вместо глубины стека.
  • Удостоверьтесь, что всегда рекурсивно заходите в более короткую сторону, а не в левую сторону. Это означает, что даже в случае O(N^2) ваша глубина стека по-прежнему равна O(log N) . Но только если вы уже сделали предыдущий шаг. **
  • Используйте случайное, медианное из трех или другое правило поворота, которое делает обычные случаи не похожими на уже отсортированный наихудший случай. (Конечно, кто-то может все еще преднамеренно делать свой код, и не существует способа избежать этого с помощью быстрой сортировки.) В статье в Википедии есть несколько обсуждений этого вопроса и ссылки на классические документы Седжуика и Кнута.
  • Используйте реализацию Python с неограниченным стеком. ***
  • sys.setrecursionlimit(max(sys.getrecursionlimit(), len(myList)+CONSTANT)) . Таким образом, вы потерпите неудачу с места в карьер по очевидной причине, если вы не можете сделать достаточно места и обычно не потерпите неудачу в противном случае. (Но вы могли бы – вы могли бы начать сортировку уже 900 шагов в глубину стека …) Но это плохая идея. ****. Кроме того, вам нужно выяснить правильную CONSTANT , что вообще невозможно. *****

* Исторически интерпретатор CPython рекурсивно вызывает себя для рекурсивных вызовов функций Python. И стек C фиксирован по размеру; если вы переполнили конец, вы могли бы segfault, топать по всей куче памяти или всевозможные другие проблемы. Это можно было бы изменить – фактически, Stackless Python начинался как в основном только CPython с этим изменением. Но основные разработчики намеренно решили не делать этого, отчасти потому, что они не хотят побуждать людей писать глубоко рекурсивный код.

** Или если ваш язык выполняет автоматическое устранение хвостового вызова, но Python этого не делает. Но, как указывает гниблер, вы можете написать гибридную рекурсию на маленьком конце, а затем вручную развернуть хвостовую рекурсию на большом конце, что не потребует явного стека.

*** Stackless и PyPy могут быть настроены таким образом.

**** С одной стороны, в конечном итоге вы столкнетесь с C-стеком.

***** Константа на самом деле не постоянна; это зависит от того, насколько глубоко вы уже находитесь в стеке (вычислимо не-переносимо, пешая sys._getframe() до вершины) и сколько вам нужно для функций сравнения и т. д. (не вычислимо вообще, вам просто нужно Угадай).

Вы выбираете первый элемент каждого подсписчика в качестве точки опоры. Если список уже в порядке, это означает, что ваш лучший подсписок – это все предметы, кроме первого, а не примерно половина из них. По сути, каждый рекурсивный вызов обрабатывает только один элемент. Это означает, что глубина рекурсивных вызовов, которые вам нужно будет сделать, будет примерно такой же, как количество элементов в полном списке. Что переполняет встроенный лимит Python, когда вы нажмете около 1000 элементов. У вас будут похожие списки сортировки проблем, которые уже находятся в обратном порядке.

Чтобы исправить это, используйте один из обходных путей, предложенных в литературе, например, выбор случайного элемента, который должен быть стержнем или средой первого, среднего и последнего предметов.

Всегда выбирая первый (или последний) элемент, поскольку стержень будет иметь проблемы для быстрой сортировки – наихудшая производительность для некоторых общих входов, как вы видели

Один метод, который работает достаточно хорошо, – это выбрать среднее значение первого, среднего и последнего элементов

Вы не хотите, чтобы выбор шага был слишком сложным, или он будет доминировать во время выполнения поиска

  • python: как отсортировать сложный список на двух разных ключах
  • Сортировка файлов в Python
  • Самый быстрый способ сортировки в Python
  • Ранжирование массива numpy с возможными дубликатами
  • Естественно отсортируйте список альфа-числовых кортежей с помощью первого элемента кортежа в Python
  • Список сортировки данных Python по алфавиту
  • Куча Сортировка: как сортировать?
  • Как заменить номера с порядком в списке (python)
  • Python - лучший язык программирования в мире.