El problema con Quicksort es que compara constantemente los valores y esto es doloroso para los procesadores canalizados porque los valores generalmente son aleatorios y no tienen una tendencia que pueda predecirse. De esta manera, las instrucciones se ejecutan a un ritmo muy lento, haciendo mal uso de las capacidades de canalización del procesador. En otras palabras, ejecutar una instrucción cada 20 o 25 ciclos. Por lo tanto, reduciendo la velocidad 20 o 25 veces …
En otras palabras, los procesadores de hoy en día son capaces de predecir muy bien las tendencias para las instrucciones de ramificación condicional. Por ejemplo, en un ciclo, usualmente saltas a la primera instrucción del ciclo. Solo faltan las últimas instrucciones. Por lo tanto, obtienen previamente las instrucciones que se están ejecutando, aunque el procesador no sabe si será necesario completarlas, pero supone que tendrán que ejecutarse. Esto permite que el procesador tenga la tubería llena y ejecute una instrucción por ciclo en promedio.
Cuando no puede predecir, hay un 50% de posibilidades de que pierda su predicción, por lo que la tubería del procesador se vacía cuando la predicción falla, causando una desaceleración considerable de la velocidad de ejecución.
- ¿Cómo funciona la clasificación bayesiana? ¿Cuáles son algunas de sus aplicaciones?
- Cómo resolver este problema en la búsqueda binaria
- ¿La informática es solo sobre programación y algoritmos?
- ¿Cuáles son las desventajas del algoritmo genético?
- ¿Mejorará la velocidad de búsqueda y clasificación de algoritmos o hemos alcanzado el límite?
Esta es la razón por la que otros algoritmos como el tipo Radix tienen más posibilidades de tener éxito en los procesadores canalizados de hoy en día. Nunca comparan, solo cuentan, leen y almacenan valores, que es totalmente paralelo y con muy buenas características canalizadas.
Sin embargo, esos algoritmos similares a Radix tienen un problema de localidad de memoria que Quicksort no tiene. ¡Siempre hay pros y contras en todas las formas de vida! Lea este documento para obtener una descripción detallada de Quicksort y radi sort, El efecto de la clasificación local en los algoritmos de clasificación paralela.
