Humos y arbolitos

O árboles y humitos: Este post es el par de mi lado del post Python más rápido que Java que escribió Humitos hace algunos días.

Arranquemos desde el principio... una mañana en la que entra Humitos al canal IRC de Python Argentina (#pyar en irc.freenode.net), y plantea el problema de cual es la mejor estructura de datos para armar un autocompletador de palabras. Esto es, a partir de un diccionario de palabras, que estructura las guarda mejor para que cuando uno ponga joye, el sistema sugiera joyel, joyelero, joyero y joyer.

Yo pensé en un árbol con una letra por nodo. Al toque, le sugirieron que usase un árbol Trie. Yo, que como no soy informático no conozco muchos nombres, fui a revisar qué era un árbol Trie.

La cuestión es que un árbol Trie era lo que yo pensaba que era: un árbol con una letra por nodo. Por ejemplo, para las palabras que usé antes:

Árbol simple

Perfecto. Humitos tenía la tortura de tener que hacer esto en Java para la facultad, así que luego de llorar un rato puso manos a la obra. Iba como "reportando" en el canal de PyAr, e hizo un par de preguntas. Yo, viendo que era difícil discutir el tema desde lo abstracto, me tomé un rato e hice una implementación en Python y se la pasé.

Salió bastante derechita. Básicamente hice una clase Nodo que mantenía la letra, los ramas hijas, y un flag para indicar que hasta ahí llegaba la palabra. Parecía andar, tanto que Humitos termino implementando casi lo mismo en Java.

Al otro día, sin embargo, Humitos me dió dos malas noticias. La primera, era que el sistema este consumía mucha memoria... para el diccionario de más de 80 mil palabras, ¡¡el árbol armado ocupaba 180 MB!!. Como efecto secundario, tardaba mucho en armar la estructura en memoria (como 7 segundos); lo bueno era que la búsqueda en sí era súper rápida.

Por un lado lo mejoré usando __slots__ (para que cada objeto Nodo ocupe menos memoria, algo sólo relevante cuando uno tiene tantos y tantos objetos). Por otro lado, encontré y solucioné una ineficiencia importante: tenía un nodo casi al pedo en cada hoja del árbol. Con estas dos correcciones, el sistema pasó a ocupar 55 MB en memoria, y tardaba 4 o 5 segundos en levantar.

Hasta acá, todo bien.

Pero luego, Humitos se dió cuenta de que tanto su programa como el mío tenían algunos problemas en aquellas palabras que simultáneamente eran completas y parte de otras. Siguiendo con el ejemplo anterior, tenemos allí dos casos de estos: joyel es palabra completa, pero a su vez parte de joyelero; lo mismo con joyer y joyero (por otro lado, joye, por ejemplo, es sólo parte de otras palabras, no una palabra completa por si misma).

El problema era tan sutil que se mostraba en algunos casos y en otros no, dependiendo del orden de las letras (y esto era provocado por la forma en que armábamos la estructura palabra por palabra).

Estuve como tres horas en la oficina peleándome con esto, pero luego tuve que hacer otras cosas (trabajar, bah) y no lo pude solucionar. El código se iba complicando y complicando, y no le encontraba la vuelta.

Esa noche era el concert de uno de los jardines de Moni, así que tuve como media hora de auto hasta allá. En esa media hora el cerebro trabajó tranquilo, y me di cuenta de tres cosas....

Por un lado debía dejar de usar clases para el Nodo, una estructura de diccionarios debía de servir si encontraba la manera de marcar el fin de las palabras. Por otro lado, en lugar de ir armando la estructura palabra por palabra, seguramente sería más fácil a nivel de código el armarla teniendo todas las palabras y recorriéndolas por "columnas" de letras.

Esas eran optimizaciones, pero también se me ocurrió un cambio más fundamental. En los finales de las palabras, en muchos casos seguramente la estructura pierde forma de árbol frondoso y como que le quedan "ramas peladas". En estos casos, en lugar de almacenar secuencias de nodos, es mucho más eficiente guardar el resto de la palabra y listo.

Para verlo mejor, les redibujo el ejemplo anterior, pero bajo este concepto:

Comprimido

Como es una especie de Trie degenerado, excusándome bajo una incapacidad total a la hora de los nombres, y considerando que la versión anterior me tenía un poco frustrado, lo terminé llamando Fucked Trie.

Llegué al concert bastante antes que los padres, pasaron 40, o 45 minutos antes de que se ocupara el salón. Ese tiempo lo pasé codeando tirado en un rincón, e implementé el 95% de lo que sería la solución final. Le terminé de dar un par de retoques el lunes o el martes pasado, en Brasil, donde le corrí el profiler y optimicé un par de detalles.

El producto final tarda menos de un segundo en cargar, ocupa sólo 18 MB de memoria, y hace las busquedas en 60 micro segundos, centenares de veces más rápido que antes... ¡una preciosura! El código, junto con el diccionario de palabras, acá.

Comentarios Imprimir

Películas, actualización, gran

¡Cuanto hace que no hacía este update! Casi seis meses.... Supongo que por eso es tan sabroso.

Todo esto es lo que acabo de anotar para ver:

Y todo esto es lo que vi en este período, junto con un pequeño comentario así el Chaghi no me patea los tobillos, :)

  • ...al fin, el mar: +0. Es medio lentona, y el tema principal no es del todo interesante, pero es una película aprovechable sobre algunos puntos de vista de la vida cubana.

  • Amanece que no es poco: -1. Bizarra, rara, tanto que sólo aguantamos los primeros 15 minutos.

  • Art school confidential: -0. Por ahí abajo hay dos o incluso tres temas interesantes que podrían desarrollarse... pero la peli no los aprovecha, y termina aburriendo.

  • Before sunset: +0. Linda, interesante, mucho diálogo, pero sabroso.

  • Charlie and the chocolate factory: +1. Burton, Johnny Depp y Helena Boham Carter... le agregás un tema interesante y la película ya es buenísima, ;)

  • Clerks: +0. Interesante película, incluso sin considerar que se hizo con algunos miles de dólares solamente (eso sí, no esperen decorados, actores conocidos o efectos especiales...).

  • El laberinto del fauno: +0. El tema es súper interesante, y es bueno ver cómo se pueden hacer películas de alta calidad de efectos especiales en castellano; el guión de la peli no es del todo atractivo.

  • Fracture: +0. El final no desmerece la peli, pero esperaba algo más ahí. ¡Qué bueno es Anthony Hopkins para este tipo de películas!

  • Girl, interrupted: +1. Cuando una película dramática me gusta es porque tiene mucho contenido aprovechable para aprender de otras personas y situaciones; muy buenas actuaciones, también.

  • Harry Potter and the Order of the Phoenix: +0. La peli está buena, pero es oooooootro capítulo del chico Potter, y no agrega mucho nuevo.

  • Ice age 2: +0. No está tan buena como la primera, pero es divertida.

  • Palermo Hollywood: -1. La historia tiene una luz de que sea interesante, pero está mal llevada y mal actuada.

  • Playing God: +1. Interesante perspectiva de cómo una persona puede tomar control de su vida, y aprovechar lo que pasa para salir a flote, aunque lo que pasa no sea precisamente bueno.

  • Raging Bull: +0. Es un clásico absoluto, de los que estoy viendo por los actores y director de la peli. Todo muy bien, lo único que le resta es que es la vida de un boxeador... y el boxeo me disgusta.

  • Spiderman 3: +0. Pochoclera, obviamente, es un cómic. Mírenla si quieren ver eso.

  • Taxi Driver: +1. Otro clásico imperdible.

  • The constant gardener: +1. Profunda, bien actuada, con un tema interesante, y muy dinámica.

  • The Godfather, I, II y III: +1. Es una historia muy buena, muy bien dirigida, y con actuaciones fantásticas. En algunas partes es apenas lenta, pero es bastante profunda y con mucho significado.

  • The grudge: -0: Pintaba interesante, pero sólo fue más de la típica película de terror de estos últimos años.

  • The ninth gate: +1. Muy buena historia, muy buen tema (el final raro, pero no alcanza a apagarla).

  • The passion of the Christ: -1: Comentario.

  • The skeleton key: +1. Al revés que la de arriba, esta pintaba como lo mismo de siempre pero con la vuelta del vudú, y sin embargo sorprende y es inesperada.

  • Transformers: -0. No me gustó, demasiada acción para poder disfrutar los robots, y demasiados momentos de filosofía que no tiene nada que ver. Aclaración: nunca fui fanático de estos dibujitos.

