El formato MIDI

Clásico: digo que no debería dejar de escribir, y prontamente decido dejar de escribir durante tres semanas. El motivo por el cual no he escrito estas semanas, es porque durante estas vacaciones (además de meditar y tomar decisiones Muy Importantes™) me he estado divirtiendo como pocas veces en mi vida, trabajando en un proyecto personal que está básicamente terminado, ya que sólo falta una pequeña pieza del rompecabezas.

Esta entrada es acerca de otra de las piezas: el formato MIDI.

Durante mis dos últimos años en el CCH Sur, llevé a la escuela una guitarra todos los días. El resultado de esto fue que puedo tocar (mal) un puñado de canciones, y algunas de ellas hasta las puedo cantar (peor todavía). Tomé un cursito de guitarra bastante malo, que además no terminé, y el resto de mi educación musical fue juntarme con los chavos que tocaban la guitarra y tratar de robarles los acordes y/o requintos.

Además de eso, y al igual que (me imagino) casi todos los estudiantes de secundaria pública en el país, tuve una flauta dulce donde alguna vez (recuerdo vagamente) llegué a tocar la Oda a la Alegría de Beethoven.

Y ya: esa es toda la “educación” musical que he tenido; no sé nada de teoría musical, soy incapaz de leer una partitura, y mientras que creo que soy capaz de dibujar o esculpir algo que al menos se parezca un poco a lo que tuviera en mi mente antes de empezar, me sentiría completamente inhabilitado para poder reproducir en ningún instrumento una tonadita que yo me inventara… y de hecho no estoy seguro de poder inventarme una tonadita.

Todo lo anterior es para explicar por qué yo, asiduo como soy a casi todo relacionado con la computadora, jamás utilicé ni me interesó mucho el formato MIDI.

Para finales de los setentas del siglo pasado la música electrónica había evolucionado de ser un curioso experimento a ser parte fundamental del acto de varios artistas, y los instrumentos electrónicos tenían la enorme ventaja de poder guardar y reproducir las actuaciones de los artistas que los utilizaban, usando una fracción minúscula del ancho de banda que usan los instrumentos analógicos.

Me explico: si yo con mi guitarra de Paracho, Michoacán, quiero grabar Wendolyne, no tengo de otra sino poner un micrófono enfrente de la misma y grabar las vibraciones del aire en formato WAVE, que es del orden (más o menos) de diez megabytes por cada minuto de audio. Claro, ahora en el siglo XXI podemos utilizar MP3, que mejora en un orden de magnitud las cosas a (más o menos) un megabyte por minuto; pero las computadoras personales de finales de los setentas no tenían suficiente procesador para poder reproducir MP3 (básicamente no existían, además), a nadie en su sano juicio se le había ocurrido inventar MP3, e incluso si hubiera habido suficiente procesador, un megabyte por minuto era una fortuna en ese entonces.

Los instrumentos electrónicos pueden superar esto por mucho, porque en lugar de guardar vibraciones del aire, sencillamente pueden guardar la información musical: en el segundo 0, se tocó la nota Do a tal volumen y velocidad; en el segundo 0.024 se tocó la nota Mi a tal volumen y velocidad; en el segundo 0.57 se tocó la nota Ra a tal volumen y velocidad (si no entienden el chiste yo no se los voy a explicar). En casi todos los instrumentos electrónicos, las notas son sencillamente cerrar un circuito, así que guardando el tiempo en que el circuito se cierra y cuando se abre de nuevo, uno puede guardar casi perfectamente la información interesante de un acto.

A finales de los setentas casi todos los fabricantes de instrumentos electrónicos tenían formatos propietarios, que hacía que los músicos se jalaran las greñas porque era muy común que les gustara usar el teclado electrónico de un fabricante, y la batería electrónica de otro; lo que ocasionaba que combinar las distintas grabaciones fuera un infierno porque utilizaban formatos distintos.

Para inicios de los ochentas los fabricantes decidieron ponerse de acuerdo, y se creó el formato MIDI, que especifica en doloroso detalle no sólo el formato digital (unos y ceros) de MIDI, sino también cosas como conectores, voltajes, y otras cosas que únicamente a músicos podrían interesarles.

A mí no me importa nada fuera de los unos y los ceros; conectores, voltajes, y cosas de músicos me tienen sin cuidado. El formato de los archivos MIDI (generalmente con extensión .mid) es lo que tuve que estudiar y programar.

Un archivo MIDI tiene un simple encabezado de 12 bytes donde se especifica el número de pistas que tendrá; es común (pero no obligatorio) que cada pista represente las notas de un instrumento distinto. Cada una de las pistas consiste en “eventos”, donde se especifica el tiempo del evento, el evento mismo, y uno o dos parámetros del mismo. En el caso de las notas, los eventos son generalmente “nota prendida” y “nota apagada”, un canal (cada pista puede tener hasta 16 canales), el número de la nota, y la duración (o velocidad) de la misma. Estos son los eventos que a mí me interesaban; y más aún, me interesaban los eventos de un único instrumento.

Todo el formato MIDI está pensado para poder utilizar el mínimo número de bits posible; y lo consigue de forma magistral: todo el Carmina Burana debe utilizar menos de un megabyte de memoria, incluyendo todos los instrumentos de la orquesta. El precio que se paga es que esta información es inútil si uno no tiene lo necesario para reproducirlo; para reproducir un archivo MIDI propiamente, uno necesita “fuentes de sonido” (sound fonts), que es básicamente los sonidos de las notas de todos los posibles instrumentos que el archivo MIDI necesita. Sin una buena fuente de sonido, cualquier archivo MIDI suena básicamente como la musiquita de Super Mario Bros.

Cuando comencé a usar la computadora a inicios de los noventas, y cuando compré mi primea SoundBlaster, todavía llegué a toparme con archivos MIDI; pero justamente como nunca me molesté en buscar fuentes de sonido, nunca le vi mucho sentido, porque todo sonaba como la musiquita de Super Mario Bros. Con una buena fuente de sonido, hacer música con MIDI debe ser bastante chido, y de hecho casi todos los músicos profesionales en la actualidad lo utilizan de alguna u otra forma.

Como sea, y volviendo al formato de los archivos MIDI, cuando digo que los eventos tienen un “tiempo”, este tiempo no está representado en segundos, ni milisegundos, ni microsegundos. De hecho, olvídense de segundos; el tiempo está representado en… ¿saben qué? Aún ahora no sé en qué chingados está representado el tiempo; tiene que ver con pulsaciones por segundo, pulsos por cuartos de nota, submarcos, pulsos por minutos, y no sé qué madres más. No me interesa en lo más mínimo; pero lo necesitaba porque necesitaba el tiempo preciso en que cada nota se prendía y se apagaba. Y para acabarla de amolar, el tiempo no es absoluto; es relativo a la nota anterior: es un formato acumulativo, donde el tiempo de cada nota es una delta que se le suma al tiempo de la nota anterior.

Después de muchos quebraderos de cabeza, conseguí la fórmula que me permitía convertir el tiempo de cada nota (después de obtenerlo a partir del tiempo de la nota anterior y de la delta) a milisegundos, y me puse a sacar los tiempos de las notas del instrumento (o sea la pista) que me interesaba. Y por supuesto todo se desincronizaba; pero esto ocurría únicamente de vez en cuando, y únicamente en algunas canciones.

Estuve días golpeándome la cabeza contra un muro hasta que por fin encontré el problema: estaba calculando el tiempo utilizando las notas de la pista que me interesaba; y hay que usar todas las pistas. En otras palabras, si hay una pausa en las notas de la guitarra, pero en esa pausa la batería sí reproduce notas, la siguiente delta de la guitarra no se aplica a la última nota de la guitarra, sino a la última nota de cualquier instrumento (en este ejemplo, la batería). Lo cual tiene sentido cuando uno ve lo ridículamente pequeño que es un archivo MIDI; no hay problema en preprocesarlo todo de antemano para poder tener la información de todas las pistas disponible.

Y aún así, todavía tengo unas cuantas canciones donde de cualquier forma se me desincronizan las cosas. No tengo idea de qué pueda estar pasando; como el formato MIDI acepta cualquier cantidad de madres (por ejemplo, las letras de las canciones pueden incluirse en el archivo, para hacer cosas como karaokes), no sé si a algunas de ellas les esté tomando en cuenta el tiempo cuando no debería, o qué carajo: pero como sólo ocurre con dos o tres canciones, decidí esas arreglarlas a pie, y olvidarme del asunto para siempre. Con lo que tenía era más que suficiente para hacer lo que quería hacer, y de hecho ya lo hice; supongo que sí descubriera cuál era el problema estaría chido, pero a estas alturas ya es un extra. Lo que quería conseguir ya lo conseguí.

Para conseguirlo, escribí un programa que convertía la información de un archivo MIDI a un formato que me inventé donde dice en que nanosegundo ocurre que se prende o apaga una nota; primero lo hice en Python, pero he estado convirtiendo todo a Vala, porque es 10 veces más rapido, aunque como los archivos son todos chiquititos realemente no sería tan grave dejarlo en Python. También utilicé un programa que convertía el MIDI a un formato CSV (tipo hoja de cálculo), pero como no me salían las cosas terminé escribiendo yo uno igual, porque no me quedaba claro si había un error en el programa o cómo interpretaba yo las cosas (el error era mío, pero pues ya tengo mi programa que lee MIDIs directamente).

El medio entender el formato MIDI fue sólo una de las partes del proyecto en el que estuve trabajando; tengo todavía la duda de porqué un par de canciones se me desincronizan, pero fuera de eso creo que tengo dominada esta parte. Y de hecho, medio entender el formato MIDI me resultó de utilidad en otra de las partes del proyecto que encontré más adelante; pero de eso escribiré luego.

