Hay muchos benchmarks de frameworks en la web, uno de los más recientes es este de techempower que mide más de 70 frameworks diferentes.

Como estoy investigando Play Framework, y ya llevo usando Grails hace un par de años hice un pequeño test entre ambos ambientes, usando parte de un proyecto interno de mi trabajo. Publiqué en twitter que Play-Scala era varias veces más rápido que Grails, y mis colegas me pidieron que les “mostrara el código”.

Como no podía revelar el código del proyecto de mi trabajo, durante el fin de semana implementé un mini benchmark, y publiqué el código en este repositorio GitHub.

Ha terminado la fase de apelación al resultado del desafío Marzo Abril, les pido las disculpas del caso pues había prometido informar esto el domingo pasado.

Hay un cambio importantísimo, puesto que Rodrigo Chappa, acertadamente ha cuestionado la validez de mis pruebas, y como efectivamente tiene razón, corresponde reparar mi error.

El set original de datos sólo consideraba el caso en que las muestras tenían el mismo largo que la evidencia, esto genera que la solución de Sebastián resuelva el problema en tiempo más rápido y resultara ganadora en esas condiciones.

Sin embargo, la solución usando programación dinámica de Rodrigo Chappa es mejor, desde el punto de vista algorítmico, y eso se nota cuando cambiamos ligeramente las muestras.

La solución de Sebastían tiene una complejidad aproximada a O(n!), mientras que la de Rodrigo tiene siempre la complejidad O(n*m), donde n es el largo de la muestra y m el largo del ADN del sospechoso.

Las nuevas muestras están en mi repositorio GitHub corresponden a las muestras set4.adn y set5.adn, en que los largos de las muestras son diferentes. Pueden validar los resultado ustedes mismos.

Al ejecutar el programa de Rodrigo Chappa reconoce adecuadamente al culpable. Lamentablemente la solución de Sebastián empieza a consumir cpu y memoria, al punto que genera una excepción por consumo del heap.

Así que con estos antecedentes tengo que cambiar el veredicto, y otorgar el primer lugar a Rodrigo Chappa, felicitaciones por el algoritmo y por defender su solución.

En virtud de esto, el premio de 40 dólares originales(*), se dividirá en $30 dólares para Rodrigo y $10 para Sebastián como segundo lugar. Me contactaré con ellos para enviarles su giftcard en los próximos días.

Gracias a todos por participar, y gracias a Rodrigo y Sebastián por el espíritu deportivo mostrado.

Los invito a estar atentos pues se viene un nuevo desafío en los próximos días.

(*) recordemos que el premio total era para el ganador sólo si habían al menos 8 participantes, condición que no se cumplió, pero dado el esfuerzo he decidido premiarlos igual de esta forma.

