algorithm - fastest - timsort python
¿Por qué el smoothsort no es más común? (3)
Después de leer this artículo de Wikipedia sobre algoritmos de clasificación, parece que smoothsort es el mejor algoritmo de clasificación que existe. Tiene un rendimiento superior en todas las categorías: mejor, promedio y peor. Nada lo supera en ninguna categoría. También tiene requisitos de memoria constante. El único inconveniente es que no es estable.
Es mejor que el timsort en la memoria, y es mejor que el quicksort tanto en el peor de los casos como en la memoria.
Pero nunca escuché sobre smoothsort. Nadie lo menciona nunca, y la mayoría de las discusiones parecen girar en torno a otros algoritmos de clasificación.
¿Porqué es eso?
Bueno, primero diría que no es como Smoothsort no es famoso. Depende de la necesidad de un usuario y también depende de si el usuario lo usa o no.
La ventaja de smoothsort es que se acerca más al tiempo O (n) si la entrada ya está clasificada en algún grado, mientras que la media de la pila promedia O (n log n) independientemente del estado inicial ordenado.
De la Documentation : -
El algoritmo smoothsort necesita poder mantener en memoria los tamaños de todos los montones de la cadena. Como todos estos valores son distintos, esto generalmente se hace usando un vector de bits. Además, dado que hay como máximo números O (log n) en la secuencia, estos bits se pueden codificar en O (1) palabras máquina, suponiendo un modelo de máquina transdicotómica.
El rendimiento de Big-O es excelente para la publicación de trabajos, pero en el mundo real también tenemos que mirar las constantes. Quicksort ha sido el algoritmo de elección para la clasificación en memoria inestable, en el lugar, durante tanto tiempo, porque podemos implementar su bucle interno de manera muy eficiente y es muy amigable con el caché. Incluso si puede implementar el bucle interno de smoothsort tan eficientemente, o casi tan eficientemente, como el de quicksort, probablemente encontrará que su tasa de errores de caché lo hace más lento.
Mitigamos el peor rendimiento del quicksort al dedicar un poco más de esfuerzo a elegir buenos pivotes (para reducir el número de casos patológicos) y detectar casos patológicos. Busque introsort . Introsort ejecuta el quicksort primero, pero cambia a heapsort si detecta una recursión excesiva (lo que indica un caso patológico de quicksort).
Mejor asintótico no implica un mejor rendimiento (aunque generalmente resulta así). La constante oculta puede ser varias veces más grande, haciendo que sea más lenta que otro algoritmo (con la misma o peor complejidad asintótica) en matrices de tamaño relativamente pequeño (donde la matriz relativamente pequeña , de hecho, puede ser de tamaño arbitrario, 10 100 , para ejemplo. Eso es un análisis asintótico). Pero no sé nada sobre las constantes ocultas de smoothsort.
Por ejemplo, hay un algoritmo O (n) de peor caso en el tiempo para encontrar la estadística de orden k, pero es tan complejo que la versión peor de O (n log n) la supera en la mayoría de los casos.
Además, hay una comparison interesante:
... Como puede ver, tanto Timsort como Smoothsort no cortaron la mostaza. Smoothsort es peor que AWL en todos los casos (incluso con std: bitset reemplazado con operaciones de bits sin procesar) ...