Gimme power

Mi teléfono celular tiene el mismo problema que tienen muchos dispositivos modernos: la batería le dura alrededor de 24 horas en circunstancias normales.

Ahorita no estoy en circunstancias normales; estoy utilizando la aplicación que guarda mis coordenadas para después poder ponerle información GPS a las fotos que estoy tomando.

Mi batería entonces dura como la mitad de lo normal; ayer pude conectarlo en el restaurante donde comimos, si no hubiera muerto. Mi teléfono tiene un modo de ahorro de energía, pero entonces detiene casi todas las aplicaciones para ahorrar energía cuando la pantalla se apaga, lo que incluye mi rastreador GPS.

Sólo hasta hoy descubrí que uno puede seleccionar aplicaciones que el modo de ahorro de energía no detendrá. Mi teléfono dice ahora que le va a durar dos días la batería; no le creo nada, pero si aguanta el día me daré por bien servido.

Los datos

Voy a estar una semana en el gabacho en total; como ya me he acostumbrado a tener datos en mi teléfono celular todo el tiempo, decidí que no quería pasar esta semana como ciego dando tumbos en la oscuridad electrónica.

Eso me parece que fue razonable de mi parte; lo que fue increíblemente estúpido, fue creer que podía confiar en Telcel para solucionar mi problema.

Me metí a la página de Telcel, y contraté 250 megabytes para usar en el gabacho. Fue relativamente sencillo, y el cobro de hecho se realizará hasta quién sabe cuándo, en mi estado de cuenta mensual. El problema fue que llegué a gabacholandia, y por supuesto no funcionó.

Les llamé para reclamarles, y después de probar varias cosas, los muy inútiles me dijeron que no podían hacer nada. Estoy usando un teléfono que no es de Telcel, porque cuando me robaron mi celular en diciembre, compré uno independientemente, justamente porque me desesperó la inutilidad de la gente de Telcel para poder sencillamente venderme un teléfono al que le pudiera poner mi chip.

Por supuesto ellos se agarraron de esto para decir que no podían hacer nada. Me dio mucho coraje, porque cuando me hartaron en diciembre con su incapacidad para simplemente venderme un teléfono, me aseguraron que no había problema conque yo comprara un teléfono por afuera y le pusiera mi chip. Y significa que lo que gasté por mis 250 megabytes básicamente se tira a la basura.

Perdí unas dos horas de mi vida ya aquí en Chicago viendo qué podía hacer al respecto, hasta que al final me resigné a haber perdido mi dinero, y salí a al menos a conocer la ciudad, aunque fuera como ciego dando tumbos en la oscuridad electrónica.

Y entonces vi un local de T Mobile.

Me metí y pregunté si podía tener 7 días de datos. “Claro”, me dijeron (sólo que en inglés). Quince minutos después, salí del local con datos en mi celular, un número básicamente ilimitado de megabytes al día (tendría que pasármela todo el tiempo viendo videos en YouTube para acabármelos), y a la mitad del precio de Telcel.

Lo que es mejor; mi teléfono (que también compré independientemente de Telcel) tiene dos ranuras para tarjetas SIM, así que puedo recibir llamadas y mandar mensajes por mi número de México, mientras recibo datos con mi número T Mobile (que sólo usaré para ello), todo al mismo tiempo.

Así que sí perdí dinero con Telcel; pero es la última vez en la vida que lo haré. Si vienen al gabacho, ni se molesten en tratar de comprar los planes de Telcel; es probable que no funcione, y es demasiado caro para una cantidad de megabytes tan pequeña. Compren una tarjeta SIM; si tienen un teléfono con dos ranuras, tienen lo mejor de los dos mundos; si tienen sólo una, usen el SIM gringo para correo, Google Maps, redes sociales, etc., y sólo pongan el SIM de Telcel cuando quieran revisar sus mensajes o correo de voz, o hacer llamadas.

Estoy considerando seriamente dejar a Telcel por otra compañía celular; se han portado de manera criminalmente incompetente las últimas veces que he tenido que lidiar con ellos.

Pero al menos tengo datos aquí, y funciona muy bien, aunque tuve que perder dinero para aprender mi lección de que no debo utilizar los servicios que provee Telcel, porque de verdad son unos inútiles.

Formas PDF

En la academia, al parecer, hay que llenar catorce millones de formas cada quince minutos, más o menos. Formas para plazas, formas para becas, formas para estímulos, formas para calificaciones, formas para viajes, formas para viáticos, formas para que nos paguen viáticos ya gastados, formas para votos, formas para pedir otras formas que entonces hay que llenar para poder hacernos acreedores a nuevas formas…

La única vez que he trabajado (fuera de la academia) en el sector público, cuando estuve en el IFE (que ya ni siquiera existe), no tuve que llenar tantas formas; pero estaba por obra determinada, así que no sé cómo sea si uno tiene un puesto “fijo”. En la industria privada jamás tuve que hacer nada por el estilo, pero tampoco creo que se pueda considerar “fijo” lo que hacía en ese entonces.

Como sea, hasta hace no mucho uno tenía que ir por sus formas a algún lado, pedirlas por favor, y llenarlas con pluma o máquina de escribir. Siempre odié eso, porque involucraba escribir a mano, lo cual nunca se me ha dado mucho (mi caligrafía de caquitas de mosca embarradas en el papel no ha tenido el éxito que yo hubiera esperado), así que fue con alegría cuando descubrí que por fin todo mundo empezó a poner formas en línea.

Al inicio muchas veces la forma era el escaneo de la forma original, si bien le iba a uno como un PDF, si no como un vil JPG. A veces daban las formas en el formato .doc de Microsoft Office, pero creo que ya casi nadie hace eso. Desde hace algunos años esto se ha ido estandarizando en utilizar PDFs editables, o formas PDF. Esto para mí es la gloria, porque entonces ya no tengo que hacer ningún truco sucio; sólo lleno la forma, salvo el documento PDF, y soy feliz.

Cuando no es editable el PDF, soy bastante menos feliz. Lo que he hecho desde hace algunos años, es recrear la forma en SVG con Inkscape, y entonces llenarla con la herramienta de texto que tiene. En general funciona bastante bien, y tengo ya una biblioteca considerablemente amplia de formitas en SVG que sólo abro para editar de vez en cuando. Dado que SVG es XML, en algunos casos simplemente pongo texto como un marcador de posición (por ejemplo, NOMBRE), y hago un script que reemplaza esa cadena por la que realmente quiera usar. Jala muy bien; el único problema es que a veces es un desmadre recrear la forma completa en SVG, pero incluso esto es evitable si la forma no es una imagen, sino que la información vectorial de la misma viene en el PDF: para esos casos sencillamente utilizo pdf2svg, o abro el PDF directamente con Inkscape.

El otro problema es cuando la forma son múltiples páginas. SVG no tiene realmente una manera de modelar documentos con múltiples páginas, entonces tengo que crear una serie de documentos (forma1.svg, forma2.svg, etc.), y hacer un Makefile o algo así para compilarlos a un único PDF. Que es la situación en la que me encuentro ahorita.

Por supuesto, clavado como soy, ya ando pensando en cómo mejorar mi flujo de trabajo. Lo obvio por supuesto sería escribir un programa que recibiera las entradas de la forma (o las leyera de una base de datos), y generara los SVG, o incluso el PDF ya directamente. Lo único que me detiene para hacer esto (además del hecho de que tengo que terminar de llenar mis estúpidas formas), es que no sé cómo obtener la dimensión que ocupa un texto determinado en SVG, y que aún teniendo esto tendría que implementar un algoritmo para partir líneas muy largas en párrafos, de preferencia tratando de que las distintas líneas todas tengan más o menos el mismo ancho. Este algoritmo ya existe, por supuesto; es el que Knuth y un estudiante suyo de doctorado diseñaron e implementaron para \LaTeX, pero tengo entendido que es suficientemente complejo como para que lo implemente yo durante un fin de semana.

Así que por mientras sigo peleándome con mis SVG separados.

La presentación

Una vez oí a alguien comparar el hacer un examen de grado de la UNAM con participar en un encuentro de lucha libre, en el sentido de que el resultado está decidido de antemano, pero eso no evita que le vayan a poner a uno una santa madriza.

Para prepararme para dicha madriza, me puse a hacer mi presentación casi desde que me dieron la fecha del examen.

Yo me considero bastante bueno dando presentaciones, y a lo largo de mi vida académica he utilizado varios programas para hacerlas (aunque obviamente jamás Power Point, dado que no uso Windows). Para la presentación de mi examen de doctorado quise hacer algo nuevo, así que primero intenté utilizar PinPoint.

El programa está simpático, pero me resultó inútil: no acepta fórmulas matemáticas, y a pesar de que tiene transiciones muy bonitas, éstas sólo funcionan entre transparencias, no objetos de las mismas. Además, no puede cargar nativamente SVGs, y como que más bien está pensado para presentaciones “corporativas” (dícese, texto con imágenes lindas de fondo). Ni siquiera encontré cómo poner dos figuras en la misma transparencia (que no involucrara combinarlas en una misma imagen de fondo).

Después intenté JessyInk (viene integrado con Inkscape). Yo soy fan rabioso de Inkscape; lo uso para todo, y aunque la mayor parte de las figuras de mi tesis son resultado de programas que yo escribí que escupían SVG, casi todas fueron retocadas con Inkscape, en muchos casos al menos para agregarle etiquetas. Sin embargo, de nuevo me decepcionó lo que hace JessyInk; las presentaciones que crea son muy apantalladoras, pero además de marear al espectador (pueden ver un ejemplo aquí), no vi nada que me ayudara a mí en lo que quería hacer: poder manipular objetos individuales dentro de cada transparencia.