Llegó el final del plazo para el desafío Marzo/Abril. A pesar de que hubo varios comentarios y consulta sólo llegaron a la fecha del 30 de abril 6 participantes, por lo que el premio prometido no podrá ser entregado (la giftcard de 40 dólares), puesto que no se cumple el mínimo de 8 participantes :-(

Sin embargo, vamos a revisar la participación de los otros seis y elegiremos al mejor. A continuación voy a publicar los resultados de las pruebas y tendrán una semana para apelar, al final de ese periodo entregaré un premio definitivo (distinto al ofrecido originalmente).

ACTUALIZACIÓN 1 DE MAYO 21:00 horas Estimados amigos, el plazo para participar ya se cumplió, tenemos 6 participantes. Lamentablemente no he podido organizar el tiempo para revisar las participaciones. Así que los resultados estarán dentro de los próximos días. Saludos y gracias a todos los que han participado.

Uno de los problemas comunes en bio informática es el de tratar de encontrar similitud entre secuencias de genes.

Los genes, en bio informática, se representan como secuencias de 4 posibles letras A,C, G o T (A de Adenina, C de Citosina, G de Guanina y T de Timina, las cuatro bases de los ácidos nucléicos como el ADN o el ARN).

Una manera de determinar la similitud de dos secuencias de ADN es usando una técnica conocida como alineamiento de secuencias.

El proceso de alineamiento de secuencias de genes es como sigue.

Dados dos genes, por ejemplo: AGTGATG y GTTAG, lo primero que se hace es insertar espacios (representados mediante el símbolo guión ‘-‘) en las secuencias de modo que ambas queden de igual largo. Los espacios se deben insertar de manera tal que permitan aumentar el grado de similitud entre ambas secuencias.

Para calcular este grado de similitud se asigna un puntaje de acuerdo a una matriz del modo que se explicará a continuación.

Una forma de alinear los genes AGTGATG y GTTAG es la siguiente:

1
2

AGTGAT-G
-GT--TAG

En este caso tenemos 4 coincidencias G en la segunda posición, T en la tercera, T en la sexta y G en la octava posición.

Otra forma de alinear ambos genes es la siguiente

1
2

AGTGATG
-GTTA-G

Acá tenemos también 4 coincidencias, G en la segunda posición, T en la tercera, A en la quinta posición y G en la octava posición.

¿Cuál alineamiento es el mejor?

Para determinarlo calculamos el puntaje de alineamiento, usando la siguiente matriz simétrica de puntajes:

Lo que hacemos es que vemos todos los pares que se forman y sumamos los valores de acuerdo a la matriz (el asterisco indica que no pueden haber pares -,-).

En el caso del primer alineamiento tenemos los siguientes pares:

1

A-,GG,TT,G-,A-,TT,-A,GG

Buscamos en la matriz de acuerdo a estas “coordenadas”:

1

A-=(-3), GG=5, TT=5, G-=(-2), A-=(-3), TT=5, -A=(-3), GG=5

Sumamos: (-3)+5+5+(-2)+(-3)+5+(-3)+5=9

Hagamos el mismo cálculo para el segundo alineamiento:

1

A-=(-3), GG=5, TT=5, GT=(-2), AA=5, T-=(-1), GG=5

Sumamos: (-3)+5+5+(-2)+5+(-1)+5 = 14

En este caso el puntaje de alineamiento es 14 por lo tanto este alineamiento es mejor.

El problema es encontrar un algoritmo que dados dos genes encuentre el alineamiento con el mayor puntaje.

Desafío Marzo-Abril 2013

Se ha cometido un asesinato. Entre las evidencias se tiene ADN de la víctima y del presunto asesino. Sin embargo, después de secuenciar el ADN el servidor que contienen el software que permite comparar las muestras ha sufrido un crash de disco. El equipo forense ha sido descuidado y no tiene respaldos.

Lo lamentable es que el computador contenía la implementación de un notable algoritmo de Alineamiento de Secuencias de Genes desarrollado por un prestigioso investigador con el que se ha perdido contacto.

Por lo tanto nos han pedido que propongamos distintos algoritmos de alineamiento de secuencias y que comparemos el ADN recogido en la escena del crimen contra el genoma de varios sospechosos.

Así que el desafío de esta oportunidad consiste en construir un programa que reciba un archivo con la siguiente forma: - En que la primeras 5 lineas viene la matriz de puntajes - Después viene la evidencia (el ADN recogido en la escena del crimen) - Finalmente vienen las secuencias de ADN de varios sospechosos. - El archivo puede venir con comentarios, los que empiezan con el carácter #. - Las lineas que comienzan con las letras A,C,G,T y el guión corresponden a los datos de la matriz, la linea que comienza con el numero 0 corresponde a la evidencia, y las lineas que comienzan con un número mayor o igual 1 corresponden a los ADN de los sospechosos.

El siguiente es un ejemplo de archivo de entrada:

1
2
3
4
5
6
7
8
9
10
11
12
13

# Matriz
A:5,-1,-2,-1,-3
C:-1,5,-3,-2,-4
G:-2,-3,5,-2,-2
T:-1,-2,-2,5,-1
-:-3,-4,-2,-1,*
          # Evidencia
0:AGTGATG
          # ADN Sospechosos
1:AAATGC
2:AGGAA
3:AGTGATA
4:GATTACA

El programa debe entregar como resultado el número del sospechoso cuyo ADN se parece más al de la evidencia.

En este caso, con el archivo de entrada mostrado anteriormente la salida del programa debe ser:

El culpable es el sospechoso número 3 (AGTGATA).

Opcionalmente el programa puede mostrar los alineamientos y el puntaje de alineamiento, pero no es necesario para participar (aunque si hay un empate, el programa con más “features” tiene más “puntos”).

Ganará el programa que se demore el menor tiempo en calcular el culpable. En caso de haber empate, o tener tiempos muy similares, se calculará el valor E de acuerdo a las métricas de Halstead.

El premio por este desafío será una Giftcard Amazon de 40 dólares la que se entregará sólo si participan 8 o más concursantes.

El código fuente de los programas debe estar disponibles en un repositorio público GitHub o Bitbucket, no se aceptarán programas entregados en otro medio.

Que empiece la competencia, y que gane el “más mejor”, el ganador se determinará el día 1 de mayo.

RESULTADO FINAL: (NOTA del 21 de febrero) Se cumplió el plazo final ofrecido el 15 de febrero. Gracias a Cristóbal Leiva, Israel Leiva y Tomás Hermosilla, por seguir participando. Los programas mejoraron bastantes, y la verdad es que no me gusta dejar este desafío sin ganador.

Por un lado el programa de Cristobal mejoró bastante, y pasa la segunda prueba. Los programas de Israel y Tomás también, aunque aún tienen problemas con condiciones de borde en el manejo de strings.

Debo admitir que el manejo de strings complica más de lo necesario el desafío, así que para revertir esta situación he decidido entregar igual el premio a Cristobal, que escribió el mejor programa de acuerdo a los requisitos, es decir, es el que tiene el menor valor para E de acuerdo al ranking que aparece más abajo.

Así que felicitaciones a Cristóbal, y a los demás gracias por participar. Los espero en nuevos desafíos.

ATENCIÓN: (NOTA del 15 de febrero) Debido al comentario de Cristóbal Leiva se hizo una corrección en la gramática de mi reconocedor ANTLR, pueden revisar el cambio acá. Esto implica un ajuste en el valor de E para algunos participantes, pero no alteró el ranking, ver los ajustes más abajo).