Como resultado de tamaño update, la relación entre las fechas en que anoté cada peli para ver quedó así:

Total:         59
(anterior)     17
(02-Dic-2006)  11
(26-Jan-2007)   4
(26-Mar-2007)   8
(15-Jun-2007)   4
(19-Nov-2007)  15

Finalmente nos vamos quedando principalmente con cosas nuevas para ver...

Comentarios Imprimir

Semana de curso

El viernes Moni tuvo el concierto de cierre de uno de sus jardines. La producción fue interesante, con una historia central de unos chicos recorriendo el mundo y conociendo distintos países. Los nenes de Moni fueron los que más me gustaron de todos: tenían menos guión y producción (tengan en cuenta que son niños de 2 años de edad), pero fueron los que más se divirtieron en el escenario (quizás justamente por lo primero).

El sábado fue el bautismo y el primer cumpleaños de Sofía, la segunda hija de Diego y Diana (creo que a Jose ya la conocen, tantas fotos puse acá...). El bautismo estuvo lindo, aunque a mi entrar a una iglesia no me hace ninguna gracia. Sofía se portó muy bien, incluso apenas lloró con la "enjuagada bautismal".

Padre, madre, y Sofi

Luego nos fuimos a la casa de los chicos, donde se desarrolló el cumpleaños. Comí poco, pero demasiado (no, no es un oxímoron). Todo muy bien. Incluso, con Hernán, nos comportamos como seres humanos normales y todo! Las fotos de ambos eventos, acá.

