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 rojinegros, decidí echarle un ojo a mis pruebas.

Para los que no lo sepan, los árboles rojinegros 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 rojinegros 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 rojinegros 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 rojinegros; 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 rojinegros 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 rojinegros 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.

 Imprimir entrada

Total que Omar me pidió mi código para hacer él mismo pruebas, lo que me obligó a limpiarlo un poquito. Entre las cosas que hice al limpiar mi código, fue cambiar cómo llenaba los arreglos y listas; originalmente los estaba llenando así (en Java):

import java.util.Random;
// ...
    Random r = new Random();
    // ...
    int n = r.nextInt() % 100;

Y así en C:

#include <stdlib.h>
// ...
    srand((unsigned int)time(NULL));
    // ...
    int n = rand() % 100;

El cambio que hice fue el reemplazar el número mágico 100 con N en el módulo al generador de números pseudo aleatorios, donde N es el número de elementos. Esto cambió radicalmente los resultados; para ponerlo en perspectiva, aquí están los resultados en C de una corrida (suelen ser todos muy similares) con módulo 100 (incluí el qsort de glibc a sugerencia de otro lector):

Tiempo QuickSort (normal): 46.125371409 segundos
Tiempo QuickSort (int): 6.318009789 segundos
Tiempo QuickSort (memcpy): 29.476040174 segundos
Tiempo QuickSort (long): 4.455134060 segundos
Tiempo QuickSort (glibc qsort): 0.182938334 segundos
Tiempo MergeSort (lista): 5.097989382 segundos
Tiempo MergeSort (dlista): 3.018067951 segundos

En Java los números son:

Tiempo QuickSort (int): 2.231362337 segundos
Tiempo QuickSort (genéricos): 35.452854731 segundos
Tiempo MergeSort: 2.599635738 segundos

Haciendo módulo N, los resultados son, en C:

Tiempo QuickSort (normal): 0.558278904 segundos
Tiempo QuickSort (int): 0.117254171 segundos
Tiempo QuickSort (memcpy): 0.279380050 segundos
Tiempo QuickSort (long): 0.121708671 segundos
Tiempo QuickSort (glibc qsort): 0.220501083 segundos
Tiempo MergeSort (lista): 5.311177622 segundos
Tiempo MergeSort (dlista): 3.196143267 segundos

Y en Java:

Tiempo QuickSort (int): 0.172914364 segundos
Tiempo QuickSort (genéricos): 0.578500354 segundos
Tiempo MergeSort: 2.15927644 segundos

Al inicio me súper saqué de onda, pero no tardé en encontrar la respuesta. Si N=1000000 (un millón), y cada entero en mi arreglo está entre 0 y 99 (inclusive), eso quiere decir que en promedio cada elemento del arreglo está repetido 10,000 veces, lo que hace que la probabilidad de encontrar un pivote malo (el mínimo o máximo del arreglo) sea mucho mayor que si estuvieran mejor distribuidos los valores. Es por ello que cuando cambio a hacer módulo N, todas mis versiones del algoritmo mejoran, algunas por varios órdenes de magnitud; en general el pivote es un buen pivote. Esta no es toda la historia, por supuesto; de ser así sólo tendría que elegir un pivote aleatorio y todo funcionaría más rápido, y como expliqué en la entrada anterior, en mis pruebas usar un pivote aleatorio no mejora sustancialmente el desempeño del algoritmo. Me parece que teniendo tantos elementos y tan poquitos valores (comparativamente) para inicializarlos, sencillamente ocurre muchas veces que un subarreglo tiene muchos elementos iguales, y entonces incluso un pivote aleatorio tiene mucha probabilidad de ser el mínimo o el máximo.

Sin embargo, esto no parece molestarle a qsort de glibc; es endiabladamente rápido. Incluso en mi versión módulo 100 corre en menos de medio segundo, y de hecho es la única implementación del algoritmo que lo hace. Como le comentaba al lector que me recomendó probar con qsort, la complejidad del mismo es más de un orden de magnitud mayor que mis versiones: qsort son unas 250 líneas de código no muy fácil de leer a comparación de 22 líneas en cada una de mis versiones. La complejidad radica en primer lugar en cómo encuentra el pivote: selecciona la mediana entre el primer, medio y último elementos del subarreglo (ordenándolos de paso); y en segundo lugar en que no hace recursión: utilizando una pilita se ahorra el estar gastando registros de activación, y mete todo dentro de un while.