Bien, se cumplió el plazo para responder al desafío de enero: “Las Métricas de Halstead”. Al parecer estuvo más complicado de lo que esperaba. Finalmente sólo se presentaron 7 participantes, por lo que, lamentablemente, no tendremos premio :( …

Pero… con el fin de estimularlos, y animarlos a que participen en el desafío que viene (en marzo), voy a hacer una excepción, y dado que sólo falto un participante, vamos a tener premio de Gift Card Amazon por 30 dólares en esta oportunidad!!

Los participantes son:

• Manuel Ortega (mannungo) con una solución en php.
• Aldrin Martoq (aldrinmartoq) con una solución en ruby.
• Tomás Hermosilla (thermosilla) con su solución en python 3.
• Cristóbal Leiva (cleiva) con su participación en PHP.
• Daniel Martinez (edmt) con una solución en python.
• Israel Leiva (ileiva) con su solución en perl.
• Rodrigore Campos (rodrigore) con la última participación en ruby.

Para medir el esfuerzo de implementación (E) usé este programa en ANTLR. Para los que no lo conocen, ANTLR es una herramienta para generar compiladores (o parsers). Por razones de tiempo no voy a explicar como funciona mi programa, pero ahí está disponible para que lo analicen y me manden sus observaciones.

A continuación va el ranking en función del valor E, recuerden que las reglas decían que ganaría aquel programa con el menor valor para E. Sin embargo, el programa debe funcionar correctamente, así que primero vamos a ordenar a los participantes por el valor E, y luego iremos ejecutando sus programas para verificar que estén correctos. Sólo voy a ejecutar el programa con menor valor E, si este funciona adecuadamente para los archivos de prueba, entonces ganará inmediatamente, sino continuaré con el siguiente de la lista.

Ranking

(Se hizo un ajuste en el ranking de algunos participantes debido a la observación de Cristóbal Leiva, ver [este comentario])

1. cleiva: E=5.101,61

2. mannungo: E=8.437,93

3. thermosilla: E=9.729,20 // E=8.716,17

4. aldrinmartoq: 10.990,32 // anterior E=10.963,06

5. rodrigore: E=13.036,08 // anterior E=13.278,09

6. ileiva: E=32.833,86 // anterior E=33.844,43

7. edmt: E=34.034,31

8. lnds: E=83.483,11 // anterior E=83.285,76

Evaluación

Los archivos de prueba son:

• fuente1.test: este archivo es el ejemplo mencionado en el desafío. Hay que notar que la lista de operadores es distinta, así que los valores esperados no son los mismos.

• Halstead.g4: esta es mi solución en Antlr 4.

• ileiva.pl: Perl tiene algunas particularidades bien especiales con respecto a las expresiones regulares, la idea es ver que tal se manejan con este lenguaje.

• edmt.py: Este programa en python tiene strings con triple comillas (“”“), es interesante observar cómo maneja esa condición cada programa.

El archivo de operadores definitivo es el siguiente:

• operadores.txt

Resultados

Probé primero el programa de Cristobal, que es el que tiene el menor valor para E.

Este es el resultado de las pruebas:

Programa: cleiva.php

1. fuente1.test: Calcula perfecto el valor de E: 115,64.
2. Halstead.g4: calcula correctamente n1 y N1, pero falla al evaluar n2, y N2, con lo que el valor de E difiere de lo esperado. n2 debería ser 199, y N2 debería ser 443, sin embargo el programa de Cristóbal calcula n2 como 197 y N2 como 441. La diferencia se debe a que mi programa considera esta secuencia \r\n\t como 3 tokens distintos, en cambio el programa cleiva.php lo considera como una sóla secuencia de 6 caracteres. Lo que está incorrecto, ¡prueba no superada!

Así que pasamos al siguiente participante.

Programa: mannungo.php

1. fuente1.test: Acá nos fue mal :(, por alguna razón obtengo una división por cero en la linea 18 y un mensaje “unknown modifier” en las lineas 8 y 12. Así que mannungo, espero que me expliques en los comentarios que pasó. ¡prueba no superada!

Pasamos al siguiente participante en el ranking.

Programa: thermosilla.py

1. fuente1.test: Calcula perfecto E y los otros valores.
2. Halstead.g4: Los valores para n1 y N1 no coinciden, claramente hay un problema con las expresiones regulares. n1 debería ser 14, pero arroja 8, y N1 debería ser 248 pero calcula 108. No reconoce los símbolos >, <, @, $, ~, *. ¡Prueba no superada!

Vamos al cuarto participante.

Programa: aldrinmartoq.rb

1. fuente1.test: sin problemas.
2. Halstead.g4: prueba no superada. Problemas con n1 y N1, calcula 9 y 102 respectivamente, tampoco reconoce >, <, @, $ y ~. ¡Prueba no superada!

Veamos cómo le va al quinto partecipante:

Programa: rodrigore.rb

1. fuente1.test: prueba superada.
2. Halstead.g4: falla al no reconocer el operador ~.

Esto salió bastante difícil para nuestros concursantes, vamos al sexto participante:

Programa: ileiva.pl

1. fuente1.test: en este caso el programa lleva el consumo de la cpu al tope, y después de varios minutos sin avanzar decidí detenerlo. Así que Israel, espero en los comentarios tus indicaciones para ver como lo puedo probar.

El último participante:

Programa: edmt.py

1. fuente1.test: sin complicaciones
2. Halstead.g4: falla al calcular n1, lamentablemente este programa no entrega la lista de operadores, así que no puedo indicar donde está el error.

¡Y el ganador es!

–Bueno, ¡hasta el momento no hay ganador! :( – Cristóbal Leiva (ver nota del 21 de febrero al inicio de este post).

¡Felicitaciones Cristóbal! Me contactaré contigo en los próximos días.

–A menos que antes de 5 días alguno de los participantes entregue un programa que supere las pruebas. ¡Ah! y si no has participado, y crees que puedes superar a los finalistas puedes intentarlo también, de todas maneras tendrá preferencia cualquiera de los otros 7 finalistas, pero puedes intentarlo…–

Ha llegado la hora de empezar los desafíos de este año. La meta es prepararse para el gran desafío de octubre, que tendrá un premio especial y que llamaremos el Premio DMW (como homenaje póstumo a nuestro colega Daniel Molina Wegener).

Este primer desafío es bien especial, porque nos servirá para construir la herramienta que nos permitirá medir a los futuros participantes.

Se trata de las métricas de Halstead.

Mis disculpas por la demora en publicar el resultado del desafío de diciembre, se suponía que serían dos semanas, pero el fin de año estuvo intenso. Pero ya retomamos, y con un cambio de look.

Este blog ahora está siendo generado usando octopress, y todo su contenido quedará disponible en este repositorio github

Este ejercicio es un calentamiento para los ejercicios que vendrán y los desafíos que tendremos el próximo año.

Recordemos que los números de Fibonacci se definen como la secuencia de números que se construyen de la siguiente manera:

Fib(1) = 1

Fib(2) = 1

Fib(3) = 2

Fib(4) = 3

Fib(i) = Fib(i-1)+Fib(i-2)  (para i>= 3)

Es decir, cada número de fibonacci es la suma de los números previos de Fibonacci.

Probablemente tu jefe, y mi jefe, sin ser informáticos, ni programadores sean mejores programadores funcionales que tu mismo, claro, porque es probable que ellos utilicen uno de los lenguajes funcionales más populares que existen: Excel.

Sí, Excel, ese que usan muchos de tus colegas no informáticos, soporta perfectamente el paradigma funcional.

Daniel Molina dejó este mundo este lunes, de forma inexplicable, este joven brillante ya no estará con nosotros.

Daniel era un programador extraordinario, que nos regaló probablemente su último post, que salió publicado este domingo en este mismo sitio.

Qué es la programación funcional.

Daniel era brillante, y ganó desafíos, de hecho participaba activamente resolviendo algunos de los desafíos que planteamos.

Su trabajo en estos desafíos está en este repositorio GitHub, de hecho me he encargado de clonar ese repositorio en particular, ante la eventualidad de que desaparezca dada su partida.

En particular su trabajo en el desafío de Octubre es notable, a pesar de que el problema tenía una solución sencila, y pretendía medir otra cosa, él fue más allá, esta imagen muestra el análisis que estaba haciendo para parsear programas en Fortran IV, este grafo se genera a partir de su analizador del código recibido en la entrada:

No sólo hemos perdido a una gran mente, a un gran programador y hacker, también a una buena persona, por lo poco que pude conocerlo, y por el testimonio de los que lo conocieron.

Humildemente, este espacio mantendrá su nombre, los desafíos volverán, y una vez al año entregaremos el premio Daniel Molina Wegener al mejor competidor, si me ayudan podemos hacer algo muy bonito y conmemorativo por él. Veré la manera de conseguir un premio adecuado que honre su memoria. Ustedes pueden honrarlo participando o promoviendo la participación entre sus amigos programadores o hackers. Estoy seguro que el sonreiría feliz con la idea.