Origen (Inception)

8 August 2010 at 21:31

Ayer Kiko y yo fuimos a ver la última película de Christopher Nolan, el thriller de ciencia ficción “Origen“, en la que nos sumerge en la surrealista física de los sueños donde todo es posible:

DiCaprio es un agente dedicado al espionaje industrial que se introduce en los sueños de sus víctimas para hacerse con sus secretos cuando son más vulnerables. Recibirá el encargo del que podría ser su último trabajo, pero en esta ocasión consistirá en introducir una idea en el subconsciente de su víctima.

Seguramente muchos de vosotros hayáis visto otras películas de este director como “Memento“, “Batman Begins” o “El caballero oscuro“. En esta película vuelve a sorprendernos jugando con el tiempo, arquitecturas imposibles y tramas con varios niveles de profundidad, que pueden llegar a dejarte algo cansado mentalmente, pero cuya originalidad se agradece tras una larga temporada de precuelas, secuelas, adaptaciones y remakes. Igual le sobra un poco de acción pero indudablemente es la mejor película de ciencia ficción desde hace bastante tiempo.

Imprescindible.

Como afecta el algoritmo al rendimiento (o resolviendo una pregunta de Google)

11 April 2010 at 16:35
Comments Off

Tras nueve meses de sequía bloguera, vuelvo con un post bastante parecido al de “Exponenciación modular” (uno de los que más visitas tiene) que toca uno de los temas que me apasionan: el rendimiento de los algoritmos. Hace bastantes meses leí, via meneame, un post con 140 preguntas que (supuestamente) Google puede hacerte en una entrevista de trabajo. Una de esas preguntas me llamó la atención, tanto que unos cuantos compañeros del trabajo la estuvimos comentando. Te pedían que escribieras un algoritmo muy simple:

Dado un array A[N] de N números. Tienes que generar un array Ouput[N] de manera que Output[i] sea la multiplicación de todos los elementos de A[N] excepto A[i]. Por ejemplo Output[0] será la multiplicación desde A[1] hasta A[N-1] y Output[1] sera la multiplicación de A[0] y desde A[2] hasta A[N-1]…

En ruby es tan sencillo como:

n = A.length
Ouput = Array.new(n) do |i|
  result = 1
  n.times { |j| result *= A[j] unless j == i }
  result
end

El problema es que la pregunta continuaba con:

… hazlo en O(n) …

Ups, hay que repensarlo ya que el algoritmo anterior tiene dos bucles sobre N anidados por lo que es O(n2). Se me ocurrió hacerlo precalculando el producto de todos los elementos de A[N] y hacer que Output[i] = Total / A[i]. Así queda O(n).

product = A.inject(1) { |total, n| total * n }
Output = A.collect { |n| product / n }

Pero faltaba un último detalle de la pregunta:

… sin el operador de división.

Uff, ahora se pone interesante. Tras pensarlo un poco y escribir Ouput como una matriz de los elementos a multiplicar, ví un patrón que me podía servir. La matriz está formada por dos “triángulos” (perdón si el termino no es correcto. Hay algún matemático entre la audiencia?) que llamaremos L, resaltado en azul, y R, en rojo.

Output[0]   = [   1, A[1], A[2], ..., A[N-1]]
Output[1]   = [A[0],    1, A[2], ..., A[N-1]]
Output[2]   = [A[0], A[1],    1, ..., A[N-1]]
...
Output[N-1] = [A[0], A[1], A[2], ...,      1]

Se me ocurrió que esos dos “triángulos” o productos parciales se podían calcular a la vez en un único bucle para usarlos posteriormente para calcular Ouput[i] = L[i] * R[i] ya que:

  • L[i] = L[i-1] * A[i-1] para i > 0 (L[0] = 1)
  • R[i] = R[i+1] * A[i+1] para i < N-1 (R[N-1] = 1)
n = A.length
left,right = Array.new(n, 1), Array.new(n, 1)
1.upto(n-1) do |i|
  left[i]        =  left[i-1] * A[i-1]
  right[n-(i+1)] = right[n-i] * A[n-i]
end
Output = Array.new(n) { |i| left[i] * right[i] }

Bien, creo que al final lo hemos conseguido. Un algoritmo O(n) que no usa la división y que calcula los resultados según la formula indicada. Además, el algoritmo que usa la división tiene un problema: necesita que los elementos de A[N] sean números naturales (es decir, que no puedan ser 0) mientras que los otros dos algoritmos no tienen esta restricción.

