Lo que el burbujeo me enseñó

No dejo de alegrarme cuando creo que entiendo un tema y de repente aparece una pieza de información adicional que me hace replantearme los preconceptos. Es una situación ideal para repensar algo que, de otra manera, hubiera dado por sentado y nunca me hubiera detenido a considerar.

Contexto

Esta vez viene de la mano de un pequeño experimento que hacemos con nuestros alumnos de Programación Avanzada, en la Universidad Nacional de La Matanza. La clase correspondía a métodos clásicos de ordenamiento, y estábamos analizando el rendimiento de cada uno de ellos. La forma más simple de hacerlo es generar arrays sucesivamente más grandes, y tomar tiempos de ejecución. Las tres configuraciones clásicas son las de array aleatorio, array ordenado y array invertido.

El algoritmo

El algoritmo de ordenamiento por burbujeo tiene una complejidad computacional bien conocida: O(n²) comparaciones, y O(n²) intercambios. El algoritmo básico no puede evitar comparaciones, ya que son parte fundamental de su código. Por lo tanto, siempre compara una cantidad constante de n² veces. Sin embargo, en los tres casos clásicos varía completamente la cantidad de intercambios: si el array viniera ordenado, no necesita hacer intercambios; si viniera aleatoriamente ordenado, haría un promedio de (n²)/2 intercambios; y en el caso invertido haría todos los intercambios posibles: n².

Las mediciones

Armé un pequeñísimo código para tomar mediciones de tiempos, comparaciones e intercambios para una cantidad logarítmicamente ascendente de elementos. Aquí los resultados para cada una de las configuraciones:

Configuración aleatoria

Configuración ordenada

Configuración invertida

Análisis

Y aquí es que los números se contradicen (en principio). Podemos ver que la cantidad de intercambios sigue la tendencia que marca la teoría de complejidad computacional:

Sin embargo, los tiempos son los que llevan la contra:

¿Cómo puede ser que el caso extremo, en el que el array se encuentra invertido, tome menos tiempo que el caso promedio, en el que el array se encuentra en orden aleatorio?

El concepto nuevo (para mí)

No les voy a mentir: cuando sucedió esto, yo no estaba en el aula. Pero me enteré por el grupo de docentes, y quise investigar. Un estudiante nombró el concepto, y eso diparó las búsquedas: el branch prediction unit.

¿Qué es la unidad de predicción de saltos (branch prediction unit)?

En arquitectura de computadoras, un predictor de ramas es un circuito digital que intenta adivinar por qué rama (por ejemplo, en una estructura if-then-else) ejecutará el código hasta que se conozca a ciencia cierta. Su propósito es el de mejorar el flujo de ejecución. Los predictores de rama desempeñan un rol crítico en conseguir un rendimiento alto y efectivo en muchas arquitecturas de microprocesador como la x86.
Fuente: Wikipedia

En mis propias palabras, y aplicado al caso: resulta que la predicción favorece la rama por la cual se realiza el intercambio en el algoritmo de burbujeo. Entonces, ahorra la comparación y ejecuta con una certeza del 100% de los casos en el escenario de array invertido.
En cambio, en el escenario de array aleatorio, no puede realizar las predicciones, y se fuerza a evaluar las condiciones individualmente.

Algo que debo destacar, es que esta tecnología no es nueva, ni mucho menos. Hay primeros experimentos con la técnica que datan de los años ‘50.

Tendré que estar más atento a posibles oportunidades para desbancar preconceptos. ¡Resulta que ahora en el peor caso los algoritmos de ordenamiento funcionan muy bien!

Corolario: Habrá que empezar a probar con algoritmos “casi invertidos”, para ejercitar casos extremos.