2010-07-31 16 views
9

He leído que qsort es solo un tipo genérico, sin promesas sobre la implementación. No sé cómo varían las bibliotecas de una plataforma a otra, pero suponiendo que las implementaciones de Mac OS X y Linux son muy similares, son las implementaciones qsort recursivas y/o requieren una gran cantidad de la pila?¿El qsort de stdlib es recursivo?

Tengo una gran matriz (cientos de miles de elementos) y quiero ordenarla sin soplar mi pila al olvido. Alternativamente, ¿alguna sugerencia para un equivalente para matrices grandes?

Respuesta

21

Aquí hay una versión de BSD, los derechos de autor de Apple, presumiblemente utilizado en OS X en algún momento u otro:

http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/kern/qsort.c

Es llamada recursiva, aunque el límite superior en la profundidad de recursión es pequeña , como Blindy explica.

Aquí hay una versión de glibc, presumiblemente utilizado en los sistemas Linux en algún momento u otro:

http://www.umcs.maine.edu/~chaw/200801/capstone/n/qsort.c

Es no llamada recursiva. Por exactamente la misma razón por la que el límite en la recursión de llamadas es pequeño, puede usar una pequeña cantidad fija de la pila para administrar su recursión de bucle.

¿Me molestan las nuevas versiones? No ;-)

Para unos cientos de miles de elementos de matriz, incluso la implementación de llamada recursiva no llamará a más de 20 niveles de profundidad. En el gran esquema de cosas que no es profundo, excepto en dispositivos integrados muy limitados, que no tendrían suficiente memoria para tener una matriz tan grande para ordenar en primer lugar. Cuando N está limitado anteriormente, O (log N) obviamente es constante, pero más que eso es una constante bastante manejable. Por lo general, 32 o 64 veces "pequeño" es "razonable".

+0

+1 para ver realmente el código fuente. Es interesante observar que glibc usa un híbrido de clasificación de inserción/quicksort en su qsort() – nos

+1

@nos: IIRC eso es lo que Knuth le dice que haga, tan interesante pero con suerte no sorprendente ;-) –

+0

+1 por "32 o 64 veces" small 'is' reasonable '":-) –

9

Sí, es recursivo. No, probablemente no usará grandes cantidades de pila. ¿Por qué no simplemente probarlo? La recursividad no es un tipo de bogey: es la solución preferida para muchos problemas.

+0

excelente respuesta, Butterworth :) – abelenky

+0

Confía en mí, yo uso recursividad todo el tiempo! Nunca antes para profundidades como esta, de ahí mi pregunta primero. – Joe

+2

@Joe Profundidades como qué? La recursión en quicksort empuja los fotogramas de la pila (es decir, las variables locales y las direcciones de retorno) a la pila, no a las copias de la cosa que se está ordenando. Esto es muy poca información. –

11

Ya sabes, la parte recursiva es bastante profunda. En 64 niveles de recursión (que es ~ 64 * 4 = ~ 256 bytes de total de la pila) puede ordenar una matriz de tamaño ~ 2^64, es decir, una matriz tan grande como pueda en una CPU de 64 bits, que es 147573952589676412928 bytes para enteros de 64 bits. ¡Ni siquiera puedes sostenerlo en la memoria!

Preocuparse por cosas que importan.

+0

+1. Pueden ser unos cuantos bytes más que 256 dependiendo de cuánto se empuja en la pila para cada nivel, pero sigue siendo una pequeña constante. – ShreevatsaR

+3

-1: Esto está mal. Quicksort tiene la peor complejidad de espacio de caso O (n), no O (log n). Una gran matriz * puede * volar la pila. –

+6

@Luther: cuando se implementa correctamente (cuando se repiten, primero se ordena la partición más pequeña), el uso de la pila se limita a un crecimiento aproximadamente logarítmico. Para ser exacto, Knuth lo da como [lg (N + 1)/(M + 2)] (con "[]" que significa "piso"), donde N = número de elementos que se ordenan y M = tamaño de la partición donde deje de recurrir (suponiendo una Quicksort "mejorada" que cambia a ordenar por inserción cuando todo está casi ordenado). –

1

Con quicksort, la pila crecerá logarítmicamente. Necesitará mucho de elementos para explotar su pila.

+1

@msw: Al ver que insistes en ser pedante, olvidaste definir * N * como el tamaño de la matriz. En lo que a mí respecta, el término "crecimiento logarítmico" generalmente se entiende como O (lg (* n *)) cuando se habla de algoritmos. –

0

Una implementación de qsort que puede fallar en arreglos grandes está extremadamente rota. Si realmente está preocupado, iría a RTFS, pero sospecho que cualquier implementación medio decente usará un algoritmo de ordenamiento in situ o usará malloc como espacio temporal y recurrirá a un algoritmo en contexto si falla malloc.

