Y el claro ganador es C

Ya no seguí con mis comparaciones entre C y Java porque, de verdad, he andado demasiado ocupado, con cosas académicas, de trabajo y personales. Pero hoy por fin terminé de escribir las pruebas unitarias para las estructuras de datos que estamos viendo en mi curso de ídem, y como la última que hemos visto fueron árboles rojo-negros, decidí echarle un ojo a mis pruebas.

Para los que no lo sepan, los árboles rojo-negros son árboles binarios autobalanceados, lo que en su caso particular quiere decir que un camino simple (sin regresarse nunca) de cualquier nodo a cualquiera de sus hojas siempre tiene el mismo número de nodos negros. Eso se traduce (por una propiedad de los árboles rojo-negros que dice que un nodo rojo siempre tiene dos hijos negros) a que la diferencia más grande de longitudes entre ramas es que una tenga k nodos, y la otra 2k (una rama con puros nodos negros, otra con negro, rojo, negro, rojo, etc.) La estructura permite agregar y eliminar elementos con complejidad en tiempo acotada por la altura del árbol; que siempre esté balanceado garantiza que dicha complejidad es siempre O(log n). Los árboles rojo-negros son una estructura de datos utilizada en todos lados por (como veremos ahorita) su espectacular desempeño; en particular, el kernel de Linux incluye una implementación desde mi punto de vista preciosa y humilladoramente elegante; la pueden checar en /usr/src/linux/lib/rbtree.c.

No voy a poner mi código para agregar o eliminar elementos a árboles rojo-negros; no sólo porque mis alumnos aún no entregan su práctica, sino además porque es demasiado engorroso. No es ciencia de cohetes, pero sí hay suficientes casos como para que uno tenga que ir haciendo dibujitos en papel para no perderse en qué punto del algoritmo nos hayamos. Como sea, terminé de escribir el código en Java y C como siempre, y corrí unas pruebas con un millón de elementos (me pueden pedir el código, si quieren).

Ambas implementaciones le ganan por mucho a MergeSort; me imagino que algo tendrá que ver el uso de memoria (MergeSort crea el equivalente a log n listas con n elementos cada una durante la ejecución del algoritmo, mientras que los árboles rojo-negros usan O(1) de memoria al agregar). Ambas son básicamente idénticas, incluyendo que usan recursión en el paso interesante: es recursión de cola, por lo que sencillamente lo pude haber reescrito iterativamente; pero como les digo el algoritmo ya es lo suficientemente engorroso como para que lo complicara aún más con un acumulador. La única diferencia discernible en el uso de cada versión, es que guardo la raíz cada vez que agrego en un elemento en C; tengo que hacerlo para no tener que andarla persiguiendo cada vez. En Java, al usar el diseño orientado a objetos, siempre tengo una variable de clase para la raíz.

Con Java, el algoritmo tarda 0.777676317 segundos (en promedio) en agregar 1,000,000 (un millón) de elementos. C sin optimizaciones tarda 0.376824469 segundos; con optimizaciones tarda 0.183850452 segundos. Por supuesto ambas versiones son genéricas; la de Java propiamente usando genéricos, la de C usando void* como tipo de dato, y pasando una apuntador a función para hacer comparaciones. Con 10,000,000 (diez millones) de elementos la diferencia es todavía más abismal; Java tarda 20.266719661 segundos, mientras que la versión en C tarda 1.881134884 segundos; pero esto ya no me extraña, dado que como ya había visto la última vez, con 10,000,000 de elementos, Java no puede evitar no utilizar el swap.

No me queda claro por qué C gana; dado que MergeSort también es recursiva, y ahí Java le ganaba a C, hubiera esperado que en el caso de los árboles rojo-negros pasara lo mismo. Lo que sí es que el desempeño de la estructura de datos es espectacular, y a mí me parece de las estructuras más bonitas y poderosas que existen. Por supuesto los diccionarios (¿alguien sabe una mejor traducción para hash table?) también son muy padres; pero siempre está el hecho de que en el peor de los casos el buscar y el eliminar tardan O(n). Y como mis experimentos con QuickSort me recordaron hace unas semanas, el peor caso (o uno suficientemente malo) siempre anda asomándose detrás de las esquinas.