Habemus doctor philosophiae

Hace más de tres semanas de esto, pero había tenido tanto trabajo que no lo había comentado aquí:

Dear Mr. Peláez,

We hereby acknowledge receipt of the final version of your paper entitled

                "Convex blocking and partial orders on the plane"

                        by

                J.M. Díaz-Báñez, M.A. Heredia, C. Peláez, J.A. Sellarés, J. Urrutia, I. Ventura

to COMPUTATIONAL GEOMETRY: Theory and Applications.

¿Qué significa esto? Pues que Habemus doctor philosophiae. O en cristiano, que me doctoraré ya pronto.

Ya está, nomás no compila

Una alumna me manda su práctica: “Profesor, mi programa compila, pero truena al correr, y no sé por qué. Pero creo que ya está.”

Me recordó lo que decíamos mis cuates y yo cuando éramos estudiantes: “ya está, nomás no compila”.

Encontré los errores que tenía (nada grave), y le mandé un correo explicándoselos. Me contesta a los pocos minutos, diciéndome “creo que ahora sí ya está, profe”.

Ahora ni siquiera compilaba.

Hay cosas que no cambian en este mundo.

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.

Más sobre carreritas entre Java y C

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.

Carreritas entre Java y C

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.

Nada más que no tarden igual en responder

En diciembre de 2006 fui a un taller organizado por mi director de tesis de la maestría (y director actual en el doctorado), en Guanajuato. Escribí al respecto en su momento.

En dicho taller presentaron un problema. La historia de ese problema y cómo lo resolvimos es larga, embrollada, e involucra a cuatro países. El punto es que hoy, cinco años y cinco meses después, por fin envié el artículo correspondiente a una revista.

Ahora sólo falta esperar a ver qué nos dicen.

Trucos con \LaTeX

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 \LaTeX en español de nuevo ha hecho que descubra (o redescubra) varios trucos interesantes. Lo primero es hacer que \LaTeX hable español, por supuesto, que se logra con un simple

\usepackage[spanish]{babel}

Lo siguiente es hacer que \LaTeX 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 \LaTeX use UTF-8, sólo se necesita un simple

\usepackage[utf8]{inputenc}

Con eso al 99% de la gente que escribe \LaTeX en español debería bastarle; para los neuróticos como yo, el que sigue está interesante. Con los dos paquetes de arriba \LaTeX ya genera un documento correcto usando español, pero si uno usa \textrm{PDF}\LaTeX (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 \LaTeX con los dos paquetes que mencioné, compílenlo con \textrm{PDF}\LaTeX, y luego seleccionen una parte del documento con acentos. Debería pasarles algo así:

Texto seleccionado

Texto seleccionado

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:

Texto seleccionado con fontenc

Texto seleccionado con fontenc

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 \LaTeX 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 \LaTeX como SVG dentro de un archivo de Inkscape (que también es SVG).

Todo esto funciona muy bien, pero como el texto de \LaTeX 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:

Documento en Inkscape

Documento en Inkscape

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

Documento en Inkscape con texto

Documento en Inkscape con texto

Por supuesto, uno selecciona la fuente de Inkscape que mejor se acerque a la de \LaTeX aunque dado el cuidado que pone \LaTeX 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 \LaTeX y no de Inkscape en primer lugar). Hecho esto, uno centra el texto de Inkscape sobre el de \LaTeX, para que estén casi uno encima del otro:

Documento en Inkscape con texto centrado

Documento en Inkscape con texto centrado

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

Documento en Inkscape con texto invisible

Documento en Inkscape con texto 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:

PDF seleccionable

PDF seleccionable

Por supuesto, cuando no se esté seleccionando, el texto de Inkscape será invisible, dejando únicamente visible (e imprimible) el texto bonito de \LaTeX. 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 \LaTeX generado por textext, e inserta el código \LaTeX que generó el texto. Por ejemplo, la siguiente figura:

Figura

Figura

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

Figura seleccionable

Figura seleccionable

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.

Tlaxcala

Vinimos a Tlaxcala al Coloquio Víctor Neumann, pero esta vez sí fue de pisa y corre. Llegamos el lunes en la tarde, yo di mi plática el martes, Isabel dio la suya hoy, y ya nos vamos de regreso a la Ciudad. Tenemos demasiadas cosas que hacer como para quedarnos.