1

Supongo que la mayoría de las implementaciones modernas de qsort realmente usan el algoritmo Introsort. Un Quicksort razonablemente escrito no volará la pila de todos modos (primero clasificará la partición más pequeña, lo que limita la profundidad de la pila al crecimiento logarítmico).

Introsort va un paso más allá - para limitar la peor de las situaciones complejas, si ve que Quicksort no está funcionando bien (demasiada recursión, por lo que podría tener O (N) complejidad) ll cambiar a un heapsort que garantiza O (N log N) complejidad y límites pila de uso, así. Por lo tanto, incluso si el Quicksort que utiliza está escrito de manera descuidada, el cambio a Heapsort limitará el uso de la pila de todos modos.

2

Recuerdo haber leído en este libro: C Programming: A Modern Approach que la especificación ANSI C no define cómo implementar qsort.

Y el libro que escribió qsort podría ser en realidad una especie de otra especie, ordenamiento por mezcla, la ordenación por inserción y por eso no la ordenación de burbuja: P

Por lo tanto, la aplicación qsort no pueden ser recursivas.

+2

Los buenos estándares no describen cómo implementar nada; sin embargo, hacen cosas como géneros que especifican garantías mínimas de complejidad que pueden limitar la elección del algoritmo para las implementaciones. –

+2

@Neil: independientemente de lo que hagan los buenos estándares, el estándar C no especifica las complejidades de 'qsort' y' bsearch'. Afortunadamente, la pregunta es acerca de dos implementaciones en particular, por lo que el estándar es bastante irrelevante. Si Apple va a cambiar de forma perversa OS X a Bogosort en la próxima versión, entonces si salirse con la suya no dependerá de si rompe el estándar C ... –

4

Una implementación correcta de qsort no requiere más que log2 (N) niveles de recursión (es decir, profundidad de la pila), donde N es el tamaño de matriz más grande en la plataforma determinada. Tenga en cuenta que este límite se aplica independientemente de lo bueno o malo el reparto pasa a ser, es decir que es el peor de los casos profundidad de recursión. Por ejemplo, en una plataforma de 32 bits, la profundidad de recursión nunca superior a 32, en el peor de los casos posibles, dada una aplicación sensata de qsort.

En otras palabras, si usted está preocupado por el uso de la pila en concreto, que no tienen nada de que preocuparse, a menos que se trata de alguna implementación extraña de baja calidad.

0

El peor de los casos el espacio-complejidad de una aplicación ingenua ordenación rápida (que sigue siendo una opción popular para qsort) es O (n). Si la aplicación se modifica para ordenar la primera optimización más pequeña arary y cola recursividad o un pila explícita e iteración se utiliza continuación el espacio peor de los casos puede reducirse a O (log N), (lo que más respuestas aquí ya escribió). Por lo tanto, no explotará su pila si la implementación de clasificación rápida no se rompe y la biblioteca no se rompió por indicadores de compilación inadecuados. Pero, por ejemplo, la mayoría de los compiladores que soportan la eliminación de la recursión de cola no harán esta optimización en compilaciones de depuración no optimizadas. Una biblioteca construida con las banderas equivocadas (es decir, no es suficiente optimización, por ejemplo, en el dominio incrustado donde a veces se construye su propia libc depuración) se puede bloquear la pila a continuación.

Para la mayoría de los desarrolladores, esto nunca será un problema (han probado libc de proveedores que tienen una complejidad de espacio O (log N)), pero diría que es una buena idea tener un ojo en posibles problemas de biblioteca tiempo al tiempo.

ACTUALIZACIÓN: He aquí un ejemplo de lo que quiero decir: un error en libc (desde 2000) donde qsort comenzaría a agotar memoria virtual porque la implementación qsort cambiaría internamente a mergesort porque aunque hay memoria suficiente para contener una matriz temporal .

http://sources.redhat.com/ml/libc-alpha/2000-03/msg00139.html

+2

Interlocutor pregunta sobre sistemas particulares, que tienen una calidad razonable de implementación . "la implementación ingenua de quicksort sigue siendo una opción popular" es simplemente falsa. No es popular entre las personas que escriben bibliotecas C, que es lo que concierne a la pregunta. –

+1

Interlocutor preguntado sobre "Linux". Linux no tiene implementación de qsort, porque es un kernel. qsort es una función de la biblioteca C-runtime para la que hay varias opciones (glibc, uclibc, newlib, dietlibc ... y luego hay algo que han puesto en Android). También: mira mi actualización. –

+0

-1 de mí: un hipotético qsort mal implementado es bastante irrelevante. El glibc qsort se implementa bastante bien, y supongo que el OS X uno también. Una mala implementación de qsort es un error que debe corregirse. –

Cuestiones relacionadas