No sé si sea eso lo que lo hace el ganador indiscutible de las distintas implementaciones; lo que sí sé es que glibc lo comenzaron a escribir a inicios de los ochentas, y que en estos treinta años le han metido todas las optimizaciones que se les han podido ocurrir. De cualquier forma, estoy ahora más contento con mis implementaciones en C: si el arreglo tiene sus valores bien distribuidos, cada una de mis versiones en C le gana a su equivalente en Java, y de hecho mi mejor versión genérica en C (que tiene exactamente la misma firma de qsort, por cierto) es sólo 0.05 segundos más lenta. Que no está nada mal, si me permiten decirlo.

De cualquier forma, los arreglos con muchos elementos repetidos son una entrada válida de QuickSort, así que Java sigue siendo bastante bueno en su versión para enteros (por cierto, mi versión genérica era desde el inicio mejor que la de Java; lo que pasa es que en Java el módulo incluye valores negativos, y entonces Java tenía el doble de valores distintos que la versión de C), y no terriblemente lento en comparación en las otras versiones. Para cosas genéricas C le puede ganar fácilmente; pero usando enteros nada más, Java le gana de calle a mi versión en C para arreglos con muchos elementos repetidos. Y de hecho implementando una versión iterativa de QuickSort, no dudo que Java le diera una buena pelea a qsort (un torito, para el que quiera animarse).

La otra conclusión importante es ver la enorme diferencia que puede significar el tipo de entrada para QuickSort; es por eso que Java utiliza MergeSort en general en sus algoritmos de ordenamientos. Es más lento en el mejor caso de ambos, sin duda; pero siempre es O(n log n). Además es estable (no cambia el orden de dos elementos iguales), lo que también está padre.

Dado que ya limpié el código gracias a Omar, lo pueden bajar de aquí. Dado que son implementaciones de una estructura y dos algoritmos que probablemente sean los más conocidos en el mundo, ni siquiera le pongo licencia a los archivos.

 Imprimir entrada

Estoy enseñando Introducción a Ciencias de la Computación II (mejor conocida como ICC-2) por primera vez en mi vida, en gran medida por un ligero error administrativo. La verdad es que me estoy divirtiendo como enano (al parecer, tristemente disfruto yo más el curso que mis alumnos), y entre las cosas divertidas que decidí hacer fue el darle a mis alumnos la oportunidad de hacer las prácticas en C (en lugar de Java) por un punto extra durante el curso, o medio si hacen al menos la mitad. Desafortunadamente, ninguno de mis alumnos me ha entregado una práctica escrita en C.

Como sea, para poder dejarles las prácticas en C a mis alumnos, primero tengo que hacerlas yo, y eso es en gran medida la razón de que me esté divirtiendo tanto. Por supuesto también hago las prácticas en Java; como ICC-2 es en gran parte estructuras de datos, esto también significa ver las características novedosas de Java, como son iteradores y genéricos. Lo cual también es muy divertido; especialmente cuando puedo comparar los dos lenguajes en cosas como velocidad de ejecución.

Como es necesario siempre que uno ve arreglos y listas, les dejé a mis estudiantes que programaran QuickSort y MergeSort. Yo recuerdo que como estudiante tuve que programar esos algoritmos al menos tres veces: la primera en ICC-2, la segunda en Análisis de Algoritmos, y ahora sí que como dice la canción, la tercera por placer. También recuerdo claramente que QuickSort me parecía el mejor de ambos algoritmos; la inocencia de tener veinte años, supongo.

Total que implementé ambos algoritmos en C y en Java, y me llevé una sorpresa con los resultados. Voy a relatar lo que resultó de investigar porqué las diferencias en velocidades, que la verdad yo no termino de entender.