Tlaxcala está bonito, si bien chiquitito chiquitito. Me parece ya haber estado aquí, pero si así fue, habrá sido hace décadas.

Yo me alegro de regresar, tengo millones de cosas qué hacer.

Los pases

Tuve que ir a mi viejo departamento a buscar unos papeles para mi posgrado, relacionados a mi viaje el año pasado. Entre las cosas que hallé, estaban los pases de abordar de todos los vuelos que tomé el año pasado durante mis estancias de investigación.

Los pases

Los pases

Si a alguien le interesa, los vuelos fueron:

  • México – Washington
  • Washington – Madrid
  • Madrid – Roma
  • Roma – Trieste
  • Ljubljana – París (de Trieste llegamos a Bled en carro, y en carro fui de Bled a Ljubljana)
  • París – Madrid
  • Sevilla – Barcelona (de Madrid fui a Alcalá en autobús, y de Alcalá a Sevilla en tren via Madrid)
  • Barcelona – Amsterdam (puro tren cuando me moví entre Amsterdam, Delft, Den Haag y Rotterdam)
  • Amsterdam – Madrid
  • Madrid – Washington
  • Washington – Toronto
  • Toronto – Nueva York
  • Nueva York – Toronto
  • Toronto – Los Ángeles
  • Los Ángeles – México

En varios lugares me quedé sólo un par de horas (en Washington, las dos veces, que fueron las estadías más cortas). En otros me quedé varias semanas, el máximo siendo Los Ángeles durante dos meses.

Espero nunca más hacer un viaje así. Fue demasiado agotador.

Pero valió la pena.

Y por eso no me gusta trabajar

Total que en el poco más de un mes que llevo en California, me he encarrilado a trabajar con Bernardo y Silvia en su área, combinatoria, que aunque relacionada (y mucho) a la geometría computacional, es una bestia completamente distinta.

En particular, muchas veces el chiste del asunto es estar contando pendejaditas, para saber cuántos elementos de las pendejaditas existen. En la enorme mayoría de los casos (o al menos los que yo he visto y trabajado), dichas cuentas generalmente no son exactas, y entonces uno termina con una cota superior, que uno justifica con cualquier argumento que se pueda usar, y una cota inferior, que casi siempre se justifica con una familia de ejemplos que alcanzan dicha cota inferior. Cuando la cota inferior y superior coinciden, bingo, uno resolvió el bisne.

Yo en general he trabajado en las cotas inferiores, porque la computadora ayuda (y mucho) a encontrarlas, y porque la familia que justifica su existencia debe ser generable a partir de instrucciones finitas, y eso, entre otras varias formas, se resuelve mostrando un algoritmo que construye dicha familia.

Antes de que yo llegara ya teníamos una cota inferior para un subcaso del problema general, y escribiendo el programa que generaba todos los ejemplos a partir de una n determinada, descubrí que podía mejorar la cota. Lo cual es bueno; lo malo es que toda la chamba que había hecho para la cota anterior se tira a la basura, porque ahora existe una nueva cota, y entonces tengo que rehacer todo.

“Es tu culpa”, me dijo Silvia, “¿para qué encuentras una nueva cota?”

Así que me arremangué y me puse a volver a hacer todo de nuevo una vez más, hasta hace unos minutos, cuando encontré que de nuevo había mejorado la cota. Lo cual significa que de nuevo tengo que volver a hacer todo.

Chale. Me voy a mi casa, ya son las siete de la noche y no tengo la energía para volver a hacer (por tercera vez) la chamba. Me extrañaría mucho poder mejorar la cota de nuevo, pero no es imposible; no sabemos si es lo mejor que existe.

Y por eso nunca me ha gustado trabajar. Generalmente causa que uno tenga que seguir trabajando.

El código portátil

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:

RLayers en Linux, versión simple

RLayers en Linux, versión simple

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:

Windows XP en VirtualBox

Windows XP en VirtualBox

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):

RLayers en Windows XP, versión simple

RLayers en Windows XP, versión simple

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:

RLayers en Linux, versión bonita

RLayers en Linux, versión bonita

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:

RLayers en Windows XP, versión bonita

RLayers en Windows XP, versión bonita

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.