Mi tesis consiste en problemas de geometría computacional que lidian con cositos dando de vueltas en el plano. Lo que yo quería era que dichos giros pudiera implementarlos dentro de la presentación misma, girando realmente los objetos en ella, en logar de girar a pie las imágenes de cada transparencia.

Un último intento fue utilizar Impress, el paquete de presentaciones de LibreOffice; pero nada más estar baboseando cinco minutos con él fueron suficientes para que me percatara de que no iba a poder usarlo para lo que quería.

Así que como durante dos horas estuve coqueteando seriamente con la idea de yo escribir un programa, donde las presentaciones fueran programas mismos que cargaran los objetos de SVG, los interpretaran como códigos de dibujo para Cairo, y yo pudiera animar cada parte de ellos de forma individual. Suena un proyecto interesante, y en Vala incluso podría salir relativamente rápido; pero ciertamente no hubiera acabado a tiempo para mi examen.

Así que me puse a girar las imágenes a pie antes de ponerlas en transparencias. Estuve a punto de usar sólo un montón de SVGs que compilara a un PDF usando un Makefile, pero al final decidí utilizar el viejo y confiable Beamer, a pesar de que no lo había usado en años.

La presentación me quedó padre, me parece; el único problema fue que la hice como si no tuviera restricciones de tiempo para exponerla, así que como dos terceras partes de la misma las di medio corriendo.

Pero eso será una historia para otro día.

La vida digital

Ayer mi mamá me pidió que la acompañara a comprar una tele en Best Buy, porque así es la vida.

De pura chiripa encontramos una tele Samsung LED FullHD de 39″ en 5,999.99 pesos, porque estaba de promoción, así que le dije que se llevara esa, porque sí estaba muy barata. Ya pagando, vi que podía pagarse a 12 meses sin intereses con tarjetas de crédito Banamex; yo acabo de sacar la mía porque llevaban meses jode y jode los de Banamex con que sacara una, y porque con ella compré mi nuevo celular, así que le dije a mi mamá que me dejara pagarla con mi tarjeta de crédito y que luego ella me pagara las mensualidades.

Por supuesto mi tarjeta no pasó, porque con ella pagué el hotel de Oaxaca durante el congreso de la semana pasada y tengo como tres pesos de crédito; pero entonces se me ocurrió una idea: saqué mi celular, abrí mi aplicación de Banamex, y pagué mi tarjeta de crédito ahí mismo en la tienda, todavía enfrente de la caja donde la acababan de rebotar. Acto seguido, compré la tele de mi mamá con mi tarjeta de crédito, que ahora sí pasó.

Es chistoso, pero fue a la vez sorprendente y natural que pudiera hacer eso. Sorprendente porque nunca lo había hecho, y si hace algunos años me hubieran dicho que podría hacer algo así lo hubiera puesto altamente en duda… comenzando por el hecho de que yo tendría una tarjeta de crédito. Natural porque, vamos, es el mundo en el que ahora vivimos.

Ahora si tan solo pudiera comprar procesadores en Amazon México…

5 veces más líneas, 400 veces más rápido

Xochitl está a veces bajo ataque. En general son ataques idiotas que tratan de entrar por SSH usando combinaciones de usuario/clave del tipo “root/root” o “user1/user1″; evidentemente eso casi nunca funciona, y además esos ataques son automáticamente detenidos después de tres intentos fallidos con denyhosts.

Esos ataques no me dan problemas; me dan problemas los ataques dirigidos específicamente contra mi blog y/o galería en línea. No porque alguna vez hayan logrado nada (los mantengo actualizados); el problema es que a veces generan una cantidad tal de solicitudes que Apache comienza a sobrecargar MySQL, la base de datos queda trabada, y Apache entonces se queda atorado sirviendo páginas. Si los atacantes solicitan muchísimas solicitudes a la vez, esto causa que MySQL quede atorado con cientos de consultas en su cola, y por lo tanto que Apache quede atorado con cientos (o miles) de páginas que quieren ser servidas.

Como Apache trata de no tirar conexiones, y cada una de ellas utiliza procesador, esto hace que el CPU de Xochitl de repente se encuentre utilizado al 117%. Aquí es donde debo mencionar que Xochitl es una pobre Pentium 4 a 2.40 Ghz; es posible (y de hecho probable) que la mayoría de los teléfonos celulares inteligentes que han salido este año sean más rápidos (y tengan más memoria) que Xochitl.

De todo lo anterior no es esta entrada.

Esta entrada es acerca de una situación que encontré mientras buscaba qué poder hacer para aliviar a la pobre de Xochitl. La más sencilla es ver qué IPs están solicitando más conexiones HTTP, y agregarlas a /etc/hosts.deny (teniendo cuidado de no negarme acceso a mí y mis máquinas, o a los robots rastreros de Google). Suele funcionar; sobre todo considerando que estos “ataques” (la verdad ya no sé si son ataques o sólo lectores ligeramente stalkeadores de mi blog/álbum) no ocurren muy seguido.

Así que hice un programita que leyera los logs (o bitácora, si quisiera usar español correcto) de acceso de Apache, sacara las IPs, y contara cuántas veces aparece cada una. Como lo primero que aparece en cada línea es la IP solicitante seguida de un espacio, con el siguiente comando obtengo todas las IPs que solicitan páginas a Apache:

cat /var/log/apache2/access_log | cut -d " " -f 1

Hasta ahí vamos bien; ahora, ¿cómo saco de ahí cuántas veces se repite una IP?, porque sabiendo eso ya puedo saber cuáles IP solicitan un número ridículo de conexiones. Siendo, como soy, programador, escribí un programita que hiciera esto por mí. Lo escribí en Python, porque lo quería rápido, y esto me salió:

#!/usr/bin/env python

import sys

if __name__ == '__main__':
    ips = {}
    for line in sys.stdin.readlines():
        line = line.strip()
        if line in ips.keys():
            ips[line] = ips[line] + 1
        else:
            ips[line] = 1
    for ip in ips.keys():
        print('%d: %s' % (ips[ip], ip))

Esas son 14 líneas de Python, incluyendo el shebang y dos líneas en blanco. El programa lee línea a línea la entrada estándar, y usa un hash table para ir contando cada aparición de una IP.

Muy contento con mi programa lo corrí… y el maldito programa corrió, y corrió, y corrió, y siguió corriendo. Al minuto lo detuve, incrédulo de que pudiera ser tan endiabladamente lento. Lo revisé, lo puse a imprimir resultados intermedios, y el resultado era el mismo: es lentísimo.

Estúpido Python.

Me subí las mangas y lo reescribí en C, usando glib porque no me iba a a poner a escribir mi propio hash table (been there, done that). Esto me salió:

#include < stdio.h >
#include < string.h >
#include < glib.h >

typedef struct _integer integer;

struct _integer {
        int n;
};

static integer*
integer_new(int n) 
{
        integer* i = g_new(integer, 1);
        i->n = n;
        return i;
}

static char*
read_line(FILE* file)
{
        char line[4096];
        int i = 0;
        line[i] = (char)0;
        int c;
        while (TRUE) {
                c = fgetc(file);
                if (c == EOF || c == NEW_LINE)
                        return strdup(line);
                line[i++] = c;
                line[i] = char(0);
        }
        return strdup(line);
}

void
print_key_value(char* key, integer* value, gpointer user_data)
{
        printf("%d: %sn", value->n, key);
}

int
main(int argc, char* argv[])
{
        GHashTable* h;
        h = g_hash_table_new_full(g_str_hash, g_str_equal, g_free, g_free);
        do {
                char* line = read_line(stdin);
                if (!strcmp(line, "")) {
                        free(line);
                        continue;
                }
                char* key;
                integer* value;
                if (g_hash_table_lookup_extended(h, line, &key, &value)) {
                        value->n++;
                } else {
                        value = integer_new(1);
                        g_hash_table_insert(h, line, value);
                }
        } while (!feof(stdin));
        g_hash_table_foreach(h, print_key_value, NULL);
        g_hash_table_destroy(h);
        return 0;
}

Esas son 65 líneas en C, incluyendo la definición medio redundante de una estructura integer porque no quise usar las macros GINT_TO_POINTER y GPOINTER_TO_INT. No es elegante.

Ya que tuve mis dos versiones, según yo, equivalentes, las corrí ambas. La salida que producen es idéntica, así que me parece que sí son equivalentes. La versión en Python tarda más o menos 1 minuto 58 segundos (más/menos dos segundos, en todas las ocasiones en que lo corrí). La versión en C tarda 0.285 segundos, consistentemente debajo de 0.290. Esto para una bitácora de 95,080 líneas, de 12 Megabytes de tamaño.

La versión en C es unas 5 veces más larga en líneas que la de Python (de hecho 4.333, pero no importa), además de que las líneas tienen más caracteres; y sin embargo tarda (en tiempo de ejecución) del orden de 400 veces menos.

Ahí está el código si alguien quiere tratar de mejorar el resultado en Python. Yo estoy sumamente decepcionado; creí que las hash tables de Python estaban decentemente optimizadas: estoy usando cadenas como llaves al fin y al cabo. Y lo peor es que la versión en C ni siquiera me tomó mucho más tiempo en escribir.

Actualización: Gracias a Omar, ya vi que estaba cometiendo un errosote al buscar la llave en la hash table de Python; no tenía porqué buscarla en .keys() cuando puedo hacerlo directamente en la tabla. Con la sugerencia de Omar, el código Python es solamente el doble de lento que el código C. Lo que de hecho tiene sentido.

Dónde estás, que no te veo