Aquí está QuickSort en Java:

public static void swap(T[] a, int i, int j) {
    if (i == j)
        return;
    T t = a[j];
    a[j] = a[i];
    a[i] = t;
}

public static < T extends Comparable < T > >
                 void quickSort(T[] a) {
    quickSort(a, 0, a.length-1);
}

private static < T extends Comparable < T > >;
                  void quickSort(T[] a, int ini, int fin) {
    if (fin - ini < 1)
        return;
    int i = ini + 1, j = fin;
    while (i < j)
        if (a[i].compareTo(a[ini]) > 0 &&
            a[j].compareTo(a[ini]) < = 0)
            swap(a, i++, j--);
	else if (a[i].compareTo(a[ini]) <= 0)
	    i++;
	else
	    j--;
    if (a[i].compareTo(a[ini]) > 0)
        i--;
    swap(a, ini, i);
    quickSort(a, ini, i-1);
    quickSort(a, i+1, fin);
}

Y aquí está en C:

inline static void
swap(void** a, int i, int j)
{
	if (i == j)
		return;
	void* t = a[i];
	a[i] = a[j];
	a[j] = t;
}

void
quicksort(void** a, int n, func_compara f)
{
	quicksort_aux(a, 0, n-1, f);
}

static void
quicksort_aux(void** a, int ini, int fin, func_compara f) {
	if (fin - ini < 1)
	    return;
	int i = ini + 1, j = fin;
	while (i < j)
		if (f(a[i], a[ini]) > 0 &&
                    f(a[j], a[ini]) < = 0)
			swap(a, i++, j--);
		else if (f(a[i], a[ini]) <= 0)
			i++;
		else
			j--;
	if (f(a[i], a[ini]) > 0)
		i--;
	swap(a, ini, i);
	quicksort_aux(a, ini, i-1, f);
	quicksort_aux(a, i+1, fin, f);
}

(En mi blog el código aparece bonito con destacamiento de sintaxis; no sé cómo aparecerá en RSS, pero dudo que bonito.)

Con el código así, la versión en Java necesita 33.4 segundos (en promedio en mi máquina) para ordenar un arreglo de un millón (1,000,000) de elementos aleatorios. Sin optimizaciones, la versión en C tarda 114.7 segundos; lo cual es una diferencia brutal, si me permiten decirlo. Con la mejor optimización (-O3; el resultado es idéntico a -Ofast), esta velocidad baja a 44.85 segundos; mucho mejor, pero de cualquier forma más lento que con Java.

La versión en C utiliza void** como tipo del arreglo, y recibe un apuntador a función f justamente para emular los genéricos de Java; la idea es que el QuickSort de C pueda ordenar arreglos de cualquier tipo de elemento. Nada más por completez, incluyo la definición del tipo func_compara, así como la implementación usada para estas pruebas:

typedef int  (*func_compara)      (const void*   a,
				   const void*   b);

int
compara_enteros(const void* a, const void* b) 
{
	int aa = *((int*)a);
	int bb = *((int*)b);
	return aa - bb;
}

Mi primera impresión fue que estos “genéricos” en C (altamente basados en la biblioteca GLib) le estaban dando en la madre a la velocidad de ejecución de mi implementación en C. El andar siguiendo los apuntadores, sacar el valor de las referencias en compara_enteros, y los castings probablemente eran la razón (pensaba yo) de que mi versión en C fuera (ligeramente) más lenta que la de Java. Así que hice trampa y volví a implementar QuickSort, pero esta vez nada más para enteros:

inline static void
swap_int(int* a, int i, int j)
{
	if (i == j)
		return;
	int t = a[i];
	a[i] = a[j];
	a[j] = t;
}

void
quicksort_int(int* a, int n)
{
	quicksort_int_aux(a, 0, n-1);
}