RLayers en Windows XP, de un ejecutable

RLayers en Windows XP, de un ejecutable

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.

RLayers en Windows Vista, de un ejecutable

RLayers en Windows Vista, de un ejecutable

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.

Mis niños

Como no soy (todavía) doctor, en Fields me aventaron en un cubículo enorme donde también aventaron a todos los otros no-doctores en el instituto. Lo que causó que a la entrada de la oficina estuviera esto:

El megacubo

El megacubo

Creo que si hubieran podido, hubieran aventado ahí a otros ocho estudiantes de doctorado.

La cosa que me diferenciaba a mí de todos ellos (además de ser unas catorce millones de veces más moreno), es que yo trabajé varios años después de la licenciatura antes de hacer la maestría, y luego unos meses más después de la maestría antes de hacer el doctorado. Encima, yo entré un año después a la licenciatura de lo que me tocaba (me eché la secundaria en 4 años pa’ que todo me quedara bien claro), me tocó la huelga en la UNAM, y además yo nunca fui particularmente rápido.

Todo el choro de arriba es para justificar por qué yo era el más viejo de todos los estudiantes de doctorado, y en particular porqué a los chavillos rusos les llevo probablemente más de diez años, siendo ellos medallistas de oro en la Olimpiada Internacional de Matemáticas. Con grado perfecto, como tuvieron bien a informarme.

No sé si la diferencia de edad tuviera algo que ver conque en general mis niños se apilaran de un lado de la oficina, y me dejaran casi una mitad para mí solo. Como sea, comencé a referirme a ellos como mis niños, porque de verdad me daban la impresión a veces de tener quince años.

Hoy mis niños se fueron, dejando el cubículo que compartí con ellos desoladoramente vacío. Claro que no es tan grave, porque yo me voy el sábado, pero sí fue un cambio medio radical el tener un día siete personas apiladas en el cubo, para al otro estar nada más yo solito.

Y ahora de regreso también

Hace poco más de un mes, describí cómo configurar Emacs para ligarlo a Evince, de tal forma que si compilamos un archivo \LaTeX a PDF con la opción -synctex=1, y al hacer Control-click en una parte del PDF, Emacs enmarque el archivo .tex en la línea correspondiente.

A los pocos días Omar me comentó que sí servía, y se quejó amargamente de que no funcionaba al revés: que dentro de Emacs mi código (que estaba basado en en el de aquí) no permitía saltar dentro del PDF a la región de texto correspondiente al archivo .tex.

Por supuesto, una vez más, sí se puede: estamos hablando de Emacs al fin y al cabo. Sólo que yo estaba atareadísimo terminando de escribir un artículo y las notas para otro, y los fines de semana yendo a la CN Tower y a las cataratas del Niágara, y no había tenido tiempo de revisar el código. Además, es Emacs Lisp, que la verdad (como todos los lenguajes tipo Lisp) tiendo a aborrecer ligeramente.

Por fin hace unos días revisé el código, y lo primero que hice fue corregir y mejorar algunas cosas de la primera parte, lo que hace que Evince se comunique con Emacs. El código funcionaba porque el alcance de las variables en Emacs Lisp no tiene sentido; en un lenguaje más sensato hubiera fallado miserablemente. Corregí eso y así quedó:

(require 'dbus)

(defun goto-line-and-recenter (line col)
    (goto-line line)
    (recenter line)
    (raise-frame))

(defun synctex-find-file (buf line col)
  (find-file buf)
  (goto-line-and-recenter line col))

(defun synctex-switch-to-buffer (buf line col)
  (switch-to-buffer buf)
  (goto-line-and-recenter line col))

(defun evince-backwards-sync (file linecol time)
  (let ((buf (get-file-buffer (substring file 7)))
        (line (car linecol))
        (col (cdr linecol)))
    (if (null buf)
      (synctex-find-file (substring file 7) line col)
      (synctex-switch-to-buffer buf line col))))

(dbus-register-signal
 :session nil "/org/gnome/evince/Window/0"
 "org.gnome.evince.Window" "SyncSource"
 'evince-backwards-sync)

Quedó un poquito más corto y más bonito; aunque en GNOME 3 sigue sin levantar la ventana de Emacs cuando se enmarca el documento (otra queja amarga de Omar). En otros escritorios debería levantarla: no tengo acceso a otros escritorios ahorita, y aunque lo tuviera la verdad me da mucha hueva comprobarlo.

Después comencé a ver el otro lado, que Emacs se comunique con Evince, y resulta que es similarmente sencillo, exceptuando el hecho de que Emacs Lisp es de esos lenguajes idiotas que dicen ser débilmente tipificados, lo cual significa que los tipos fallan justo cuando uno no quiere que fallen. Siendo justo, el problema realmente es que DBus es fuertemente tipificado, y entonces a veces hay que darle una manita a Emacs Lisp para que sepa cuál es el tipo que debe enviar por el cable (de ahí los feos :int32 que de repente aparecen en el código).

El código correspondiente me quedó así:

(defun get-evince-document (file)
  (dbus-call-method
   :session "org.gnome.evince.Daemon" "/org/gnome/evince/Daemon"
   "org.gnome.evince.Daemon" "FindDocument"
   (concat "file://" (replace-regexp-in-string "tex$" "pdf" file)) t))

(defun evince-forwards-sync (file line col)
  (dbus-call-method 
   :session (get-evince-document file) "/org/gnome/evince/Window/0"
   "org.gnome.evince.Window" "SyncView"
   file (list :struct :int32 line :int32 col) 0))

(defun current-line-number ()
  (1+ (count-lines 1 (point))))

(defun do-evince-forwards-sync ()
  (interactive)
  (if (not (null (buffer-file-name)))
      (if (not (buffer-modified-p))
	  (if (string-equal (substring (buffer-file-name) -4)
			    ".tex")
	      (if (file-exists-p (replace-regexp-in-string 
				  "tex$" "pdf"
				  (buffer-file-name)))
		  (evince-forwards-sync (buffer-file-name)
					(current-line-number) 1)
		(message "You need to PDFLaTeX your file."))
	    (message "You can only forward sync LaTeX files."))
	(message "You need to save your buffer first"))
    (message "Forward sync only works in file buffers.")))

Además yo en particular puse

(global-set-key (kbd "< f1 >") 'do-evince-forwards-sync)

en mi .emacs, así que ahora si le pico F1 a mi compu mientras Emacs está en un archivo .tex que esté salvado, inmediatamente manda al PDF a la página correspondiente en Evince. De nuevo, GNOME 3 no permite que una aplicación le robe el foco a otra, así que Evince no se levanta, pero debería hacerlo en otros escritorios.

Está bastante padre cómo funciona el asunto, y además funciona (me parece) de forma suficientemente robusta. Ciertamente espero usarlo mucho durante los próximos artículos que escriba.

Las cataratas

El domingo (ahora sí, el anterior), fuimos a las cataratas del Niágara.

Isa y yo en Niágara

Isa y yo en Niágara

Hay mucha agua ahí.

Fuera de broma, sí es impresionante el chorrito de agua, y como fuimos en uno de los últimos días de verano (que aquí en Canadá parece durar como quince minutos), nos tocó ver cosas como la siguiente:

El arcoiris

El arcoiris

Es medio chistoso ver el puentecito que los gringos hicieron para poder ver las cataratas desde su lado. Del lado de Canadá se ven muy padres.

Mi estancia aquí se acerca a su fin: me voy en menos de dos semanas. Como el resto de mi viaje, ha sido satisfactoriamente muy productivo, que ha sido la razón principal por la que no he escrito la bola de cosas que hecho: entre otras tareas, acabé de escribir una parte del trabajo que Fred, Víctor y yo estamos haciendo, y que Fred y yo retomamos en Holanda hace casi dos meses.

Después seguirá California. Pero por ahora, terminaré la chamba que aquí me queda, y aprovecharé lo que me queda de estar en Toronto y con mi novia.

We’re in business

Cuando solicité participar en el programa temático del Instituto Fields aquí en Toronto, no solicité apoyo económico porque cuando viajo fuera de México me apoya el CONACyT con las famosas Becas Mixtas (que aún no me dan… pero eso es otra historia). Lo que sí pedí fue “espacio de oficina”, que como todo mundo suele entender es una oficina (seguramente compartida) donde uno pueda dejar sus cosas, trabajar en paz, y cosas así.

Fields tardó semanas en contestarme nada, y con mi fecha de despegue acercándose ominosamente, les volví a escribir y ellos me contestaron que yo estaba invitado al programa, pero que no sabían si habría espacio de oficina para mí. Les dije que estaba bien, que podía trabajar en la biblioteca, y así quedó todo.

La primera semana que estuve aquí no hubo problema porque estaba en el CCCG 2011, y ya la siguiente semana fui a ver cómo estaría mi estancia aquí. Me dijeron que siempre sí habría lugar para mí, pero que la oficina estaba siendo ocupada por niños de licenciatura durante dos semanas, que si había problema que esperara ese tiempo. Yo les dije que por supuesto que no había problema, porque de entrada no había esperado tener oficina.

Intenté lo de trabajar en la bibliotea ese tiempo: de hecho en los pasillos, porque Fields tiene unas convenientes mesitas para laptops con cables de red y todo. Fue bastante incómodo, así que estuve solicitando asilo en distintas oficinas aquí (mi cuate Vincent está aquí, como también Isabel y otra gente que conozco).

Hoy por fin me dieron las llaves de mi oficina, y además con la sorpresa de que es para mí solo (al menos por hoy… es para 6 personas, así que no dudo que algún compañero de oficina llegue en algún momento). Como estoy solito se ve enorme, y además tengo una vista a la CN Tower bastante padre:

Vista desde la oficina

Vista desde la oficina

We’re in business.

Toronto

Llegué a Toronto el martes, pero de inmediato al otro día comenzó el Canadian Conference on Computational Geometry 2011, y ya no tuve tiempo de escribir aquí. Mi presentación fue el primer día, y la verdad no estoy tan contento con ella. Ser el primero entre otras cosas implicó que más de la mitad de los espectadores fueron entrando a la plática después de que ya la había empezado, y eso me sacó de onda. De cualquier forma quedó bien, me parece.

Ahora voy a empezar a trabajar en el Instituto Fields durante las próximas semanas. Espero también llegar a conocer mejor esta ciudad, dado que sólo pude estar en ella menos de 48 horas el año pasado, cuando vine a visitar a Omar (que ahora está en Boston). En el congreso estuvieron varios amigos míos, y algunos se van a quedar aquí más tiempo, lo cual me dará la oportunidad de convivir con ellos.

Y, mucho más importante que todo lo anterior, mi novia está aquí. Es bueno verla después de casi dos meses de estar separados.

El lunes me presento en el Instituto Fields, pero este fin de semana sencillamente voy a descansar: llevo para motivos prácticos del tingo al tango durante las últimas seis semanas.

Amsterdam, y Rotterdam, y Den Haag y Delft

Estoy a punto de tomar mi avión rumbo a Madrid, donde pasaré una noche y al otro día volaré a Toronto, vía Washington.

Esta semana fue de las más intensas que he tenido, hablando acerca de trabajo. Mi amigo Fred y yo demostramos básicamente lo que queríamos demostrar, y además fue interesante trabajar con él porque él está acostumbrado a hacer demostraciones de forma radicalmente distinta a como yo estoy acostumbrado: yo suelo usar argumentos geométricos, Fred suele escribir todo como ecuaciones y demostrar lo que sea que haya que demostrar resolviendo dichas ecuaciones.

Esto causó que, por primera vez en años, volviera a hacer una demostración donde tuve que probar un límite. Mi cálculo estaba bastante oxidado, pero todo salió bien. Y mi entrenamiento en geometría computacional de hecho sirvió, porque en una parte de lo que queríamos demostrar nos atoramos, y yo di un argumento geométrico que nos permitió poder conseguir la prueba.

La semana fue muy pesada, trabajando diario con Fred, y luego yo quedándome en las tardes en la universidad (TUDelft) escribiendo mi presentación para el CCCG: doy la primera plática el primer día en la primera sala, así que no puedo llegar al congreso sin mi plática preparada. También tengo que acabar un artículo en las próximas dos semanas, así que sí estaba bastante ocupado.

Como sea, un día cené con Fred en Rotterdam, aunque realmente no conocí la ciudad, el sábado fuimos a La Haya (Den Haag) a cenar comida coreana varios cuates, y el domingo Fred y Eddie me acompañaron a Amsterdam a conocer la ciudad y a visitar el museo Van Gogh. Sí, fui a las vitrinas. Y sí, es ligeramente decepcionante. Delft lo conocí un poco más, pero es tan chiquito que realmente no era muy difícil.

(De hecho todas las ciudades en los Países Bajos son muy chiquitas, pero no voy a meterme a esa discusión.)

También conocí a una banda muy buena onda en la universidad, y por encima de todo tuve la oportunidad de convivir con dos de mis amigos más queridos en Europa. Eddie se va en septiembre a una posición (potencialmente permanente) en Corea, así que no tengo idea de cuándo pueda volver a verlo, y Fred seguirá en los Países Bajos otro par de años, pero conmigo sin saber si podré viajar o no cuando acabe mi doctorado tampoco sé cuándo lo volveré a ver. Va a ocurrir que los vuelva a ver, por supuesto: sólo no sé cuándo.

No escribí en el blog porque de verdad estuvo muy intenso el trabajo, y además el poco tiempo que tuve de verdad lo utilicé para convivir con mis amigos… eso y ayudar a Fred a mudarse de Delft a Rotterdam el domingo pasado. Que fue divertido, por cierto.

Como sea, hay un par de entradas que planeo hacer, mientras espero abordar mi vuelo Amsterdam – Madrid. A ver si me da tiempo, porque creo que ya sólo tengo 10 minutos.

Los Países Bajos

El sábado llegué a Amsterdam a las 9:00 AM, después de pasar una noche increíblemente bizarra tratando de ver cómo disfrutar mi último día en Barcelona y a la vez poder llegar a las 4:25 AM al aeropuerto para poder documentar mi maleta.

Me reuní con Eddie y con Fred, dos de mis amigos más queridos que viven en Europa (Eddie desde hace casi un año, habiéndose mudado de los Estados Unidos para acá), y ya en Delft también vi a Anna, la novia de Fred y también amiga mía muy querida. Eso fue una muy agradable sorpresa, porque no sabía que ella estaría por aquí, y me alegro mucho haberla podido ver. Después de unos tragos el domingo me despedí de ella, porque regresa a Zürich donde estudia, y no tengo idea cuándo (ni dónde) la vuelva a ver.

Tengo sólo una semana aquí, porque vuelo el lunes 8 de Amsterdam para Madrid, y un día después de Madrid para Toronto vía Washington. En esta semana tengo que terminar mi presentación para el CCCG en Toronto (doy mi plática 19 horas después de aterrizar en Canadá, así que debo tenerla terminada antes de abordar el avión, supongo), tengo que escribir la última parte de un artículo que debería estar enviado a revista para el 17 de agosto, y tengo que trabajar con Fred en un problema que básicamente no hemos tocado en dos años y medio. Además, me gustaría pasar un par de días en Amsterdam, porque por bonito que esté Delft la verdad es ridículamente pequeño, y me parece que en los dos días que llevo aquí ya vi básicamente todo lo que hay que ver.

Holanda ya me gustó porque está el cielo permanentemente nublado, y está fresquito (algunos incluso dirían frío) todo el tiempo, lo cual es un agradable cambio de España. La comida apesta, sin embargo.

Es mi primera vez en Holanda, y espero aprovechar al completo esta semana: en trabajo, y en pasarla bien con mis amigos. Y ya: ese es el plan para mi última semana en Europa, y después continuará mi viaje de trabajo por Canadá y Estados Unidos.

Adéu, Barcelona

(Escrito en la madrugada del 30 de julio, a punto de abordar mi avión a Holanda, y sin Internet ni tiempo suficiente para crackear una red inalámbrica).

Me voy de Barcelona y de España, a pasar una semana en Holanda trabajando con mis amigos Fred y Eddie, en el Technische Universiteit Delft.

Voy a volver a Barcelona: es probablemente la ciudad de España más querida para mí, y siempre guardará un lugar especial en mi memoria. Siempre que tenga la oportunidad de viajar a Europa trataré de pasar por aquí aunque sea un par de días.

Voy a volver a Barcelona: el único problema es que no tengo idea de cuándo será ni bajo qué circunstancias. Es posible (aunque obviamente espero que no) que pasen años antes de que pueda regresar. Pero regresaré.

Mientras tanto, no me queda más que decir que: adéu, Barcelona.