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

Estoy escribiendo mi tesis de doctorado, y lo estoy haciendo en español porque al fin y al cabo los artículos sobre los que estará basada ya los escribí en inglés, y no le veo sentido a andarme rompiendo la cabeza de nuevo escribiendo en inglés cuando puedo hacerlo en español, y soy mucho mejor escritor en mi idioma natal.

Como sea, escribiendo en español de nuevo ha hecho que descubra (o redescubra) varios trucos interesantes. Lo primero es hacer que hable español, por supuesto, que se logra con un simple

\usepackage[spanish]{babel}

Lo siguiente es hacer que use UTF-8 para entender acentos, para así poder escribir á, y no \'a. Yo esperaría que ya todo mundo lo supiera, pero me he encontrado con varias personas que siguen usando el modo “tradicional”, que es por supuesto lento, propenso a errores, y en español hace que un documento sea ilegible. Para que use UTF-8, sólo se necesita un simple

\usepackage[utf8]{inputenc}

Con eso al 99% de la gente que escribe en español debería bastarle; para los neuróticos como yo, el que sigue está interesante. Con los dos paquetes de arriba ya genera un documento correcto usando español, pero si uno usa (como yo, que ya le perdí la fe para siempre a PostScript), en el documento resultante no están sincronizados el texto dibujado en pantalla, y el texto subyaciente. Para que me entiendan, creen un documento con los dos paquetes que mencioné, compílenlo con , y luego seleccionen una parte del documento con acentos. Debería pasarles algo así:

Eso no sólo se ve horrible; la búsqueda en el PDF deja de funcionar, y afecta también cosas como buscadores automáticos (como el de Google) que analizan los PDFs por el texto subyaciente, no por cómo se dibuje en la pantalla. Repararlo es bien sencillo:

\usepackage[T1]{fontenc}

Con este paquete, el PDF ya sincroniza el texto subyaciente con el dibujado en la pantalla, y todos los problemas que mencioné arriba se corrigen:

El siguiente truco está relacionado; para las tesis en la UNAM, la portada siempre tiene que seguir un cierto formato del que sencillamente no hay forma de escapar. La manera más sencilla (para mí) de cumplir con el requerimiento de la portada, fue hacerla en Inkscape, exportarla a PDF, e incluirla como página completa en mi documento con \includepdf, del paquete pdfpages. Ahora, todo el texto en la portada lo hice con dentro de Inkscape para que usara la misma fuente que el resto del documento, para esto usé la extensión textext de Inkscape que permite insertar la salida de como SVG dentro de un archivo de Inkscape (que también es SVG).

Todo esto funciona muy bien, pero como el texto de se inserta como SVG (dícese, líneas, curvas de Bézier, y cosas así), el PDF resultante no tiene texto subyaciente, y por lo tanto no es seleccionable, buscable, analizable, etc., porque de hecho no hay tal. Para arreglarlo es muy fácil; uno toma su documento en Inkscape:

Y le agrega texto de Inkscape, o sea, el texto que de hecho SVG sabe manejar:

Por supuesto, uno selecciona la fuente de Inkscape que mejor se acerque a la de aunque dado el cuidado que pone para dibujar texto, por mucho que se parezca la fuente de Inkscape no se verá igual (que es la razón por la cual uso texto de y no de Inkscape en primer lugar). Hecho esto, uno centra el texto de Inkscape sobre el de , para que estén casi uno encima del otro:

Y por último uno selecciona el texto de Inkscape, y lo hace invisible:

Y ya, con esto el texto subyaciente del PDF será el de Inkscape, y aunque no se verá idéntico al dibujado en el PDF, sí será seleccionable:

Por supuesto, cuando no se esté seleccionando, el texto de Inkscape será invisible, dejando únicamente visible (e imprimible) el texto bonito de . Ya que tuve mi portada lista, lo siguiente que pensé fue si valía la pena hacer las figuras de mi tesis seleccionables. Son chorroscientas, y además tendría que estar poniendo caracteres griegos la mayor parte del tiempo, y eso me dio mucha flojera. Sin embargo, hice una pequeña extensión para Inkscape que toma el texto de generado por textext, e inserta el código que generó el texto. Por ejemplo, la siguiente figura:

esto es lo que se ve cuando uno selecciona texto dentro de ella:

No es terriblemente útil, pero como ligué mi extensión en Inkscape a un atajo del teclado, es bastante fácil de hacer, y se ve mamón. Esos son todos los trucos que he aprendido (o vuelto a aprender); si encuentro otros luego los publico.

 Imprimir entrada

En Barcelona estuve trabajando con un investigador, Carlos Seara, y entre las varias cosas que hice fue el escribir un programita que utilizamos para ver ejemplos y cosas por el estilo. Desde hace años he venido juntando pequeños pedazos de código en Python que me permiten hacer programas de cosas geométricas (sólo en 2D) más o menos rápido; esos pedazos de código son lo único que queda de mi programa de geometría, geom, que lo tengo abandonado desde hace años. Como sea, el programita que hice en Barcelona está escrito en Python y, aunque funcional, ciertamente es muy sencillo:

Justo antes de salir de Toronto, Carlos me dijo que expondrá acerca de lo que trabajamos en noviembre, y que sería bueno que pudiera mostrar el programa durante su presentación. Dado que él usa Windows, me dijo que, si podía, le enviara una versión que jalara ahí.