static void
quicksort_int_aux(int* a, int ini, int fin) {
	if (fin - ini < 1)
	    return;
	int i = ini + 1, j = fin;
	while (i < j)
		if (a[i] > a[ini] &&
                    a[j] < = a[ini])
			swap_int(a, i++, j--);
		else if (a[i] <= a[ini])
			i++;
		else
			j--;
	if (a[i] > a[ini])
		i--;
	swap_int(a, ini, i);
	quicksort_int_aux(a, ini, i-1);
	quicksort_int_aux(a, i+1, fin);
}

No muy sorprendentemente, esta versión le partió completamente su madre a la de Java: tarda en promedio 6.35 segundos. Hago notar que los elementos del arreglo son generados aleatoriamente; por lo que el escoger un pivote aleatorio entre ini y fin no serviría (en teoría) de nada. Ciertamente no marcó ninguna diferencia en mis pruebas.

Aunque esta versión es bastante rápida, estaba haciéndo muchísima trampa. De nada (o muy poco) me sirve un QuickSort rapidísimo, si voy a tener que reimplementarlo cada vez que cambie el tipo de mis arreglos. Así que me puse a pensar cómo mejorar una versión “genérica” en C. La respuesta es que sí se puede, pero es bastante feo desde mi punto de vista.

La idea es sencillamente utilizar aritmética de apuntadores, y al intercambiar elementos el copiarlos usando la memoria:

inline static void
swap_memcpy(void* a, int i, int j, size_t s, void* t)
{
	if (i == j)
		return;
	memcpy(t, a+(i * s), s);
	memcpy(a+(i * s), a+(j * s), s);
	memcpy(a+(j * s), t, s);
}

void
quicksort_memcpy(void* a, int n, size_t s, func_compara f)
{
	void* t = malloc(s);
	quicksort_memcpy_aux(a, 0, n-1, f, s, t);
	free(t);
}

static void
quicksort_memcpy_aux(void* a, int ini, int fin,
                    func_compara f, size_t s, void* t) {
	if (fin - ini < 1)
	    return;
	int i = ini + 1, j = fin;
	while (i < j)
		if (f(a+(i*s), a+(ini*s)) > 0 &&
                    f(a+(j*s), a+(ini*s)) < = 0)
			swap_memcpy(a, i++, j--, s, t);
		else if (f(a+(i*s), a+(ini*s)) <= 0)
			i++;
		else
			j--;
	if (f(a+(i*s), a+(ini*s)) > 0)
		i--;
	swap_memcpy(a, ini, i, s, t);
	quicksort_memcpy_aux(a, ini, i-1, f, s, t);
	quicksort_memcpy_aux(a, i+1, fin, f, s, t);
}

Esta versión es superior a la de void** ya que puedo pasarle un arreglo de tipo int* directamente, y funciona sin problema; la versión void** necesita por fuerza que le pase un arreglo de apuntadores al tipo que me interesa; en otras palabras, tengo que pasarle un int**, y además tengo que hacerle cast a void**. Además de esto (que no es poco), es más rápido que la primera versión en C, y más rápido que la versión en Java. No por mucho, pero más rápido: tarda 27.5 segundos con un millón de elementos.

Por lo demás, está bastante fea; necesito por fuerza el tamaño del tipo que me interesa ordenar (porque el arreglo lo veo como un chorizo enorme de bytes), y por lo mismo para intercambiar elementos del arreglo debo utilizar memcpy, además de que cargo por todas partes un pedazo de memoria t para guardar el valor temporal durante el intercambio; la alternativa hubiera sido usar variables globales (the horror!), o solicitar y liberar memoria en cada intercambio de variables.

Hasta aquí estaba más o menos satisfecho: ya tenía una versión “genérica” en C que era más rápida que la de Java (aunque desde mi punto de vista la solución sea bastante fea), pero entonces se me ocurrió que estaba siendo muy injusto: si hice una versión tramposa para C (la que sólo sirve para enteros), debería hacer una versión tramposa para Java también. Así que eso hice:

public static void swap(int[] a, int i, int j) {
    if (i == j)
        return;
    int t = a[j];
    a[j] = a[i];
    a[i] = t;
}

public static void quickSort(int[] a) {
    quickSort(a, 0, a.length-1);
}

