ShellSort más rapido que Quicksort ??
Hola mi duda se resumen al titulo de este post, les comento que estaba leyendo el libro estructura de datos en Java de Mark Allen Weis.
Especificamente la parte de Algoritmos de ordenacion.
En ese libro habian 2 algoritmos uno era para el quicksort y el otro para el ShellSort.
Este es el algoritmo de sehllsort, el de quicskor no lo pongo porque es largo, ademas de que java tiene su propio Quicksort ( Arrays.sort ) :
Decidi hacer una prueba de cual de los 2 algoritmos es más rapido asi que los probe :
La primera comparacion que hice tenia estas caracteristicas :
-Tamaño del vector : 1´000´000 de Objetos Integer cuyos valores varian entre 0 y 100´000´000
-Numero de pruebas Seguidas : 10
Tiempo Quicksort : 1680 1599 1531 1781 1766 1679 1652 1504 1785 1543 ( Milisegundos )
Tiempo Shellsort : 6695 6613 6582 6877 6758 6784 6584 6322 6852 6449 ( Milisegundos )
La segunda comparacion que hice tenia estas caracteristicas :
-Tamaño del vector : 50000 de Objetos Integer cuyos valores varian entre 0 y 100´000´000
-Numero de pruebas Seguidas : 15
Tiempo quicksort : 219 166 161 142 172 23 18 17 18 15 18 17 17 17 18 ( Milisegundos )
Tiempo Shellsort : 136 97 73 69 60 72 65 68 66 50 63 67 64 64 66 ( Milisegundos )
Como veran cuando las entradas son muy grandes ( Primera Prueba ) el, se ve claramente la diferencia en velocidad entre quicksort y shellsort.
Pero mi curiosidad se origino al ver los otros resultados osea cuando las entradas son medianas :
Como podran ver al principio el quicksort es mas lento que el shellsort, pero conforme siguen las pruebas los tiempos de los 2 algoritmos reducen
drasticamente su tiempo, hasta un punto donde el quicksort es mas rapido que el shellsort,
¿ Alguien sabe a que se debe eso ?, en el libro que lei menciona algo sobre un caching, he buscado en google pero no encuentro nada.
De lo anterior intui que si se hacian muchas ordenaciones seguidas, por algun motivo quicksort se hace muy rapido, shellsort tambien reduce su tiempo, pero
no tanto como lo hace quicksort.
Pero que pasaba si se hacia solo 1 ordenacion( Esto es el caso mas comun, ya que nadie ordena un arreglo 10 veces seguidas ), hice la prueba y asi que compare los 2 algoritmos haciendo solo 1 prueba por vez . en total hice 10 pruebas
y el resultado fue el suiguiente :
Tiempo Quicksort : 314 184 227 336 374 291 358 209 234 298 ( Milisegundos )
Tiempo Shellsort : 157 153 134 190 164 158 222 178 150 138 ( Milisegundos )
Como podran ver el algoritmo de quicksort es mas lengo que el ShellSort, lo cual no me cabe en la cabeza ya que por teoria
quicksort tiene como complejidad temporal promedio O( n logn ) y el algoritmo de shellsort con incremento 2.2 tiene como
complejitad temporal promedio O( n^(7/6) ).
- Inicie sesión o regístrese para enviar comentarios
Depende, de que depende? de segun como se mire todo depende...
La respuesta, al parecer, es como en muchos otros casos "depende". Diferentes algoritmos de ordenamiento reaccionan diferente a ante diferentes listas de datos a ordenar.
En estos casos, hiciste ordenamiento de 50,000 elementos, pero solo hiciste 10 ordenamientos (con 10 listas distintas?). Tal ves tu resultado seria diferente si hicieras 50,000 ordenamientos con 50,000 listas distintas... asi es mas probable que te topes con listas que son cercanas al "peor escenario posible" para ambos algoritmos. Recuerda que lo importante no es si un algoritmo es mas rápido que otro para ciertas listas, si no que tan mal puede llegar a comportarse si empiezan a presentarse casos "malos". Es posible que shellsort se mas rapido que quicksort para listas mas pequeñas, pero la pregutna es... como se degrada su rendimiento conforme crece la lista? si dibujas una grafica con 500,000 ejecuciones, en donde cada 10,000 duplicas el tamaño de la lista, cual curva señala una degradacion grave del rendimiento? sospecho que la perdedora entonces sera shellsort, aunque al principio con listas mas cortas podria ser quicksort el que se ve mal, conforme la lista aumente de tamaño las cosas empezaran a verse mal para shellsort.
¿Cual usar entonces para un problema del mundo real? Bueno, supongo que depende del tamaño de listas que piensas ordenar, inclusive podrias preguntar por el tamaño de la lista antes de empezar y usar un algoritmo o el otro, algunas bases de datos inclusive llevan estadisticas y pueden llegar a probar distintos algoritmos para un determinado conjunto de datos hasta encontrar el que se comporte mejor.
En realidad hice muchisimos
En realidad hice muchisimos ordenamientos, solo puse 10 porque eran los que representaban en resumen el resultado de todos los demas ordeanmientos, oe pero una duda, cuando hice las pruebas de ordenamientos, para un vector de tamaño medio, el shellsort y el quicksort disminuian el tiempo que se demoraban en ordenar el vector, esto lo puse en la segunda prueba
-Tamaño del vector : 50000 de Objetos Integer cuyos valores varian entre 0 y 100´000´000
-Numero de pruebas Seguidas : 15
Tiempo quicksort : 219 166 161 142 172 23 18 17 18 15 18 17 17 17 18 ( Milisegundos )
Tiempo Shellsort : 136 97 73 69 60 72 65 68 66 50 63 67 64 64 66 ( Milisegundos )
He heho muchisimas pruebas y todas tienen ese patron, osea ambos comienzan mal pero luego su tiempo va disminuyendo, y luego se estabilizan , en el caso de la prueaba que hice el tiempo del Quicksort se trunco en 17 segundos y el del Shellsort en 64, mi duda es porque disminuye su tiempo.
Si como muchos dicen dependiera de la aleatoridad de los datos de entrada, entonces al hacer las pruebas debera haber algun resultado en el que quicksort comienze con
17 o 18 milisegundos pero nunca me sucedio eso, en todas las que hice simepre comienza con alrededor de 200 milisegundos y disminuy hasta 17 o 18
Muchisimos es impreciso. Tambien toma en cuenta a HotSpot
"Muchisimos" es muy impreciso ;-)... si quieres resultados que te den una idea clara del desempeño, tienes que hacerle como te dije "500,000 ejecuciones, en donde cada 10,000 duplicas el tamaño de la lista", ademas, por cada ejecucion, debes usar la misma lista para shellsort y para quicksort (para evitar que por mala suerte les toquen peores listas a uno y no al otro) y analizar la curva de tiempo de desempeño resultante. (Lo mas probable es que mucho antes de las 500,000 ejecuciones te des cuenta de cual es mas rapido)
Otra factor que podría esta haciendo que cada ejecución se haga mas rápida es HotSpot. Java ajusta y reajusta el código que ejecuta para hacerlo mas eficiente, tal ves eso explique el efecto que ves (sobretodo en listas cortas, como las que manejas de 50,000 elementos)