Hay un tiempo de ejecución teórico y hay un tiempo de ejecución práctico.
En el peor de los casos, la O grande siempre es buena para el tiempo de ejecución teórico, y solo a veces es buena para el tiempo de ejecución práctico.
La mayoría de los algoritmos de multiplicación de matriz [matemática] O (n ^ p) [/ matemática] (donde p <3) tienen varias desventajas que los hacen no aptos para la computación científica:
- Son súper complicados. Esto hace que sea difícil de entender e implementar. Sin embargo, esto es un inconveniente menor porque solo puede implementarlo una vez (u obtener una implementación de otra persona) y usarlo para siempre.
- Tienen una constante muy grande. Por ejemplo, [matemática] n ^ {2.8} [/ matemática] y [matemática] 100000 n ^ {2.8} [/ matemática] son ambas [matemática] O (n ^ {2.8}) [/ matemática]. Estos sofisticados algoritmos tienen una gran constante de tiempo. Esto, nuevamente, no es un gran inconveniente una vez que su matriz se vuelve lo suficientemente grande.
- No funcionan bien en arquitecturas informáticas modernas. Este es un gran inconveniente por estos motivos:
- Rompen la matriz de una manera que es difícil tener una buena localización del acceso a la memoria. Esto significa que incurriría en una pérdida de caché, lo que ralentizaría sustancialmente el tiempo de ejecución (potencialmente órdenes de magnitud).
- Son difíciles de implementar de forma paralela. La mayoría de los procesadores modernos tienen algún tipo de conjunto de instrucciones SIMD (ARM NEON, SSE, etc.). Estas instrucciones le permiten realizar la misma operación simple en muchos conjuntos de datos al mismo tiempo. La naturaleza compleja de estos sofisticados algoritmos hace que sea difícil utilizar las instrucciones SIMD.
- ¡Son demasiado largos! Más allá del caché de datos, también hay caché de instrucciones. Si el cuerpo de su bucle es tan grande que no cabe completamente en la memoria caché, terminaría golpeando la memoria principal en el bucle. Esto es terrible para el rendimiento. La mayoría de los procesadores modernos tienen un gran caché de instrucciones, por lo que esto es solo un inconveniente menor.
- Hay demasiados bucles y casos diferentes. Los bucles y los casos requieren una comparación y una rama para implementarse. Esto puede causar el enjuague de la tubería de instrucciones (e incluso el caché) debido a la predicción errónea de la rama.
- Migración a GPU. Muchas aplicaciones informáticas científicas ahora están migrando a GPU. Las GPU son muy buenas para realizar muchas operaciones simples en paralelo. Los algoritmos de fantasía tienden a ser difíciles de implementar de esta manera para aprovechar la informática de GPU.
Aquí hay un estudio: Uso de la recursividad para aumentar el rendimiento de ATLAS
Este estudio no tiene en cuenta la vectorización (SIMD). En un momento hice algunas pruebas con implementaciones SIMD. si / cuando tengo tiempo de desenterrar las parcelas, agregaré a esta respuesta.
- ¿Cuál es el ángulo entre los dos vectores [matemática] 6 \ hat i + 6 \ hat j – 3 \ hat k [/ math] y [math] 7 \ hat i + 4 \ hat j + 4 \ hat k [/ math ]?
- Entre la teoría de números, el álgebra lineal y el análisis matemático, ¿cuál de estos tres fue el más difícil para ti como estudiante universitario de matemáticas?
- ¿Cuál es una forma intuitiva de pensar si un conjunto de vectores es linealmente independiente o linealmente dependiente?
- ¿Cuál es la interpretación de los puntajes negativos en los vectores base obtenidos con LSI?
- ¿Qué es un archivo vectorial?
En resumen: en la práctica, los algoritmos sofisticados probablemente generan una mejora nominal en el tiempo de ejecución (si es que lo hacen) que no vale la complicación de implementación.