private static void quickSort(int[] a, int ini, int fin) {
    if (fin - ini < 1)
        return;
    int i = ini + 1, j = fin;
    while (i < j)
        if (a[i] > a[ini] &&
            a[j] < = a[ini])
            swap(a, i++, j--);
        else if (a[i] <= a[ini])
            i++;
        else
            j--;
    if (a[i] > a[ini])
        i--;
    swap(a, ini, i);
    quickSort(a, ini, i-1);
    quickSort(a, i+1, fin);
}

Esta versión tarda 2.26 segundos en ordenar un arreglo de un millón de elementos, lo que la hace casi tres veces más rápida que la versión tramposa de C. ¿Por qué ocurre esto? Sinceramente, no tengo idea; lo único que se me ocurre es que con 1,000,000 recursiones, el compilador Just-In-Time (JIT) de Java alcanza a optimizar algo durante la ejecución del programa que la versión en C no puede. Yo no veo otra alterantiva; pero me encantaría oír teorías.

Sólo un pequeño dato para terminar con QuickSort; hice otra versión tramposa en C para el tipo long, y ésta corre en 4.35 segundos, lo que la sigue haciendo más lenta que la de Java, pero más rápida que la de enteros (int) en C. ¿A lo mejor porque mi máquina es arquitectura AMD64? Una vez más, no tengo idea; pero sí me gustaría saber qué carajo hace la JVM para ser tan rápida.

Los enigmas no terminaron ahí, porque también implementé MergeSort en Java y C. Primero les enseño mis estructuras de datos en ambos lenguajes; estas son mis listas en Java:

public class Lista< T > implements Iterable< T > {
    protected class Nodo< T > {
	public T elemento;
	public Nodo< T > siguiente;
	public Nodo< T > anterior;
    }
    protected Nodo< T > cabeza;
    protected Nodo< T > rabo;
    public void agregaFinal(T elemento) { ... }
    public void agregaInicio(T elemento) { ... }
    ...
}

Ignoren el Iterable; es sólo para poder recorrer la lista con el foreach de Java. Las listas en C siguen el modelo estructurado en lugar del orientado objetos; por lo tanto en C lidiamos con los nodos directamente (mientras en Java siempre están ocultos al usuario):

struct lista 
{
	void* elemento;
	struct lista* siguiente;
	struct lista* anterior;
};

struct lista* lista_agrega_final  (struct lista* lista,
				   void*         elemento);
struct lista* lista_agrega_inicio (struct lista* lista,
				   void*         elemento);

Por su puesto para su práctica mis alumnos tuvieron que implementar más cosas; pero nada de eso es relevante para lo que discuto aquí. Mi implementación de MergeSort en Java (para estas listas) fue la siguiente:

private static < T extends Comparable< T >> Lista< T >
    merge(Lista< T > li, Lista< T > ld) {
    Lista< T > l = new Lista< T >();
    Lista< T >.Nodo< T > nli = li.cabeza;
    Lista< T >.Nodo< T > nld = ld.cabeza;
    while (nli != null && nld != null) {
        if (nli.elemento.compareTo(nld.elemento) < 0) {
            l.agregaFinal(nli.elemento);
            nli = nli.siguiente;
        } else {
            l.agregaFinal(nld.elemento);
            nld = nld.siguiente;
        }
    }
    while (nli != null) {
        l.agregaFinal(nli.elemento);
        nli = nli.siguiente;
    }
    while (nld != null) {
        l.agregaFinal(nld.elemento);
        nld = nld.siguiente;
    }
    return l;
}

public static < T extends Comparable< T >> Lista< T >
    mergeSort(Lista< T > l) {
    int n = l.longitud();
    if (n == 1)
        return l;
    Lista< T > li = new Lista< T >();
    Lista< T > ld = new Lista< T >();
    int i = 0;
    Iterator< T > iterador = l.iterator();
    while (i++ < n/2)
        li.agregaFinal(iterador.next());
    while (i++ <= n)
        ld.agregaFinal(iterador.next());
	
    li = mergeSort(li);
    ld = mergeSort(ld);
    return merge(li, ld);
}