Si os estáis preguntando si realmente hay diferencia de rendimiento entre los tres algoritmos (principalmente el primero versus los otros dos), aquí tenéis un gráfico que lo demuestra.

Como se puede ver, a medida que el tamaño del array A[N] crece los tiempos del primer algoritmo (double loop) crecen exponencialmente mientras que los otros dos (division y triangles) tienen un comportamiento lineal. Por tanto, si que hay diferencia, y mucha.

Los datos de benchmarking para generar el gráfico con el OpenOffice.org Calc los he obtenido he usado el siguiente script que genera CSV.

#! /usr/bin/env ruby
require 'benchmark'
 
def double_loop(input)
  n = input.length
  Array.new(n) do |i|
    result = 1
    n.times { |j| result *= input[j] unless j == i }
    result
  end
end
 
def division(input)
  product = input.inject(1) { |total, n| total * n }
  input.collect { |n| product / n }
end
 
def triangles(input)
  n = input.length
  left,right = Array.new(n, 1), Array.new(n, 1)
  1.upto(n-1) do |i|
     left[i]       =  left[i-1] * input[i-1]
    right[n-(i+1)] = right[n-i] * input[n-i]
  end
  Array.new(n) { |i| left[i] * right[i] }
end
 
t = 1_000
max_size  = 250
step_size = 10
 
step_size.step(max_size, step_size) do |n|
  input = Array.new(n) { rand(100) + 1 }
  t1 = Benchmark.realtime { t.times { double_loop(input) } }
  t2 = Benchmark.realtime { t.times { division(input) } }
  t3 = Benchmark.realtime { t.times { triangles(input) } }
  puts "#{input.length};#{t1};#{t2};#{t3}"
end

Por cierto, si a alguién se le ocurre otro algoritmo que lo ponga en los comentarios.

Actualización automática de los plugins de WordPress por SSH

11 July 2009 at 17:09
Comments Off

Las versiones recientes de WordPress te permiten actualizar los plugins instalados con un simple click. Aunque interesante, nunca había usado esa funcionalidad porque requería tener instalado y configurado un servidor FTP o FTPS. Y, la verdad, me daba mucha pereza tener que mantener un servicio sólo para esto.

Pero hoy, tras actualizar a la versión 2.8.1, por casualidad he lanzado un grep en un directorio que no tocaba y he descubierto el fichero wp-admin/includes/class-wp-filesystem-ssh2.php. Resulta que WordPress también puede usar SSH para realizar esas actualizaciones. Normalmente esa opción no aparece por que no disponemos de todo el software necesario para que funcione, pero es bastante sencillo conseguirlo. Veamos como hacerlo en una Debian:

$ sudo aptitude install libssh2-1 libssh2-1-dev php5-dev
$ sudo pecl install -f ssh2
$ sudo vi /etc/php5/conf.d/ssh2.ini
    extension=ssh2.so
$ sudo /etc/init.d/apache2 restart

Una vez tenemos instalada la extensión ssh2.so de PHP, podemos desinstalar los paquetes de desarrollo que instalamos en el primer paso.

$ sudo aptitude remove libssh2-1 libssh2-1-dev php5-dev

Listo, ya podemos actualizar los plugins desde la comodidad de nuestro navegador sin necesidad de tener un servidor FTP o FTPS. Seguramente también se puede usar para actualizar el propio WordPress, aunque no lo puedo confirmar ya que yo lo actualizo usando subversión.

Como se puede ver es bastante sencillo. De todas formas, os dejo un screencast que he hecho sobre la instalación (inaugurando mi cuenta de YouTube).

¿A que os recuerda este anuncio?

24 June 2009 at 10:00

Hace unos días, mientras conducía por Palma, al pararme en un semáforo en rojo tras uno de los autobuses de la EMT vi el siguiente anuncio del ayuntamiento en su parte trasera y me recordó a algo. ¿Y a vosotros? Si ponéis el cursor sobre la imágen, veréis a que me refiero. :-D

Campaña "He crescut" del Ayuntamiento de Palma

Ya tengo los DVD de la 1ª temporada de “The Big Bang Theory”

23 June 2009 at 22:18

DVDs de la primera temporada de "The Big Bang Theory"

Como comenté ayer en twitter, hoy se han puesto a la venta en España los DVDs de la primera temporada de la serie “The Big Bang Theory” y me ha faltado tiempo para ir a comprármela. Es una serie genial. La mejor comedia que he visto en mucho tiempo.