El domingo no hicimos mucho, ya que yo apenas después del mediodía partí para San Pablo, donde tenía un curso de tres días sobre una plataforma de contenidos. El curso bien, y la mayor parte de los tres días la pasé con Diego, un chico que fue al curso de Ericsson Uruguay. Pero no salimos en ningún momento, por una cuestión de seguridad.

Hoy ya estoy de vuelta en Argentina, retomando el ritmo normal de la vida. Mañana, a la oficina, y el sábado, a ver a La Renga en el Autódromo con hermana y cuñado, :D

Comentarios Imprimir

El Sentido de la Vida

Luego de algún tiempo he vuelto al blog de un tal Gonzo, blog que se llama justamente como el título de este post.

No sé bien cómo llegué aquí la primera vez. Puede haber sido por la tira ECOL (historieta protagonizada por Bilo y Nano), de la que soy fiel seguidor, o el Diario de Nantes (EDITADO: la url no existe más), una recopilación del día a día de un españolito en Francia mientras perpetra su proyecto de fin de carrera (es largo, pero buenísimo).

Recuerdo que alguna vez leí algo de su blog, pero no me enganché, no me acuerdo por qué. La cuestión que el otro día buscando no se qué, encontré este (EDITADO: la url no existe más) sobre una odisea vivida en la playa...

Se trataba sin duda de un ángel, de una visión divina con unas tetas que desafiaban a la gravedad. A la nuestra y a la de Júpiter si hacía falta. No era simplemente que estuviera de rompe y rasga, sino que respiraba sensualidad por cada poro de su expuesta piel. Cada pequeño movimiento era poesía. Nunca antes se me habían empañado unas gafas de sol.

Y allí estábamos los cinco, sentados sobre las toallas, mirando de la única manera que se podía contemplar aquel espectáculo de la naturaleza. Con descaro, alevosía y admiración al mismo tiempo. En ocasiones Dios crea montañas, grandes praderas verdes, envía preciosas tormentas que rasgan el cielo durante horas y luego dejan tardes maravillosas. Y a veces coge el Photoshop y hace cosas como aquella. Porque Dios existe. Al menos a veces. Los curas deberían subir a ángeles así al púlpito, en top-less, y preguntar: ¿Existe Dios o no, cojones? Todos conversos en diez minutos.

¿Ven el estilo de escritura? A mi me causa mucha gracia. No es que no paro de reírme, pero lo disfruto muchísimo.

Lo mejor, sin embargo, es que no sólo habla de cosas más o menos superficiales, sino que el blog es interesante en muchos aspectos. En este (EDITADO: la url no existe más), por ejemplo, habla de la Madeleine esta que desapareció en no sé donde (justo el otro día alguien me comentaba algo de esto), y las responsabilidades de los padres...

El diez de Marzo de este año desaparece un chaval de siete años en un pueblo canario. El asunto no tiene repercusión más allá de las lindes de la comarca. Es una desgracia que así sea pero, salvo la estupidez humana, todo lo demás tiene un límite. Pásame otra birra.

Cuatro días más tarde desaparece Madeleine. En las semanas siguientes se monta un circo mediático de tres pistas. Los padres son respaldados por Beckham, santificados por el Papa en cónclave público e incluso recibidos por Rubalcaba. Se hace un concierto por África, por el cambio climático y por que aparezca la cría.

...

Pero la triste y cierta realidad es que hay que pasar pruebas físicas y un complejo examen teórico y práctico para conducir un coche pero cualquier desgraciado puede traer un crío al mundo.

Y mientras tanto el planeta continúa girando, la vida sigue, los USA empiezan una guerra en otro país y ni la salsa rosa ni los periódicos ni los telediarios dicen nada de todos los padres que hacen un esfuerzo al llegar a casa y apagan la tele para jugar un rato con sus hijos.

Distinto a lo que encontramos en muchos blogs, ¿no?

Bueno, la cuestión es que finalmente me enganché con el blog y lo leo siempre, :)

Comentarios Imprimir

¡Bienvenido Nico!

Ayer fuimos con Moni a visitar a Diegote y Valeria, y al recién nacido Nicolás, :).

Nico llegó el jueves primero de Noviembre a la noche, por cesárea, pero todo muy bien.

El niño es todo un modelo de tranquilidad! Te mira, bosteza un poco, se acomoda, se despereza, se ríe un poquito si le hacés unos mimos... ¿llorar? ¿qué es eso? Un maestro, el pibe.

Nico

¡Felicitaciones!

Comentarios Imprimir