La versión en C es la que sigue:

static struct lista*
merge(struct lista* li, struct lista* ld, func_compara f) 
{
	struct lista* l = NULL;
	struct lista* ii = li;
	struct lista* id = ld;

	while (ii != NULL && id != NULL) {
		if (f(ii->elemento, id->elemento) < 0) {
			l = lista_agrega_inicio(l, ii->elemento);
			ii = ii->siguiente;
		} else {
			l = lista_agrega_inicio(l, id->elemento);
			id = id->siguiente;
		}
	}
	while (ii != NULL) {
		l = lista_agrega_inicio(l, ii->elemento);
		ii = ii->siguiente;
	}
	while (id != NULL) {
		l = lista_agrega_inicio(l, id->elemento);
		id = id->siguiente;
	}

	struct lista* tmp = lista_reversa(l);
	lista_libera(l);
	return tmp;
}

struct lista*
mergesort(struct lista* l, func_compara f)
{
	int n = lista_longitud(l);
	if (n == 1) {
		struct lista* uno =
                        lista_agrega_inicio(NULL, l->elemento);
		return uno;
	}
	struct lista* li = NULL;
	struct lista* ld = NULL;
	int i = 0;
	struct lista* tmp = l;
	while (i++ < n/2) {
		li = lista_agrega_inicio(li, tmp->elemento);
		tmp = tmp->siguiente;
	}
	while (i++ < = n) {
		ld = lista_agrega_inicio(ld, tmp->elemento);
		tmp = tmp->siguiente;
	}

	tmp = lista_reversa(li);
	lista_libera(li);
	li = tmp;

	tmp = lista_reversa(ld);
	lista_libera(ld);
	ld = tmp;

	tmp = ordenamientos_mergesort(li, f);
	lista_libera(li);
	li = tmp;

	tmp = ordenamientos_mergesort(ld, f);
	lista_libera(ld);
	ld = tmp;

	tmp = merge(li, ld, f);
	lista_libera(li);
	lista_libera(ld);
	return tmp;
}

Dado que una "lista" es realmente un nodo de la lista (siguiendo el modelo utilizado por GLib), no tengo guardado en nigún lado el rabo de la lista; por eso agrego elementos al inicio, y cuando termino la volteo. Hice mis pruebas de nuevo con 1,000,000 elementos, y lo primero que me sorprendió fue que fuera tan rápido en comparación con QuickSort; yo recordaba que cuando los implementé en mi carrera, la diferencia no era tanta. A lo mejor ahora programo mejor.

La versión en Java tarda (en promedio) 2.25 segundos; la versión en C 4.8, más del doble. Esta vez ya estaba preparado y no me sorprendió tanto, y de inmediato pensé que una obvia optimización es cargar el rabo de cada lista, y así poder agregar elementos al final en tiempo constante, sin tener que preocuparme de voltearla después. Para eso creé esta estructura de datos:

struct dlista {
	struct lista* cabeza;
	struct lista* rabo;
	int longitud;
};
void dlista_agrega_final(struct dlista* dl, void* elemento);
void dlista_agrega_inicio(struct dlista* dl, void* elemento);

Pude entonces simplificar mi versión de MergeSort:

static struct dlista*
merge(struct dlista* dli, struct dlista* dld, func_compara f) 
{
	struct dlista* dl = dlista_nueva();
	struct lista* ii = dli->cabeza;
	struct lista* id = dld->cabeza;

	while (ii != NULL && id != NULL) {
		if (f(ii->elemento, id->elemento) < 0) {
			dlista_agrega_final(dl, ii->elemento);
			ii = ii->siguiente;
		} else {
			dlista_agrega_final(dl, id->elemento);
			id = id->siguiente;
		}
	}
	while (ii != NULL) {
		dlista_agrega_final(dl, ii->elemento);
		ii = ii->siguiente;
	}
	while (id != NULL) {
		dlista_agrega_final(dl, id->elemento);
		id = id->siguiente;
	}

	return dl;
}