Para aquellos que todavía no la conozcan, aunque eso querría decir que no habéis leído mi post al respecto de hace unos ocho meses ;-) , es una seríe producida por la CBS que nos muestra las vivencias de cuatro científicos/geeks  con gran cociente intelectual pero escasas aptitudes sociales (y que, entre otras cosas, juegan al Scrabble Klingon) que conocen a la nueva y atractiva vecina que se acaba de mudar a Los Angeles en busca de una carrera como actriz. La interacción de esos dos mundos tan diferentes provocan situaciones francamente hilarantes.

Para que os hagáis una idea de  la serie, os remito a YouTube. Y si estais en Facebook, os podéis hacer fans.

Post número 100

11 June 2009 at 11:00

Post #100

Aunque no soy muy dado a las celebraciones (por no celebrar, casi no celebro ni mis cumpleaños :-) ) he pensado que estaría bien aprovechar la publicación del post número 100 para recapitular un poco lo que ha sido la irregular historia de este blog hasta el momento.

El prímer artículo es de mediados de octubre del 2004, es decir, que en unos cuatro meses el blog cumplirá ya cinco años (jo, como pasa el tiempo), y significa que, de media, he publicado un post cada aproximadamente dos semanas y media. Pero la verdad es que he tenido grandes altibajos motivados por mi estado de ánimo. Pero a pesar de esa irregularidad en la publicación, hay cerca de 200 comentarios, una media de dos por artículo., y eso me ha hecho mucha ilusión. ¡Hay gente que lee mi blog!

En cuanto a visitas, según Google Analytics, tengo una media de unas 35 visitas diárias, viniendo casí todas ellas de buscadores que suponen unas 50 páginas vistas al día, siendo las más visitadas (si obviamos la página de inicio) los post de Velocidad de obturación y apertura, Nudos de corbata y exponenciación modular, cosa que encaja con las frases más usadas en los buscadores para llegar a mi web. Pero me apena un poco que ninguno de mis recientes posts técnicos estén en el top-10.

No se puede decir que sean unos grandes números (sé que si pusiera publicidad no me haría a hacer rico, pero no es esa la intención de este blog) pero me ha hecho ilusión recopilar y analizar ligeramente todos estos datos.

Espero algún día llegar a los 200.

Coraline

8 June 2009 at 16:00
Comments Off
Coraline

Portada del libro "Coraline"

Aprovechando el reciente estreno de la adaptación cinematográfica [IMDb][Trailer], dejadme que os presente “Coraline“: una historia de fantasía cuasi onírica en la que Coraline, una niña de 14 años que se acaba de mudar, descubre en su nueva casa un pasadizo que la llevará a otra casa increíblemente parecida a la suya pero en la que viven otros padres muy cariñosos, que le prestan toda la atanción, que quieren que se quede con ellos para siempre y que tienen botones por ojos. Pronto se dará cuenta que no todo es tan bonito como parece…

El autor del relato es Neil Gaiman quien, como ya he comentado en alguna ocasión, es uno de los escritores contemporáneos de fantasía que más me gustan. Otras obras suyas son los libros “American Gods” y “Los hijos de Anansi“, el afamado cómic “The Sandman” y la novela gráfica “Stardust“, también convertida en film.

Algo que comparten la mayoría de sus obras son su atmósfera lúgubre, como de penumbra, y unas historias que te enganchan desde el primer momento y “Coraline” no es diferente. Aunque está publicitada como lectura a partir de los 12 años no desmerece la lectura por un adulto. Y, a pesar de los momentos algo oscuros que podrían asustar a los jóvenes más sensibles, tiene cierta moraleja en la historia que no estaría mal que conocieran. En resumen, un libro entretenido de lectura fácil que os recomiendo a todos.

El libró lo editó Salamandra en el 2003 pero todavía se puede encontrar en varias librerías online. También está disponible en catalán de la mano de editorial Empuries.

Como anécdota, Gaiman ha comentado en alguna ocasión que el título viene de un error tipográfico de  Caroline que le ocurrió accidentalmente.

Por cierto, me apetece mucho ir a ver la película (cuya ambientación me recuerda exageradamente a “Pesadilla antes de Navidad“) en 3D algún día de estos. ¿Se apunta alguién?

Firmas DKIM con Postfix y Amavis

6 June 2009 at 17:57

Hace bastantes meses escribí un artículo sobre como configurar el SpamAssassin para que verifique las firmas DKIM para luchar contra el Spam y me quedó pendiente explicar como firmar nuestros própios correos. Por aquel entonces era más o menos complicado pero desde la release de Debian Lenny, que incluye el paquete amavisd-new 2.6.1, la tarea se ha simplificado.