En mi departamento tengo más computadoras de las que cualquier adulto viviendo solo debería tener. Más aún si cuento cosas como mi PlayStation 3 o mi teléfono celular, o incluso mi N800, por más que no lo haya usado en los últimos dos o tres años.

Como sea, casi todas las computadoras se conectan a mi red local vía inalámbrica, y todas lo hacen a través de DHCP. Todas por lo tanto suelen tener direcciones de IP dinámicas (excepto Atom, mi servidorcito con procesador Atom; como redirijo a él las conexiones SSH de mi módem DSL, necesito que tenga una dirección estática), y después de un rato es un desmadre estar viendo cuál computadora tiene qué dirección IP.

Para solucionar esto utilizo Avahi, una implementación de zeroconf para Linux, lo que causa que cada computadora con Linux que tengo anuncie su presencia en la red local. No importa qué dirección IP tenga Centurion, mi máquina de escritorio, dentro de mi LAN puedo accederla con la dirección centurion.local (desde una máquina que use Linux y Avahi). Como hay un navegador de zeroconf para Android, incluso lo puedo usar desde mi teléfono, aunque tengo que abrir el navegador, ver qué dirección tiene centurion.local y ya usarla.

Como sea; ayer salí un rato de mi departamento y al regresar vi que se había ido la luz, ya que Atom estaba apagado. Prendí de nuevo el servidorcito y mi máquina de escritorio (la había dejado suspendida), y traté de conectarme de nuevo a atom.local. No pude, así que supuse que Atom no había iniciado correctamente. Agarré mi teclado USB y lo llevé al servidorcito, usando mi televisión de 46″ como monitor (como Atom está en el mismo mueble que la tele, lo tengo conectado a ella todo el tiempo por VGA). Cuando entré al servidorcito, vi que, aparentemente, todo estaba bien. Traté de conectarme de Atom a Centurion, y tampoco lo encontró.

El protocolo de zeroconf funciona de tal forma que, bueno, necesita cero configuración. Lo dice ahí, en su nombre. Que algo falle con Avahi es bastante raro; de hecho no ha habido nuevas versiones en años; sencillamente funciona.

Regresé a Centurion, y me puse a investigar qué podía pasar. Ambas computadoras podían accesar Internet, sólo no la una a la otra. Dado que Avahi es un protocolo distribuido (no necesita un servidor), no pensé que fuera mi módem DSL, pero ya sin muchas otras opciones me metí al mismo para ver si todo jalaba bien con él; a lo mejor algo extraño había pasado con el servidor DHCP, o quién sabe.

Y entonces en el navegador apareció la página de autenticación del módem DSL. Y resultó que no era mi módem.

Cuando volvía a prender Centurion después de que regresó la luz, en lugar de conectarse a mi módem DSL, se conectó al módem DSL de un vecino, que todavía en esta época no ha aprendido que hay que ponerle clave. Conecté Centurion a mi módem DSL, y por supuesto se pudieron encontrar él y Atom. También borré el módem DSL de mi vecino de la lista de Access Points a los cuales Centurion trata de conectarse (no tengo idea de cómo llegó ahí en primer lugar), así que espero este particular problema no vuelva a repetirse.

Photo Locator

Cuando regresé de Guadalajara de ver a mi novia, traje conmigo cerca de 200 fotografías, y a casi todas ellas les pude sincronizar la información de localización GPS que saqué usando GPS Logger; platiqué de eso hace unas semanas. Cuando mi novia vino a verme durante semana santa, su despampanante belleza causó que me distrajera lo suficiente como para olvidárseme prender GPS Logger todos los días.

A ver, no se distraigan ustedes...

A ver, no se distraigan ustedes…

Esto, aunado con el hecho de que todas mis fotos antes de mi viaje a Guadalajara no tienen etiquetas GPS, y que tomé muy pocas fotos cuando Mina vino en las vacaciones, ha resultado en que el mapa de mis fotos en mi galería en línea se vea sí:

Mapa de la galería

Mapa de la galería

Según ese mapa, he tomado más fotos en Guadalajara que en la Ciudad de México. Casi diez veces más fotos. Y cero en cualquier otro país.

No me malentiendan; no tengo nada contra Guadalajara. Está bonito por allá. Pero el hecho de que la información de geolocalización de mi galería en línea refleje (erróneamente) que he tomado más fotos allá que aquí me tiene… incómodo, por decir lo menos. Y además, no refleja nada de los fabulosos viajes que he realizado por Europa y el resto de Norteamérica.

No hay manera de que automáticamente haga que las fotos sin información GPS adquieran dicha información. Bueno; técnicamente podría hacer un script que les pusiera coordenadas aleatorias a todas mis fotos, pero eso no serviría de mucho para lo que quiero: que el mapa de allá arriba refleje mis andanzas por todo el mundo. La única forma de conseguir eso es ir foto por foto tratando de recordar dónde estaba cuando la tomé.

El problema no es acordarme; tengo una extraordinaria memoria cuando se me pega la gana, y suelo recordar con bastante precisión dónde estaba cuando tomé una foto. El problema es la interfaz para asignarles coordenadas a las fotos; el plugin de Gallery 3 que genera el mapa de allá arriba también me permite ponerle coordenadas a cada foto, pero eso es usando dos cajitas de texto.

Editor de coordenadas

Editor de coordenadas

Esto significa que me tengo que ir a Google Maps (o algún otro programa que me permita ver las coordenadas, en latitud y longitud, de un lugar), agarrar esos numeritos, y pegarlos cada uno en su lugar en las cajitas de texto. Lo intenté hacer, y como a la tercera foto ya quería aventarme a las vías del metro para terminar con mi sufrimiento. Así que hice lo que cualquier programador que se respete haría; escribí un programa para ponerles coordenadas a mis fotos viejas.

Photo Locator

Photo Locator

Realmente fue trivial; tomé la mitad del código de otro de mis programas (Quick Photo Editor), le metí un actor con un ChamplainView (de la biblioteca libchamplain)… y básicamente ya. El actor hace todo, incluyendo bajar los mapas de OpenStreetMap, y me da las coordenadas de donde yo quiera en el planeta; es de verdad una biblioteca espectacularmente fácil de usar. De hecho es más rápido para mí ponerles coordenadas a mis fotografías que escribirles el título.

El programa es para mis fotos viejas; espero seguir usando GPS Logger para las futuras (siempre y cuando la despampanante belleza de mi novia no me siga distrayendo). Pero tengo más de 9,000 fotos, así que tardaré en ponerles coordenadas a todas; más en lugares como Europa, donde tendré que meterme al Street View de Google Maps para medio ubicarme dónde estaba cuando tomé la foto. Aunque ya decidí no angustiarme tanto; si no recuerdo rápidamente el lugar exacto donde tomé una foto, me voy a conformar con atinarle a la ciudad en el peor de los casos. Y como es complicado modificar la base de datos de coordenadas con fotos que ya subí, probablemente tendré que subirlas todas de nuevo cuando acabe.

Pero al menos mi galería en línea ya no dirá en su mapa que he tomado más fotos en Guadalajara que en la Ciudad de México.

Etiquetas GPS

Para mi viaje a Guadalajara instalé GPS Logger en mi teléfono Android. Antes de tener teléfono mamón, tenía mi Nokia N800, al cual le compré un GPS bluetooth, y con el cual podía ir grabando mi posición GPS cada segundo, para después transportar esa información a mis fotos.

Nunca funcionó muy bien que digamos; para empezar, el N800 no podía estar recabando mi posición GPS todo el tiempo vía bluetooth, por la sencilla razón de que la batería se moría a las doce horas, si uno tenía suerte. Además, mi GPS bluetooth sólo era eso, GPS; no soportaba AGPS (Assisted GPS), que se ayuda de las torres de celular para aproximar la posición de uno cuando no consigue engancharse a los satélites GPS (que pasa más comúnmente de lo que uno pensaría). Pero además se volvía todo una cosa muy incómoda, cargando el N800, el GPS, la cámara, y además con la angustia de que la batería se iba a morir en cualquier momento.

La única vez que intenté usarlo así fue cuando fui a ver a mi cuate Eddie en San Francisco en el 2009, y además de que pasó todo lo que acabo de describir (se murió la batería, el GPS no se conectaba a los satélites, fue un desmadre estar cargando tantos electrónicos), cuando regresé a México y traté de sincronizar la información que el N800 había estado guardando en mis fotos, resultó que no podía porque F-Spot había cambiado las horas de las mismas. Para que esto funcione bien, el reloj del GPS y el de la cámara debe estar casi perfectamente sincronizado, obviamente.

Creo que por ahí tengo la información GPS de ese viaje a San Francisco, pero la verdad ya ni intenté ver si podía ponérsela a mis fotos. Mi N800 ahora está arrumbado por ahí, y hace años que ni siquiera lo prendo.

Con mi teléfono Android todo ya es mucho más sencillo: tiene el GPS integrado, utiliza AGPS, y además la batería es bastante mejor que el del N800, así que como dije instalé GPS Logger y estuve guardando mi ubicación todo el tiempo que tomé fotos durante mi estadía en la capital jalisciense. Hoy que ya acabé la chamba que se me había acumulado por estar tres días casi sin ni siquera consultar mi correo electrónico, investigué cómo podía sincronizar dicha información en el par de centenas de fotos que tomé durante mi viaje.

Fue bastante sencillo: hay un programita llamado GPS Correlate que lo hace automágicamente, incluso con ventanitas y así. Igual y reescribo el programa, porque la verdad sí se siente medio abandonado; pero funcionó sin ningún problema. Ya que mis fotos tenían la información de ubicación dentro de ellas, vi qué podía hacer para que mi galería en línea la utilizase. También fue sencillo; sólo instalé el módulo EXIF GPS de Gallery3, y con esto aparece un mapita de Google Maps en cada uno de mis álbumes donde haya información de localización:

Mapa de álbum

Mapa de álbum

Y por supuesto, cada foto con información de localización tiene un mapita de Google Maps individual:

Mapa de foto

Mapa de foto

Está bastante chido; vaya a ser que se me olvide dónde tomé una foto. Me da coraje no haberlo hecho antes; tengo mi teléfono mamón desde junio del 2011, y en mi megaviaje de seis meses me hubiera sido bastante útil. Pero bueno, así se aprende en esta vida. Mi Android soporta un día entero de estar usando GPS Logger, pero apenas; termina con la batería debajo del 5%. Pero ya dentro de poco me tocará renovarlo, y espero que mi próximo teléfono tenga mucho mejor batería que el de ahora (y que jale más rápido, porque ya lo siento muy lento… y que tenga un buen de memoria interna, porque la que tengo es una grosería).

Así que a partir de ahora mis fotos tendrán la información de dónde las tomé, a menos que algo le pase a mi celular.

Con la cámara de mi nueva laptop

Después de que me hicieron notar, de la manera más directa posible, que me veía horrible en la imagen que puse hace unos días de mi vieja Creative Webcam NX, decidí poner screenshot de cómo aparezco en los hangouts de Google con la cámara de mi nueva laptop:

Con la cámara de mi nueva laptop

Con la cámara de mi nueva laptop

No, la calidad tampoco es espectacular, pero hago notar que era de noche, y además es un screenshot de la página del navegador donde estaba el hangout. Ya animado se ve bastante decente.

Y ciertamente me gusta más que usar Skype. Que al parecer en menos de un mes todos los usuarios de messenger serán migrados (de forma obligatoria) a Skype; durante años utilicé el messenger, pero tiene ya meses que ni siquiera me he conectado (solía causar que trabajara aún menos al escribir la tesis). No me queda claro que lo vaya a extrañar mucho.

En una década

He estado usando casi diario los Google+ Hangouts para videoconferencia (¿cómo se traduce eso?, ¿”pasadores de tiempo”?). Las razones son varias, pero la más importante, para mí, es que me evitan la molestia de instalar Skype, que cada vez me resultaba más desesperante.

Como he comentado no pocas veces en mi blog, detesto KDE, e incluido en eso va Qt. Compilarlo además en Gentoo es lentísimo, y prefiero usar mi procesador para cosas más interesantes. El cliente de Skype para Linux utiliza Qt, y al menos en Gentoo tienen la decencia de incluir una versión binaria de Qt junto con el paquete; pero de todas formas significa usar Qt, y si puedo siempre lo evito.

Además de Qt, Skype nunca mereció mucha confianza de mi parte; menos aún cuando fue comprado por Microsoft (que además casi garantiza que un buen cliente para Linux nunca existirá). Los Hangouts de Google+ me evitan todos estos problemas, y además Google me cae mejor que casi cualquier otra compañía, así que les doy el beneficio de la duda.

Técnicamente además los famosos hangouts están bastante padres; puede uno tener videoconferencia con N personas a la vez; corre todo dentro del navegador por lo que no es otra aplicación que hay que iniciar y configurar; y corre básicamente de forma perfecta en Linux, con un plugin para Chromium (que no dudo funcione también en Firefox) que mide en total como 21 Megabytes.

Comencé usando los hangouts en mi laptop, y la experiencia ahí ha sido básicamente perfecta excepto por dos problemas (ninguno relacionado con los hangouts): el primero es que mi laptop tiene unas bocinas que yo creo que son una broma, literalmente; y el segundo es que, por esas cosas que suelen ocurrir con Linux, el chipset que utiliza el bluetooth de mi laptop ahorita no está funcionando para que jalen mis audífonos bluetooth. Y hago énfasis en ahorita: hace unos meses funcionaba, y con casi toda seguridad en unos meses volverá a funcionar, sólo que como bluez pasó de la versión 4.101 a la 5, y no son compatibles, el proceso para que las aplicaciones que usan bluez se porten a la nueva versión puede tardar mucho. De hecho, es posible que con bluez 5 mis audífonos ya sirvan, sólo no he actualizado porque todo el resto del software sigue dependiendo de bluez 4.101.

Y para hacerlo más agraviante, al parecer todo lo relacionado con bluetooth funciona con bluez 4.101; incluso mis audífonos son reconocidos y ligados a la laptop. Sólo luego no aparecen como tarjeta de sonido externa. Como sea, no es grave; me pongo mis infalibles audífonos Genius, que además cuentan con micrófono incluido, y todo está chido.

De cualquier forma me dieron ganas de ver cómo funcionarían los hangouts en mi máquina de escritorio, en gran medida porque mi silla ahí es más cómoda, y el monitor es mucho más grande. Así que lo primero fue ver si servían bien los audífonos ahí; perdí unos quince minutos buscando dónde estaba el control de volumen para el micrófono, hasta que caí en cuenta de que PulseAudio es lo suficientemente inteligente como para no mostrarlo a menos que esté conectado.

Ni siquiera sabía que las computadoras ahora podían detectar cuándo estaba conectado un micrófono.

Luego fue la cámara de video, que es una antiquísima Creative Webcam NX que se conecta por USB a la computadora. Para que tengan una idea, la compré cuando pensé que me iría a hacer el posgrado a Canadá, así que sí tiene casi diez años conmigo; hablé de ella hace mucho. Bastante ha cambiado desde esa entrada; en particular, el controlador de la camarita está en el kernel desde hace años, y por lo que tengo entendido funciona perfecto… mientras en Windows a 64 bits de hecho nunca funcionó.

De nuevo tardé como veinte minutos tratando de encontrar mi camarita (el software; la camarita lleva años viviendo físicamente encima de mi monitor), hasta que por fin caí en cuenta de que por alguna razón el controlador no estaba compilado en mi kernel. En alguna actualización la opción de tener camaritas de video USB requirió alguna otra opción que no activé, y desde entonces no se había compilado el módulo. Así que recompilé el kernel, reinicié, y por fin tuve camarita de nuevo.

Y fue casi dolorosamente decepcionante:

Camarita

Camarita

Por supuesto las condiciones de luz en mi departamento apestan (más aún a las ocho de la noche), pero la calidad de la camarita es abismal. Tiene una resolución máxima de 352×288; en comparación, mi latop (que no es último modelo) tiene una resolución de 1280×1024. En mi monitor FullHD (1920×1080), la ventana de Cheese (el programa para tomar fotos de GNOME) tiene que escalar hacia arriba la imagen para que quepan los botones de su barra de herramientas. Y con tantito que se escale, a esa resolución, todo se ve súper pixeleado.

Así que descarté mi escritorio para usar los hangouts, a menos que mis interlocutores quieran ver sombras nada más. Lo que me impresionó, y que es el punto de esta entrada, es que hace diez años una camarita USB con resolución 352×288 no sólo no era rara, sino que tendía a estar en el grado alto del espectro. E independientemente de la resolución, la calidad del video (y fotos) que toman las camaritas actuales es muchísimo mejor que las de hace diez años.

En una década ocurrió que el hablar con alguien a cientos de kilómetros de distancia, y además verlos al mismo tiempo en tiempo real, se puede hacer de forma ridículamente sencilla, y con una calidad del video tal que uno puede ver los insectos caminando en las paredes detrás de los interlocutores (true story). A veces se me olvida que ya vivimos en el futuro.

Y por cierto, los hangouts funcionan sorprendentemente bien en teléfonos celulares inteligentes, si bien sólo los probé una vez, y ambos participantes usando red inalámbrica. Supongo que habrá que ver si funciona bien sobre 3G, aunque la verdad lo dudo. Mi teléfono no es 4G LT, pero me imagino que el próximo sí lo será.

Y entonces sí voy a sentir de verdad que vivimos en el universo de Star Trek.

Mis fotos

Gracias a mi aplicación para subir fotografías, y a mi aplicación para editar etiquetas, terminé ya de organizar, etiquetar, respaldar y subir todas mis fotos, incluyendo las que tomé el fin de semana pasado cuando Juan se casó.

Galería

Galería

En el procesó afiné y mejoré varias cosas de mis aplicaciones, y me parece que ya son suficientemente robustas. La metodología que tengo para manejar mis fotos está ya bastante estandarizada, y se integra de manera perfecta con GNOME 3, así que espero no volver a quedarme tan atrasado en el mantenimiento de mi galería. Además, como ahora tengo disco duro de sobra, decidí liberar a mi laptop de un montón de cosas (videos e imágenes de CDs y DVDs, principalmente) que no tenían razón de estar ahí, con lo que puedo ya tener una copia de mi colección de fotos en mi computadora portátil.

No lo he platicado en el blog, pero estoy estrenando laptop (desde hace varios meses), y tiene un disco duro de estado sólido; esto es espectacular porque todo corre estúpidamente rápido… la desventaja es que es diminuto para el tamaño de discos duros al que estoy acostumbrado (tiene 128 GB). Es la primera laptop donde borré completamente el Windows que venía instalado; necesitaba el espacio. Actualmente mi colección de fotos ronda en los 21 Gigabytes; dado que son del orden de 9,000 fotografías, espero no llegar a los 60 Gigabytes pronto: me quedan menos de 40 Gigabytes libres en la laptop. Cuando llegue a ese tamaño, espero ya haber cambiado de computadora portátil.