struct dlista*
mergesort(struct dlista* dl, func_compara f)
{
	int n = dl->longitud;
	if (n == 1) {
		struct dlista* uno = dlista_nueva();
		dlista_agrega_final(uno, dl->cabeza->elemento);
		return uno;
	}
	struct dlista* dli = dlista_nueva();
	struct dlista* dld = dlista_nueva();
	int i = 0;
	struct lista* tmp = dl->cabeza;
	while (i++ < n/2) {
		dlista_agrega_final(dli, tmp->elemento);
		tmp = tmp->siguiente;
	}
	while (i++ < = n) {
		dlista_agrega_final(dld, tmp->elemento);
		tmp = tmp->siguiente;
	}

	struct dlista* tmp2;
	tmp2 = mergesort(dli, f);
	dlista_libera(dli);
	dli = tmp2;

	tmp2 = mergesort(dld, f);
	dlista_libera(dld);
	dld = tmp2;

	tmp2 = merge(dli, dld, f);
	dlista_libera(dli);
	dlista_libera(dld);
	return tmp2;
}

Esta nueva versión corre en 2.72 segundos; mucho más cerca a la versión de Java, pero todavía más lenta. Lo único extra que se me ocurrió que podía hacer era eliminar el manejo de memoria; pensando que tal vez Java es más rápido (en este caso) porque puede diferir el liberar memoria hasta después de correr el algoritmo. Así que quité las llamadas a la función dlista_libera tratando de emular como sería tener recolector de basura, y por supuesto el algoritmo corrió ahora más lento: 2.92 segundos. ¿A lo mejor con 1,000,000 de elementos consigo forzar que Linux pase memoria al swap? No tengo idea; pero la verdad lo dugo: tengo 4 Gb de memoria, y no vi que el foquito de mi disco duro se prendiera.

Todos estos resultados pueden atribuirse a errores del programador (dícese, yo), pero honestamente no creo estar haciendo nada obviamente mal. Mi teoría favorita (y de hecho la única) es que el compilador JIT de la JVM está haciendo algo de magia que el simple ensamblador optimizado de C no puede; lo cual sería una muesta feaciente e innegable de las ventajas que pueden tener los lenguajes de programación que compilan para una máquina virtual altamente optimizada. Sumado a que es mucho más sencillo programar todas estas estructuras de datos si uno no tiene que preocuparse de manejar la memoria, y además con la fuerte (y desde mi punto de vista muy bonita) tipificación de datos que ofrecen los genéricos en Java, la verdad no vería por qué alguien escogería C sobre Java para programar cosas que tengan que repetir una misma tarea cientos de miles de veces.

Por supuesto es un experimento sólo en mi máquina, y en estos días 1,000,000 de elementos me suena a que ya no es realmente tanto. Con 10,000,000 de elementos, la versión en C tardó 36.32 segundos, y la versión en Java tardó 41.98 segundos; además de que tuve que aumentarle el tamaño al heap de la máquina virtual de Java a 4 Gb. Si lo aumentaba a 2 Gb, tardaba 54.99 segundos; en ambos casos el foquito de mi disco duro se prendió. En uso de memoria, sin duda C sigue siendo mucho superior (al costo de que uno tiene que andar manejándola a mano).

De cualquier forma, es impresionante lo rápido que es Java hoy en día; cuando yo lo comencé a aprender (el siglo pasado), todavía muchísima gente se quejaba de lo lento que era. Ahora yo (que no tengo poca experiencia programando) no puedo hacer que una versión en C del mismo algoritmo le gane.

En nuestras vidas profesionales lo más probable es que mis alumnos y yo no tengamos que implementar ninguno de estos algoritmos nunca; lo más seguro es que ya existirá una versión suficientemente buena y suficientemente optimizada disponible, lo que haría medio inútil que la implementáramos de nuevo. Sin embargo, me parece importante que un computólogo las implemente aunque sea una vez en su vida, y entienda cómo funcionan y cómo podrían utilizar una versión personalizada para algún obscuro problema que se encuentren.

Y ahora tengo que trabajar en mis algoritmos para árboles binarios.

 Imprimir entrada