Voy a dar por sentado que tenemos un Postfix instalado y configurado para que use el Amavis para las funciones de anti-virus y anti-spam. Si no es así, te recomiendo que leas el excelente artículo de Jaume Sabater.

El primer problema lo tenemos si el mismo servidor está actuando como MX y como servidor SMTP para nuestros usuarios: Amavis firmaría tanto los correos de nuestros usuarios como los que le llegan en su función de MX, y no es lo que queremos. Por tanto, lo primero es separar esas dos funciones (MX y submission) en el Postfix añadiendo las siguientes líneas en /etc/postfix/master.cf (seguramente ya haya algo parecido pero comentado)

1
2
3
4
5
submission inet n       -       n       -       -       smtpd
-o smtpd_enforce_tls=yes
-o smtpd_sasl_auth_enable=yes
-o smtpd_client_restrictions=permit_sasl_authenticated,reject
-o content_filter=smtp-amavis:[127.0.0.1]:10026

Con estas líneas estamos indicándole al Postfix que también escuche por el puerto de submission (587/tcp), que por ese puerto sólo acepte correo de conexiones autentificadas y cifradas por TLS, y que debe enviar los correos recibidos al Amavis usando el puerto 10026 (mientras que el resto se seguirá enviando por el puerto 10024). Con esto conseguiremos que Amavis distinga y trate de forma diferente los correos de los usuarios.

Lo siguiente es hacer que Amavis también escuche por el puerto 10026 y hacer que firme los correos que le lleguen por ese puerto. Lo haremos añadiendo al fichero /etc/amavis/conf.d/50-user:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
$inet_socket_port = [10024, 10026];
 
$interface_policy{'10026'} = 'AUTH';
 
$policy_bank{'AUTH'}   = {           # Authenticated clients
os_fingerprint_method   => undef, # don't fingerprint authenticated clients
bypass_spam_checks_maps => [1],   # don't spam check authenticated clients
originating => 1,
#
# force MTA to convert mail to 7-bit before DKIM signing
# to avoid later conversions which could destroy signature:
smtpd_discard_ehlo_keywords => ['8BITMIME'],
};
 
$enable_dkim_signing = 1;
dkim_key('llull.net', 'personal', '/etc/dkim/llull.net.key.pem');

En la última línea le indicamos que para el dominio ‘llull.net‘ y el selector ‘personal‘ debe firmar los correos con la clave privada contenida en el fichero /etc/dkim/llull.net.key.pem. Para generar ese fichero ejecutaremos como root el comando

server:~# amavisd-new genrsa /etc/dkim/llull.net.key.pem
Private RSA key successfully written to file "/etc/dkim/llull.net.key.pem" (1024 bits, PEM format)

Ya sólo falta obtener y configurar en nuestro servidor DNS la clave pública y para ello disponemos de otro comando:

server:~# amavisd-new showkeys
personal._domainkey.llull.net.  3600 TXT (
"v=DKIM1; p="
"MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDoTaWXxsXpNi100Flp7fIKJSlZ"
"ptMP4aCCZjUFgT7TsWokWQJhnGUNnxexEqqPtCDbCUAvEg3iieMRrKwZoHAUDqCf"
"fvW9dcYR7+NdnaxAXCBpOh8Wg5GFJeIid9Gsx3ByBObBQnRGSMOxdBRBO4VXwGb2"
"hKAIOiBMPxaFghdDZQIDAQAB")

Y ya sólo falta añadir la salida del anterior comando a la zona de nuestro dominio en el servidor DNS. La salida está en formato Bind por lo que si usamos ese servidor DNS no tendremos más que añadir  ese texto en el fichero correspondiente.

Acordaos de reiniciar el Postfix, Amavis y Bind para que apliquen las nuevas configuraciones. Para comprobar que todo está funcionando correctamente, podemos enviar un correo a uno de los reflectores existentes.

Ahora ya no tenéis escusa para que vuestro servidor de correo no firme los correos salientes. Si os surge alguna duda, usad los comentarios. Aunque creo que me he acordado de todo, han pasado algunos meses desde que lo configuré y es posible que haya pasado algo por alto.

Artículo basado en la documentación oficial de Amavis.

All is full of love

27 May 2009 at 15:00
Comments Off