Hay dos cosas que de verdad detesto en esta vida; una de ellas es Windows, y otra es tener que trabajar en Windows, así que no estaba muy emocionado con la idea, pero comencé a ver qué podía hacer. Yo tengo Windows Vista instalado en mi laptop (venía con la máquina), y para lo único que lo he utilizado en todo el tiempo que la he tenido es para actualizar mi teléfono Xperia Play (voy a creer que los idiotas de Sony-Ericsson no puedan hacer un programa para Linux); pero definitivamente no quería abandonar mi hermoso escritorio GNOME 3.2 para menearle cosas a Windows.

Definitivamente no: eso hubiera sido demasiado fácil.

En su lugar, hice lo que cualquier persona sensata no haría, e instalé Windows XP en una máquina virtual (afortunadamente los alumnos de la UNAM tenemos acceso a casi todas las versiones de Windows gratis). Hace unos años VMWare era la máquina virtual que todo el mundo usaba, pero desde hace algún tiempo le viene haciendo mucha competencia VirtualBox, que es de Oracle (antes Sun). VirtualBox tiene además la no despreciable ventaja de que es Software Libre.

Por supuesto VirtualBox viene con un interfaz gráfica que le permite a uno fácil y rápidamente preparar su máquina virtual dando unos cuantos botonazos del ratón. Pero, una vez más, eso sería demasiado fácil; la interfaz gráfica utiliza Qt, que yo no instalo en mis computadoras sino bajo la más absoluta emergencia. Por “suerte” VirtualBox se puede instalar sin interfaz gráfica, y configurar y echar a andar usando únicamente la línea de comandos.

Si les pudiera explicar toda la sana diversión que tuve haciéndolo. Como sea, eventualmente por fin tuve mi máquina virtual corriendo dentro de mi Linux:

Entonces ahí empezó la diversión en serio. Mi programa está escrito en Python, y utiliza básicamente Gtk+ y Cairo, con la bola de dependencias que esas dos bibliotecas se jalan. En teoría, un programa escrito en Python con Gtk+ y Cairo debería ser portátil a Windows sin muchas dificultades. En la práctica, uno tiene que estarle meneando a varias cosas en el código para que sea, bueno, portátil.

La verdad no fue tan difícil: uno básicamente instala Python para Windows, y luego instala un paquete cómodamente hecho de antemano que contiene Gtk+, sus bindings para Python, e ídem con la bola de dependencias necesarias. La cosa tiene el tino de llamarse all-in-one install. Con eso, mi aplicación ya corría en Windows (XP, al menos):

Aquí yo podría haber dicho “misión cumplida”, enviarle las instrucciones a Carlos, y dejar que sufriera lentamente instalando cosas en Windows (una experiencia miserable para cualquier persona). Pero no, decidí que iba a enviarle algo sencillo de instalar, y que de paso iba a mejorar el programita.

Así que de regreso en Linux me puse a mejorar el programita: le creé su interfaz gráfica en Glade, le puse menúes y barra de herramientas, le creé un formato para los archivos que utiliza, y pendejaditas de ese estilo. Ya a punto de acabar caí en cuenta de que probablemente correría en Español el programa, así que además le agregué soporte para gettext, para que pudiera hablar distintos idiomas:

Por supuesto, el chingado soporte para idiomas valió madre, porque en Windows gettext junto con PyGTK hace cosas muy extrañas. Al parecer hay forma de solucionarlo, pero involucran magia negra, así que me lavé las manos y forcé al programa a hablar inglés siempre. Como sea, ahora se veía bonito en Windows XP también:

Pero todo esto no eran más que manitas de gato: lo interesante era lograr que la chingadera fuera “fácilmente” instalable. Así que investigué y resultó que lo que había que hacer era utilizar un módulo de Python (en Windows) que “automágicamente” arma un ejecutable con todo lo necesario dentro para que el programa funcione, supuestamente ya sin necesidad de instalar nada más. El módulo es py2exe, y tiene una de las peores documentaciones que he visto, así que me tuve que basar en Google para saber exactamente qué tenía que hacer.

La cosa se volvió básicamente una pesadilla porque soy muy neurótico en muchas cosas: por ejemplo, el programa sigue siendo el mismo para Windows y para Linux, y el archivo de instalación (del cual se cuelga py2exe para hacer su magia) también funciona en los dos sistemas operativos. También la máquina virtual es bastante lenta (mi laptop no es muy poderosa para empezar), y eso causaba todavía más quebraderos de cabeza.

Pero por fin, después de muchas horas de dolor y sufrimiento, la cosa funcionó dentro de mi máquina virtual.

Ya teniendo todo esto hecho, lo único que faltaba era la prueba final: ver que funcionara en mi Windows Vista, el que no es virtual. Este paso es fundamental, porque el ejecutable de mi máquina virtual podía utilizar bibliotecas no incluidas por py2exe, y la única forma de comprobar esto es ejecutándolo en una máquina donde no se haya instalado Python, ni Gtk+, ni nada relacionado.

Así que cruzando los dedos reinicié a Windows, y por un milagro de esos que ocurren de vez en nunca, la maldita cosa funcionó sin problemas.

En mis planes originales estaba hacer un instalador, pero acabé realmente hasta la madre, y yo creo que Carlos no tendrá problemas en descomprimir un archivo Zip, y darle doble click a un ejecutable.

Ahora no quiero saber nada de Windows (ni de máquinas virtuales) en un buen rato.

 Imprimir entrada