Profundidad máxima de recursión de Python QuickSort

(Python 2.7.8 Windows)

Estoy haciendo una comparación entre diferentes algoritmos de clasificación (Rápido, burbuja e inserción), y en su mayoría funciona como se esperaba, la clasificación rápida es considerablemente más rápida con listas largas y la burbuja y la inserción son más rápidas con listas muy cortas y ya clasificadas.

Lo que plantea un problema es la ordenación rápida y las listas “ya ordenadas” antes mencionadas. Puedo ordenar listas de hasta 100000 elementos sin problemas con esto, pero con listas de enteros de 0 … n el límite parece ser considerablemente más bajo. 0 … 500 obras pero incluso 0 … 1000 da:

RuntimeError: maximum recursion depth exceeded in cmp 

Ordenación rápida:

 def quickSort(myList): if myList == []: return [] else: pivot = myList[0] lesser = quickSort([x for x in myList[1:] if x = pivot]) myList = lesser + [pivot] + greater return myList 

¿Hay algún problema con el código o me falta algo?

Hay dos cosas sucediendo.

Primero, Python limita intencionalmente la recursión a una profundidad fija. A diferencia de, por ejemplo, Scheme, que seguirá asignando marcos para llamadas recursivas hasta que se quede sin memoria, Python (al menos la implementación más popular, CPython) solo asignará sys.getrecursionlimit() marcos (por defecto a 1000) antes de fallar. Hay razones para eso, * pero en realidad, eso no es relevante aquí; solo el hecho de que haga esto es lo que necesita saber.

Segundo, como ya sabrá, mientras que QuickSort es O(N log N) con la mayoría de las listas, tiene el peor de los casos de O(N^2) en particular (utilizando las reglas de pivote estándar) con listas ya ordenadas. Y cuando esto sucede, la profundidad de tu stack puede terminar siendo O(N) . Entonces, si tiene 1000 elementos, organizados en el peor de los casos, y ya tiene un marco en la stack, se desbordará.

Puedes solucionar esto de varias maneras:

  • Reescriba el código para que sea iterativo, con una stack explícita, de modo que solo esté limitado por la memoria del montón en lugar de la profundidad de la stack.
  • Asegúrate de recursionar siempre en el lado más corto primero, en lugar del lado izquierdo. Esto significa que incluso en el caso de O(N^2) , la profundidad de su stack sigue siendo O(log N) . Pero solo si ya has hecho el paso anterior. **
  • Use una regla aleatoria, de mediana de tres u otra regla dinámica que haga que los casos comunes no sean como el peor de los casos. (Por supuesto, alguien aún puede hacer su código intencionalmente; realmente no hay forma de evitarlo con Quicksort). El artículo de Wikipedia tiene algo de discusión al respecto y enlaces a los clásicos documentos de Sedgewick y Knuth.
  • Use una implementación de Python con una stack ilimitada. ***
  • sys.setrecursionlimit(max(sys.getrecursionlimit(), len(myList)+CONSTANT)) . De esta manera, fallarás de inmediato por una razón obvia si no puedes hacer suficiente espacio y, por lo general, no fallará. (Pero podrías … podrías estar comenzando el orden ya a 900 pasos de profundidad en la stack …) Pero esta es una mala idea. ****. Además, tienes que encontrar el CONSTANT correcto, que es imposible en general. *****

* Históricamente, el intérprete de CPython se llama a sí mismo recursivamente para las llamadas de función de Python recursivas. Y la stack C es de tamaño fijo; Si se sobrepasa el final, puede segfault, pisar fuerte en toda la memoria del montón, o todo tipo de otros problemas. Esto podría cambiarse, de hecho, Stackless Python comenzó como básicamente solo CPython con este cambio. Pero los desarrolladores centrales han elegido intencionalmente no hacerlo, en parte porque no quieren alentar a las personas a escribir código profundamente recursivo.

** O si su idioma hace la eliminación automática de llamadas de cola, pero Python no lo hace. Pero, como señala gnibbler, puede escribir una solución híbrida (hacer un recuento en el extremo pequeño, luego desenvolver manualmente la recursión de la cola en el extremo grande) que no requerirá una stack explícita.

*** Stackless y PyPy pueden configurarse de esta manera.

**** Por un lado, eventualmente vas a estrellar la stack C.

***** La constante no es realmente constante; depende de la profundidad que ya tenga en la stack (computable de forma no portátil mediante sys._getframe() hasta la parte superior) y de la holgura que necesite para las funciones de comparación, etc. (no computable en absoluto, solo tiene que adivinar).

Estás eligiendo el primer elemento de cada sublista como el pivote. Si la lista ya está en orden, esto significa que su lista greater es todos los elementos, pero el primero, en lugar de alrededor de la mitad. Esencialmente, cada llamada recursiva logra procesar solo un elemento. Lo que significa que la profundidad de las llamadas recursivas que deberá realizar será aproximadamente la misma que la cantidad de elementos en la lista completa. Que desborda el límite incorporado de Python una vez que llegas a unos 1000 elementos. Tendrá un problema similar al ordenar las listas que ya están en orden inverso.

Para corregir esto, utilice una de las soluciones alternativas sugeridas en la literatura, como elegir un elemento al azar para que sea el pivote o la mediana de los elementos primero, medio y último.

Elegir siempre el primer (o último) elemento como pivote tendrá problemas para el orden de ejecución rápida, el peor de los casos para algunas entradas comunes, como ha visto

Una técnica que funciona bastante bien es elegir el promedio del primer, medio y último elemento.

No desea que la selección de pivote sea demasiado complicada, o dominará el tiempo de ejecución de la búsqueda