Tener las fotos en la laptop (y no sólo aventadas en un directorio, sino además ya bien integradas en Shotwell) me permitirá actualizar mi galería incluso si salgo de México en un viaje largo; podré organizar las fotos en mi laptop, e incluso subirlas a la galería en línea desde donde quiera que esté. Gran parte del problema durante mis viajes largos de los últimos años fue que la base de datos de mis fotos en F-Spot estaba en México en mi máquina de escritorio, y no sabía cómo sincronizar dos instalaciones distintas del programa en máquinas diferentes. Con Shotwell ya sé cómo hacerlo: es sólo es cosa de mantener mi directorio $HOME/Pictures sincronizado entre las dos máquinas, y copiar la última versión del archivo $HOME/.local/share/shotwell/data/photo.db sobre la versión viejita en la máquina que se esté sincronizando.

Además de la copia en mi máquina de escritorio y en mi laptop, tengo una copia de mis fotos en mi media center (que tendré que escribir un programa que me permita exportar la base de datos de Shotwell y meterla en la base de datos de XBMC, porque si no sólo se puede ver fotos por directorio), otra en mi servidorcito Atom, y una más en una máquina debajo de siete capas de adamantium y kriptonita que la tengo corriendo en la Zona Fantasma. Y una copia más (pero con las fotos escaladas a 1024×768) en Xochitl en mi galería en línea, que los invito una vez más a que la exploren.

Quick Photo Editor

Limpié y subí también mi aplicacioncita para editar etiquetas en fotos; la pueden encontrar en Github.

Quick Photo Editor

Quick Photo Editor

Llevo años escribiendo pequeñas aplicaciones que me quedo nada más para mí. No creo necesariamente que le vayan a servir a absolutamente nadie más, pero el hacerlas públicas me obliga a tener el código en buen estado, legible, y a escribir el mínimo de documentación e infraestructura necesarias para que no sea nada más un archivo en Vala, Python, C o Perl aventado en algún directorio de mi $HOME, que años después no tengo ni idea de qué hacía o por qué lo había escrito.