Hasta ahora nunca le había dedicado un post a nada relacionado con la música. Aunque, como a todo el mundo, me gusta, no es un tema que me apasione fuertemente. Pero hoy me ha apetecido comentaros el que, según mi parecer, es uno de los mejores vídeos musicales (sin menospreciar a la canción, que es el 50% del vídeo): “All is full of love” de Björk, publicada en el álbum Homogenic, y reversionada para el de grandes éxitos.

Para aquellos que no la conozcáis, Björk [wikipedia] es una cantante y compositora islandesa, que también ha hecho sus pinitos como actriz, con una voz muy particular. La verdad es que no es la típica voz de cantante, pero creo que encaja bastante bien con el tipo de música que realiza: difícil de definir.

El vídeo tiene ya sus años (finales de los ’90) pero no ha quedado en absoluto desfasado. De ambientación cyberpunk (supongo que por eso me gusta). muestra la elegante y delicada construcción de dos Björk robot que se enamoran, inmersas en un escenario muy industrial, muy high-tech, mientras suena una musica con ciertos toques orientales.

La verdad, como la descripción que he realizado no le hace justicia (por mucho que lo  intentara no creo que nunca llegara ha hacerlo) y si una imagen vale más que mil palabras entonces veinticinco por segundo valdrán muchas más, creo que lo mejor es que lo veáis y valoréis vosotros mismos. Ya me diréis que os parece.

Para los curiosos, os dejo el enlace al making of.

Optimizaciones en el blog

24 May 2009 at 22:58

Desde que Xisco me pidió consejo tras probar varias de sus páginas con YSlow tenía pendiente escribir este post. YSlow es un plugin para Firefox que analiza distintos aspectos que pueden afectar al rendimiento de páginas webs y realiza recomendaciones. Todos los aspectos que se tienen en cuenta giran alrededor del tiempo de carga de la web. No entran en temas como optimización de base de datos y otros aspectos internos del servidor.

De todas las reglas, las más sencillas de corregir son:

Otras reglas pueden suponer reescribir parte de la aplicación pero para solventar estas tres basta con añadir algunas líneas al final del .htaccess del directorio raíz de nuestra web. Hay que tener en cuenta que los modulos necesarios deben estar instalados y la configuración del servidor nos debe permitir establecer esta configuración (directiva AllowOverride)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Add Expires Header
<IfModule mod_expires.c>
ExpiresActive on
ExpiresByType image/gif "access plus 1 week"
ExpiresByType image/jpeg "access plus 1 week"
ExpiresByType image/png "access plus 1 week"
ExpiresByType text/css "access plus 1 week"
ExpiresByType application/javascript "access plus 1 week"
</IfModule>
 
# Compress CSS files
<IfModule mod_deflate.c>
AddOutputFilterByType DEFLATE text/plain text/html text/xml application/rss+xml application/atom_xml
AddOutputFilterByType DEFLATE text/css application/javascript
</IfModule>
 
# ETag only use file time and size, but no inode
FileETag MTime Size

En las líneas 2 a 9 configuramos que las imágenes, hojas de estilo y javascripts tengan una fecha de expiración de una semana a partir del momento en que se ha visitado la página web. Esto significa que el navegador del usuario usará la copia local (fichero cacheado) durante una semana. Este comportamiento puede suponer un problema si tenemos ficheros de estos tipos que vamos modificando sin cambiarle el nombre (p.e. un banner) ya que los navegadores de algunos de los usuarios mantendran las versiones antiguas.

Desde la 12 a la 15 configuramos la compresión de las páginas HTML, feeds (text/xml, application/rss+xml y application/atom_xml), hojas de estilo y javascripts. De esta forma conseguimos ahorrar tráfico (importante si estamos en un hosting con limitaciones de tráfico)  y que el tiempo de transmisión sea menor.

Finalmente, en la última línea configuramos los ETags generados por el propio servidor Apache para los ficheros estáticos. Por defecto, Apache tiene en cuenta tres aspector para generar el ETag: el inodo, fecha de modificación y tamaño. Pero se recomienda no usar el inodo para generarlo ya que si nuestra web empieza a ser conocida y tenemos que distribuir la carga entre varios servidores, es muy poco probable que un fichero tenga el mismo inodo en todos los servidores de la granja. Entonces, el ETag variaría en funcion del servidor que lo generara por lo que no se sacaría provecho a esta cabecera. Para resolverlo, configuramos el Apache para que genere el ETag sólo considerando la fecha de modificación y el tamaño del fichero.

Con esta simple configuración yo conseguí pasar de una puntuación de 74 a 89.

A medida que pueda escribiré algún post más sobre optimización web y como resolverlo en el caso concreto de un blog que usa WordPress.