P: ¿Cómo explica la localidad de caché el hecho de que la ordenación rápida suele ser más rápida que la ordenación por fusión?
Mi autoridad para responder a esta pregunta proviene de los experimentos que hice en tiempos de ejecución como parte de mi libro, Optimized C ++ . Recomiendo realizar experimentos antes de hacer afirmaciones sobre el rendimiento.
A1: ¿Qué te hace pensar que quicksort es más rápido que el tipo de fusión? Mi observación de la biblioteca estándar de C ++ ordena std :: sort (), que generalmente se implementa como quicksort, y std :: stable_sort (), que es un tipo de combinación, reveló que std :: stable_sort () es más rápido cuando ambos se realizan sobre una matriz.
- ¿Cuándo la piratería se convirtió en algo malo? Pensé que hackear era una forma inteligente / ingeniosa de desarrollar un algoritmo para resolver un problema.
- Si tengo un buen conocimiento de Java, C ++, algoritmos y estructuras de datos y quiero ser un profesional independiente. ¿Cuánto puede ganar alguien con estas habilidades?
- ¿Cómo saben los codificadores cómo codificar e implementar un algoritmo instintivamente?
- Cómo implementar un algoritmo de equilibrio de carga personalizado aparte del algoritmo Round Robin predeterminado en mi Amazon Elastic Load Balancer usando Java SDK para AWS
- ¿Cuándo se debe comenzar a resolver los problemas del Proyecto Euler en HackerRank? He resuelto alrededor de 50 en SPOJ, entonces, ¿es el momento adecuado para comenzar?
A2: Quicksort, como se suele demostrar a los estudiantes universitarios de CS, se implementa sobre una matriz, mientras que la ordenación por fusión se implementa sobre una estructura de datos vinculada. Cuando se compara de esta manera, std :: sort () en una matriz fue aproximadamente un 25% más rápido que list :: sort () en los mismos datos, que es una combinación de clasificación en una estructura de datos vinculada.
Las estructuras de datos vinculados están, por naturaleza, dispersas en la memoria, mientras que los elementos de la matriz están muy juntos. Un desarrollador con mentalidad de rendimiento puede sospechar de la fusión cuando se implementa sobre una estructura de datos vinculada, pero el comportamiento real de la memoria caché puede ser difícil de predecir a partir de una regla general informal como esta.