Esta aplicación está escrita en Vala, que me parece ahí reside en gran medida el futuro de GNOME; es muy divertido de programar, y los programas son razonablemente rápidos y con poco uso de memoria (contrario a C#). Además, el código es muy legible y compacto; no al grado de Python, pero me parece que sí más que C#. El programita, aunque su funcionalidad a lo mejor le es inútil a nadie que no sea yo, sirve también para estudiar un ejemplo pequeño, pero funcional, de cómo escribir una aplicación con autotools, usando gettext para internacionalización, cómo instalarle iconos, y otras cosas de ese estilo.

Gallery 3 Uploader

Total que limpié mi programita para subir fotos a Gallery3; es básicamente para mi uso privado, pero consideré que a lo mejor a alguien le podría resultar útil al menos el módulo que se comunica con el API REST de Gallery3.

Como lo iba a hacer público, lo limpié, le puse una interfaz gráfica, lo hice que hablara varios idiomas (inglés y español, porque no sé otros), y le puse toda la parafernalia para que se pueda compilar haciendo la santísima trinidad de ./configure && make && make install. El resultado no sólo es más agradable a la vista; ahora puedo seleccionar fotos en Nautilus, hacerles click derecho, y abrirlas con esta aplicacionciota, lo cual las manda a mi galería en línea.

Gallery 3 Uploader

Gallery 3 Uploader

Le faltan muchas cosas: por ejemplo, tronará sin decir nada si alguna de las etiquetas que espero encontrar en las fotos falta, pero ya es útil para mí, y espero lo sea también para alguien más. El programita está en Github: https://github.com/canek-pelaez/g3uploader.

Ahora sólo tengo que limpiar la aplicación que edita las etiquetas.

La vida a través de una cámara digital

En 2004, la Universidad de Waterloo me aceptó para que fuera a hacer mi maestría. Entre otras cosas por eso empecé este blog, porque quería escribir acerca de mis estudios en el extranjero. Por las mismas razones, estuve considerando desde febrero de 2005 el comprar una cámara digital, y en marzo Sergio, el hermano de Enrique, me hizo el favor de comprarme una Sony Cybershot DSC-P200 en el gabacho, que en abril por fin tuve en mis manos.

Por supuesto ya saben qué pasó: Conacyt decidió que la computación no era un “área estratégica” para México y no me becaron, así que me quedé aquí y pasaron los siguientes ocho años de mi vida. De eso no es esta entrada.

La entrada es de que una vez tuve mi cámara, de inmediato decidí que necesitaba un sitio en línea para poner mis fotos a la vista de todo mundo. Agarré e instalé Gallery, que era (y es, me parece) el programa más utilizado para mantener una galería en línea, y de inmediato me desagradó. Era lento, usaba mucho (y mal) JavaScript (o a lo mejor era sólo que entonces los navegadores traían pésimos motores de JS), y además no me gustó cómo se veía. Era la versión 1 del programa.

Instalé entonces Coppermine, que fue básicamente el primer programa alternativo a Gallery que encontré, y lo usé unos cuantos meses. En mi casa usaba F-Spot, que está escrito en C#, y que en ese momento me parecía un extraordinario programa. Claro, tenía entonces del orden de doce fotografías, entonces F-Spot hasta rápido parecía.

Mi colección de fotografías digitales estuvo durante varios años manejada, y de alguna manera controlada, por F-Spot. El programa no es para nada malo, sólo sufre el mismo problema que todos los programas escritos en C#: la memoria que consumen es ridículamente alta, y se vuelven lentísimos con no mucha información. Como sea, eso no lo descubriría sino hasta años después.

En 2005 todavía no lo descubría, porque les digo que tenía como quince fotos, pero mi uso de F-Spot causó que tuviera que dejar de usar Coppermine. F-Spot nunca fue pensado para usar álbumes; previendo que eso sería el futuro, F-Spot favorecía mejor las etiquetas, y entonces una foto puede pertenecer a más de una etiqueta. Uno puede emular la funcionalidad de álbumes con etiquetas, pero no al revés. Lo grave con Coppermine no fue que no tuviera etiquetas; era que no podía ni siquiera mover fotos entre álbumes. Además no podía subirlas fácilmente desde F-Spot (y en ese entonces la red era mucho más lenta), y todo se combinó para que decidiera dejar Coppermine.

Entonces volví a revisar Gallery, y seguía básicamente igual de malo que antes; pero por suerte ya estaba disponible el primer beta de Gallery2, así que decidí probarlo. Me gustó mucho más, pero lo que me convenció de usarlo fue que F-Spot tenía un plugin para mandar un conjunto de fotos a un álbum de Gallery2. Eso hizo mi vida mucho más sencilla.

Yo soy muy neurótico con mis colecciones, de lo que sea. De música, de películas, de videojuegos, o de fotos, me interesa que todo esté meticulosamente etiquetado y catalogado. En F-Spot podía ponerles a las fotos un comentario (donde generalmente pongo el nombre de los que aparecen en la foto, o el lugar donde estoy en el peor de los casos), y el plugin que subía las fotos a Gallery2 se encargaba de hacer que dicho comentario apareciera también en Gallery2. Era la gloria.

Así estuve durante años, muy feliz, aunque con varias incongruencias en mi galería en línea. Como F-Spot tenía varias etiquetas “principales” (Favoritos, Escondidas, Eventos, Lugares y Gente), yo traté de emular eso en Gallery2… lo cual es una enorme pendejada, porque terminé aventando casi todo al álbum de eventos. Además, por alguna razón que no comprendo, creé un álbum llamado “Pruebas” que aparecía ahí en la página principal de la galería, y que lo hizo durante varios años.

Como sea, quitando esas cosas todo medio funcionaba, y lo que más me importaba era que la información que metía con F-Spot a mis fotos, se conservaba cuando las subía a Gallery2. Hasta que un día los desarrolladores de F-Spot decidieron cambiar las cosas: lo que yo metía en F-Spot como comentarios a las fotos, se subía como el título a Gallery, pero entonces decidieron cambiarlo a que fuera el comentario. Y entonces no se veía esa información a nivel del álbum en Gallery2, se veía sólo en la página de la foto. Con eso podría haber vivido; lo que era horrible era que el título ahora era el nombre del archivo, algo del estilo dsc00768.jpg.

Pude parchar a F-Spot para que funcionara como lo hacía antes (de algo tiene que servir que sepa programar), pero ya para entonces, en 2008, se había comenzado a volver muy lento con todas mis fotos. Ya tenía del orden de 2,000 fotografías, y al programa le empezaba a pesar muchísimo. Además comenzó a estar súper inestable, y tenía que estar deshabilitando cosas para que no tronara.

A pesar de todo eso lo seguí usando, y aunque no de forma perfecta seguía funcionando lo más importante para mí, que podía pasar las fotos de F-Spot a Gallery2 preservando la información de las mismas.

Y entonces me fui a Europa durante tres meses, de enero a marzo de 2009, y se me ocurrió regresar con 2,500 fotografías más.

Cuando, después de meses, había metido todas las fotos de mi viaje a F-Spot, el programa ya era básicamente inusable para mí. Y además de todo, la subida de las mismas a Gallery2 no era raro que fallara de formas extrañas, lo cual dejaba una imagen de error en lugar de la foto (aunque sí generaba correctamente la miniatura, porque F-Spot era el que la generaba antes de subir la foto, lo que hacía todavía más difícil descubrir cuándo había fallado la transferencia).

Pero lo que hizo que me deshiciera de F-Spot fue que cuando regresé de California en 2009, donde visité a mi cuate Eddie en San Francisco, había estado guardando la información GPS de donde había estado, y decidí tratar de sincronizarla con las fotos (para que cada foto marcara dónde la había tomado). Y entonces me di cuenta de que las horas de las fotos estaba desfasadas por 6 horas, porque los idiotas de F-Spot estaban suponiendo que mi cámara estaba en horario GMT (UTC+0), y que como México (y mi escritorio) estaban configurados en America/Mexico_City (UTC-6), eso quería decir que tenía que moverle al tiempo de casi todas mis fotos.

No tienen idea de cómo me encabroné, porque nunca me preguntó o dijo nada al respecto, y yo pensaba que ya no podía rescatar el tiempo original. Así que cerré por última vez en mi vida F-Spot, y seguí trabajando en mi doctorado, viajando, y tomando fotos que aventaba al primer directorio que podía, sin ni siquiera pensar en que sería bueno algún día subirlas a mi galería.

Hasta que mi disco duro tronó, como comenté hace unos días.

Ya que recuperé mis fotos, y las respaldé en cuanta máquina pude respaldarlas, comencé a pensar en cómo restituir mi colección de fotos en mi máquina (sin usar F-Spot, claramente, que además al parecer dejaron ya de mantener: la última versión salió en 2010), y cómo después tener un sistema independiente de cualquier programa (o al menos de cualquier programa no escrito por mí) para sincronizarlo con mi galería en línea, que además migré a Gallery3 cuando me quedé sin novia, sin casa, sin dinero y sin trabajo.

Primero descubrí que las fechas modificadas por F-Spot eran las dadas por la etiqueta EXIF DateTimeOriginal, pero por suerte la fecha original estaba guardada en CreateDate, así que sólo escribí un script que comparara las dos fechas y reemplazara la primera con la segunda si acaso diferían; para eso utilicé exiftool. Luego decidí mover la información de F-Spot a las fotos directamente. Los comentarios que con tanto cuidado había metido a las mismas durante mis años de usar el programa estaban en una base de datos SQLite, así que escribí un programita en Python que sacaba esa información, y la guardaba en las etiquetas EXIF UserComment, Title, ImageDescription y Caption, porque me pareció que era mejor ser redundantemente redundante. Usé exiftool de nuevo para manipular las etiquetas de las fotos.

Ya que hice eso, decidí probar Shotwell, el nuevo programa para manejar fotos de GNOME 3. El programa está escrito en Vala, que todo el lenguaje me parece un maravilloso hack, y me gustó mucho cómo funciona. Sólo que entonces vi que en algunas fotos aparecían mis comentarios como títulos, y en otras sólo el nombre del archivo. Investigando (tuve que bajar hasta el código fuente de Shotwell), vi que lo que pasaba es que Shotwell usaba la etiqueta Iptc.Application2.Caption para el título, porque al parecer es lo más estándar. Esa etiqueta no es EXIF, es IPTC, así que tuve que usar el programa exiv2 para reacomodar los comentarios en mis fotos. Por suerte, todo esto ya era sólo escribir otro script que hiciera toda la chamba. También vi que Shotwell usa la etiqueta Xmp.dc.subject para etiquetas internas del programa, así que decidí que con eso haría mis álbumes.

Shotwell maneja álbumes a la antigüita, todos basados en fechas. Se pueden mezclar fotos entre álbumes, pero decidí mandar eso completamente al carajo: a partir de ahora, mis álbumes están definidos por un rango continuo de tiempo, y a la chingada con todo lo demás. Además de álbumes, Shotwell maneja etiquetas, pero son ortogonales los primeros a las segundas. De cualquier forma, decidí arbitrariamente que la única etiqueta que tendrían mis fotos sería el nombre del álbum al que pertenecen.

Como los álbumes de Shotwell están basados en tiempo, automaticamente divide todo en años, estos en meses, y ya dentro de los meses hay álbumes que pueden ser de un instante en el tiempo (si tienen una sola foto), o de varios días. Decidí que también así funcionaría mi galería en línea, y así es como reconstruí mi colección de fotos. Fue poco trabajo, en general, porque casi todo se pudo automatizar con scripts. Sólo tuve que reacomodar algunas fotos que no tenían un álbum bien definido, y de paso acomodé las fotos igual en la jerarquía del sistema de archivos: tengo un directorio 2009, dentro de él un directorio “02 Febrero”, y dentro de él un directorio para cada álbum, que como dije describen rangos continuos de tiempo.

Jerarquía de archivos

Jerarquía de archivos

La única bronca es cuando se me parte un evento que cae entre el último día de un mes y el primero del siguiente (los años nuevos suelen ser así), pero decidí que eso no era terriblemente grave. De esta forma, Shotwell no se mete para nada con mis fotos; jamás les escribe nada. Sólo lee información de ellas, y las despliega bonito, con lo que espero evitar las broncas que F-Spot me daba. Además, la organización de mis fotos en el disco duro es virtualmente idéntica a la organización de mis fotos en Shotwell.

Shotwell

Shotwell

Con mi colección reorganizada una vez más, decidí que necesitaba reestructurar mi galería en línea también. Inicialmente pensé en borrar las fotos que ahí estaban y meterlas todas de nuevo, pero resultó imposible: tuve que borrar todo y empezar de cero. Por suerte Gallery3 ofrece un API REST para manipular la galería en línea; está súper chido, muy fácil de programar, y me permite olvidarme de que nadie más me diga cómo deben subirse los datos a mi galería. Hice un programita en Python (versión 3; el uso de UTF-8 me impide que pueda usar Python 2) que le pasa uno una lista de archivos JPG, y les saca la información que me importa (básicamente la fecha, el título en Iptc.Application2.Caption y el álbum en Xmp.dc.subject), y procede como sigue:

  1. Saca el año de la foto, y comprueba que exista un álbum principal en la galería en línea llamado como el año. Si no existe, lo crea con la descripción “Año 2009″, por ejemplo.
  2. Saca el mes de la foto (01, …, 12), y comprueba que exista un álbum con ese nombre debajo del álbum del año correspondiente. Si no existe, lo crea con la descripción “Mes de Febrero”, por ejemplo.
  3. Saca el álbum de la foto, lo normaliza (quita acentos y símbolos, convierte espacios en guiones, etc), y comprueba que exista un álbum con ese nombre debajo del álbum del mes correspondiente. Si no existe, lo crea con la descripción idéntica al álbum, sin normalizar.
  4. Escala la foto a 1024×768, de ser necesario, preservando todas las etiquetas EXIF, IPTC y XMP.
  5. Sube la foto escalada al álbum correspondiente, usando como nombre el nombre del archivo, como título la etiqueta Iptc.Application2.Caption, y como descripción una vez más el álbum.

Todo esto es automático, y además el programa es suficientemente listo como para comprobar la existencia de cada álbum exactamente una vez; si ya comprobó que existe, guarda esa información para usarla en subsecuentes fotos. Además, si hay un error en la red lo detecta, y vuelve a subir la foto en ese caso. De los miles de fotos que subí, sólo me generó tres o cuatro duplicados, que además fue muy sencillo detectar. Mi programa incluso usa colorcitos para avisar qué está haciendo:

Mi programita en Python

Mi programita en Python

Las consecuencias de todo esto son varias: mi galería en línea tiene entonces una organización virtualmente idéntica a mis fotos en Shotwell (y por lo tanto en mi disco duro):

Mi galería en línea

Mi galería en línea

Pero además las fotos, durante todo este proceso, guardan la información siempre en ellas mismas; las tengo respaldadas (como ya he dicho) en varias máquinas en éste y otros sistemas solares, así que si algo terrible ocurriera con mi computadora y con mi galería en línea, no tengo nada de qué preocuparme: sólo copio mi respaldo, y puedo reconstruir mi colección en Shotwell casi de inmediato (sólo tengo que renombrar cada álbum, pero eso es muy rápido porque cada foto tiene una única etiqueta con el nombre de su álbum), y puedo reconstruir mi galería en línea de forma automática (aunque tendría que esperarme un rato a que acabaran de subirse las fotos).

Por supuesto, para que todo esto funcione las fotos en primer lugar deben tener la información dentro de ellas. Con la parte de mi colección que ya tenía organizada esto fue muy fácil, porque todo estaba en la base de datos SQLite de F-Spot. Con las fotos que no he organizado significa meterles el título (Iptc.Application2.Caption), y el álbum (Xmp.dc.subject). El álbum no me preocupa mucho, porque al cabo eso lo puedo hacer después de acomodarlas en directorios, y correr un script (que ya escribí), que lee el nombre del directorio (quitándole el prefijo numérico de ser necesario) y se lo pone a la foto.

El título es más desmadre, porque tengo que ponerlo foto por foto. Así que hice lo que cualquier programador que se llame así mismo uno haría: escribí un programa. Lo escribí en Vala (se me antojó después de ver el código de Shotwell), y de una vez le escribí el código necesario para que también pueda girar las fotos acostadas. Que de hecho no se giran, sólo se escribe una etiqueta EXIF que especifica que esa foto debe mostrarse girada.

Quick Photo

Quick Photo

El programa es bastante rápido; al dar Enter en el campo de texto, inmediatamente se guarda la información en la foto (que la imagen en sí no se modifica, sólo sus etiquetas), y se mueve a la siguiente. Lo único malo es que tengo que usar el ratón para girar la foto a la izquierda o derecha; tengo que programarle que lo pueda hacer desde el teclado, y entonces será casi perfecto para mis necesidades. Lo pienso liberar (junto con mi progamita en Python); a lo mejor a alguien le resulta útil.

Ahora sólo tengo que hacer lo que durante años estuve evitando: organizar las miles de fotos que no he organizado. Ya organicé (y subí) un par de meses de 2010; me falta el resto de ese año, el 2011 y el 2012. En 2012 no tomé casi fotos (estaba encerrado escribiendo la tesis, o quedándome sin novia, sin casa, sin dinero y sin trabajo), pero en 2011 tomé cientos de fotos en mi viaje por alrededor del mundo. Además, ya con esta infraestructura, supongo que debería también organizar las fotos de mi celular; varias lo valen, me parece, pero eso sí me va a tomar tiempo. Mientras tanto, tengo todo respaldado de forma redundantemente redundante, y cada vez que termino con un álbum nuevo (que generalmente se traduce a un día o dos de fotos), vuelvo a respaldar todos los cambios.

Mi punto con todo este impresionante choro, es que cuando creé mi galería en línea, el programa me pidió que le pusiera un nombre a la galería. Yo, falto como siempre de imaginación, le puse “Fotos de Canek”; así se sigue llamando hasta estos días. Pero después de ponerle el nombre, me pidió que lo describiera, y en ese momento (hace casi ocho años), sin pensarlo demasiado le puse “La vida a través de una cámara digital”.

Respaldando, reparando y reorganizando todas las fotos que he tomado desde abril de 2005, me di cuenta de que no pude haber elegido una mejor descripción para mi galería en línea: de verdad refleja mucho (aunque no todo, y muchas veces ni siquiera lo más importante) de lo que ha sido mi vida en estos años, que cubren básicamente mi maestría y doctorado hasta ahora. Los invito a que ustedes también le echen un ojo, si así lo desean, a mi renovada y mejorada galería en línea; pocas cosas me enorgullecen y alegran más que poder compartir las imágenes que capturan los varios momentos significativos que he tenido, y los viajes que he realizado.

Ahora que volví a revivir casi todos los momentos que fueron capturados con mi camarita Sony, no pude sino llegar a dos conclusiones: la primera, que soy increíblemente afortunado. Y la segunda: que me la he pasado poca madre en estos años. Incluso considerando los momentos amargos, las experiencias tristes, y las inevitables heridas del corazón, en retrospectiva para mí el balance es claro: lo bueno supera con creces, y por mucho, a lo malo. Me he divertido como enano en todo este tiempo.

Y lo bailado, nadie me lo quita.

Los 500 GB

Hace unos meses se me murió un disco duro de 500 GB. No había nada ahí que no tuviera de forma redundante en otra máquina (y en algunos casos en varias otras máquinas), y lo que no estaba de forma redundante no era realmente importante para mí, o lo podía bajar de nuevo de Internet.

Todo, excepto varias decenas (si no centenas) de fotografías.

Mi galería en línea (la que acabo de actualizar, por cierto) la he tenido abandonada desde hace mucho tiempo. Regresé de mi primer viaje a Europa en marzo de 2009 con varias centenas de fotografías, y esto causó que me tardara mucho en catalogarlas y ordenarlas; mis subsecuentes viajes en 2010 agravaron la situación, y mi viaje monstruo de seis meses en el 2011 causaron que sencillamente dejara de pensar en que en algún momento de mi vida tenía que organizar mis fotos. Si lo hacía, terminaba tirado en el suelo en posición fetal respirando a través de una bolsa de papel.

Lo que terminó pasando fue que aventaba los nuevos archivos de mis fotos en varios directorios, y me olvidaba de ellos, sin jamás pensar “hey, tal vez sería buena idea respaldarlos”. Y entonces un día mi disco duro de 500 Gigabytes se murió, llevándose mi $HOME y otra partición que venía utilizando desde hacía años.

Esto ocurrió en las etapas finales de la escritura de mi tesis doctoral, así que no tuve tiempo de llorar por mis archivos perdidos. Mis documentos (incluyendo los de la tesis… y todos los demás) están triplemente respaldados en mi laptop, mi servidorcito Atom, y una máquina corriendo en una bóveda secreta debajo del océano Antártico, así que sólo cloné mis documentos en un $HOME vacío, y seguí escribiendo la tesis de doctorado.

No tiré el disco, porque pensé que tal vez un día existiría la posibilidad de recuperar la información en él.

Cuando acabé la tesis de doctorado, busqué en línea qué podía hacer para recuperar la información de un disco que estaba, aparentemente, morido. Debo resaltar que el disco duro en cuestión hacía los ruidos normales que hace un disco cuando se conecta y recibe poder, pero no aparecía en ningún lado: el BIOS de mi computadora no lo detectaba, y tampoco ocurría si lo conectaba por un cosito SATA→USB.

Internet no fue de gran ayuda, tal vez porque mi Google-fú no fue tampoco el mejor del mundo: básicamente pregunté “¿cómo le hago para revivir un disco duro morido?”. La respuesta en general fue que la mejor oportunidad (si no había click de la muerte), era agarrar el modelo del disco duro, y buscar en la red para comprar únicamente el PCB, el circuito (realmente una computadora chiquita) que está atornillado debajo. La idea era conseguir un reemplazo idéntico, y orar que con eso se pudiera recuperar la información.

Dado que ya entonces andaba corto de dinero, ni siquiera me pasó por la mente; por lo que leí había que pedir el famoso PCB a China, y nada más el envío iba a costar una lana, si es que acaso encontraba el modelo exacto que necesitaba, y sin ninguna garantía de que al final funcionara. Así que lo dejé pasar, y seguí con mi vida.

Que en este caso consistió en quedarme sin novia, sin casa, sin dinero y sin trabajo.

Cuando por fin me medio recuperé de eso, de las cosas que hice para distraerme fue actualizar y configurar propiamente mi media center. No recuerdo cuándo fue la última vez que platiqué de él, pero el año pasado lo cambié de Moovida a XBMC, que resultó ser de los programas más impresionantes en el mundo del software abierto que he visto en mi vida.

Organicé cuidadosamente mis series de televisión y mis películas, así como mi animé y mi música. Y cuando el polvo se asentó, resultó que el espacio libre en mis discos duros estaba peligrosamente bajo. Lo cual es obvio, porque había perdido 500 Gigabytes de espacio unos meses antes.

Cuando la situación se hizo insostenible, y al ver el ridículo precio al que han llegado los discos duros de 2 Terabytes, le hablé a Enrique y fuimos a que me comprara uno. El disco en sí mismo era necesario; pero además mi media center tenía un disco duro de 500 GB, y pensé que con suerte sería el mismo modelo del muerto, y por lo tanto que podría intercambiar los PCB de ambos, y milagrosamente recuperar mi información.

Así que el día que compré el disco de 2 Terabytes, agarré mi media center y lo abrí para cambiarle el disco. Cuando saqué el viejito, de inmediato vi que no me iba a servir para reparar el otro; son modelos distintos. Sin embargo, eso me hizo pensar que tal vez ahora no sería tan mala idea buscar el PCB del disco malo en la red, y eso hice.

Eso fue lo que debí hacer primero.

Resulta que ese modelo de disco duro en particular (de hecho de firmware) tiene un fallo muy conocido en la red: cuando un contador en el firmware llega a cierto número, el disco duro se apendeja y se queda ahí atorado en el estado “busy”, lo que hace que el problema sea mundialmente conocido como “Seagate BSY state”. Googléenlo, si quieren.

El punto es que en todos lados confirmaban que la información del disco estaba intacta, que era posible recuperarla, y de hecho que el mismo disco duro podía seguir siendo usado. El único problema es que necesitaba soldar un cable en especial para conectar el disco duro a un puerto serial, o canibalizar un cable de Nokia que ya tiene ese circuito integrado.

Hay una razón por la que no soy ingeniero: detesto estar peleándome con cablecitos. Por eso me ligué dos ingenieros el primer semestre de mi maestría para que con ellos pasara Arquitectura de Computadoras; yo me encargué de todo el software, y dejé que ellos se pelearan con el hardware.

Así que me puse a buscar el cable, un famoso Nokia CA-42, que para acabarla de amolar estoy seguro que tuve en algún momento de mi vida. En Amazon cuesta 7 dólares, pero no lo envían a México; en MercadoLibre está en 150 pesos, pero el envío cuesta otros 150. Así que me decidí ir al Centro a buscarlo. Lamentablemente sólo pude ir hasta hoy, porque estuve trabajando en un artículo hasta ayer en la noche. Y hoy es domingo, así que un montón de negocios estaban cerrados.

Por suerte lo encontré, pero vi con algo de temor que no era un cable de Nokia original, sino un clon chino, y ya había leído que a veces con cables no originales el procedimiento no servía. Como sea, lo compré (me costó 100 pesos), y regresé a mi casa. Voy a platicar muy por encima que es lo que tuve que hacer, pero pueden verlo a detalle aquí, aquí, o en el tubo, si les da hueva leer.

El disco duro seguía igual de muerto que meses atrás:

Disco duro muerto

Disco duro muerto

El PCB es lo que está debajo:

PCB

PCB

Lo quité:

PCB suelto

PCB suelto

Le puse un cartoncito encima de la cabeza, para que el PCB no se comunique con el disco duro, el mismo no responda, y entonces el firmware no entre en el estado ocupado:

Disco duro con cartón

Disco duro con cartón

Y volví a poner el PCB:

PCB con cartón

PCB con cartón

Después desmadré el cable de Nokia chafa, y lo conecté a un viejo cable para conectar CDs a tarjetas de sonido, para poder conectarlo fácilmente al disco duro:

Cable Nokia chafa

Cable Nokia chafa

Y finalmente prendí el disco duro, lo conecté por USB a la computadora con el cable, y comunicándome serialmente con él le mandé comandos para revivirlo. Pueden verlo a detalle en las páginas que ligo (y todo se puede hacer con Linux, sólo reemplacen Hyperterminal con minicom); la verdad no me importa mucho qué hicieran en particular los famosos comandos.

Lo que me importa es que funcionaron, y que recuperé mi disco duro.

Más importante aún es que toda la información en el mismo sigue ahí, y la estoy respaldando todita en este momento. Lo principal eran las fotos, pero de una vez estoy copiando todo, y a partir de ahora sí voy a mantener mis fotografías también triplemente respaldadas.

Y encima ahora tengo un disco duro extra de 500 GB. Y un cable Nokia chafa para hacer todo de nuevo, si acaso es necesario.

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.