domingo, 25 de marzo de 2012

Generar UUIDs aleatorios con sólo 111bytes de javascript

Introducción

Hoy vamos a ver un ejemplo de código diminuto que genera UUIDs aleatorios en el que se están aplicando muchos trucos y lecciones de javascript.  Primero introduciré el concepto de UUID para quien no lo tenga claro y luego desarrollaré el código.

Lo interesante de este diminuto código es analizar como evolucionó desde sus orígenes hasta la versión definitiva. Este código fue publicado en 140byt.es, aunque siguió cambiando tras su publicación.

La idea original es de Jed Schmidt (@jedschmidt , http://who.jed.is/ ) y fue mejorada gracias a las contribuciones de github:subzey, github:LeverOne y github:tsaniel

Vamos a hacer un uso importante de la función String.replace de javascript, así que te recomiendo que la repases en https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/String/replace sobre todo  la sección "Specifying a function as a parameter".

UUID

UUID es el acrónimo de Universally Unique Identifier o Identificador Universal Único y se trata de un estándar en software publicado por la Open Software Fundacion (OSF).

El objetivo que persiguen los UUIDs es permitir a sistemas distribuidos identificar información de forma única sin que sea precisa una coordinación central. En este contexto, la palabra única significa realmente "prácticamente única" más que "garantizadamente única". Dado que los identificadores tienen un tamaño finito es posible que dos elementos distintos compartan identificador. El tamaño y proceso de generación del identificador se seleccionan de manera que en la práctica las colisiones de identificadores sean suficientemente improbables. De esta forma, cualquiera puede crear un UUID y utilizarlo para identificar un elemento con la confianza razonable de que ese identificador no será generado de forma involuntaria por quien necesite identificar otro elemento. Esto permite que la información etiquetada con UUIDs se puedan combinar en una base de datos sin necesidad de resolver conflictos de identificadores.

Un UUID es un número de 16 bytes. En su forma canónica, un UUID se representa por 32 dígitos hexadecimales, separados en cinco grupos por guiones, en la forma 8-4-4-4-12, como por ejemplo: 550e8400-e29b-41d4-a716-446655440000.

En total hay  340,282,366,920,938,463,463,374,607,431,768,211,456 combinaciones para los UUIDs, casi nada :) .

En la forma canónica del UUID hay dos posiciones relevantes: xxxxxxxx-xxxx-Mxxx-yxxx-xxxxxxxxxxxx. Los bits más importantes de y indican la variante y para la especificación los dos bits más importantes deben tener los valores 1 0, con lo que los valores hexadecimales válidos para y son 8, 9, a y b.  Dentro de la variante cubierta por la especificación de la UUID hay cinco versiones que se identifican por el valor de M. Estas versiones son:

  • Direcciones MAC M = 1
  • DCE Security. M = 2
  • MD5 Hash. M = 3
  • UUIDs aleatorios. M = 4. Este es el que interesa en este caso, por lo que el formato del UUID será de la forma xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx, donde y valdrá 8, 9, a o b, como ya hemos comentado.
  • SHA-1 Hash. M = 5
Implementación

El inicio

La primera versión y más fácil de entender:
function() {
  return
    "00000000-0000-4000-8000-000000000000"
    .replace(
      /0/g,
      function() {
         return(
           0 |
           Math.random() * 16 
         ).toString(16)
      }
    )
}

Vemos tres importantes elementos. Primero, tenemos la plantilla del UUID. Segundo, la expresión regular para seleccionar las posiciones con cero que deben reemplazarse por números aleatorios (/0/g) y, por último, la función que genera cada caracter hexadecimal aleatorio. En esta función es reseñable el truco para generar un entero entre 0 y 15.

Math.random()*16 genera un número aleatorio entre 0 y 16, con bastantes decimales. Para conseguir de manera rápida utilizamos la expresión (0|x). Esta expresión devuelve la parte entera de x, es equivalente a aplicar Math.floor. A continuación, obtenemos la expresión hexadecimal del entero con un .toString(16)

Compactar la plantilla

En la siguiente iteración se compacta la plantilla del UUID.

(         
    "" +         // concatenamos como cadena:
    1e7 +        //  10000000 +
    -1e3 +       // -1000 +
    -4e3 +       // -4000 +
    -8e3 +       // -80000000 +
    -1e11        // -100000000000,
)

Es decir, comparando las dos alternativas de plantilla se observa una clara reducción de longitud:

"00000000-0000-4000-8000-000000000000"
(""+1e7+-1e3+-4e3+-8e3+-1e11)  //10000000-1000-4000-8000-100000000000

Claro, que ahora la plantilla, traducida a cadena tiene unos y ceros que hay que modificar, con lo que toca cambiar la expresión regular agregando dos caracteres más de /0/g a /1|0/g

De momento el código ya va así:

function(){return(""+1e7+-1e3+-4e3+-8e3+-1e11).replace(/1|0/g,function(){return(0|Math.random()*16).toString(16)})}

Recursión

Mirando el código vemos que function aparece un par de veces y esto igual se puede reducir. Para ello, nos ayudamos de la recursión. La idea es utilizar el replace y en su segundo parámetro llamar de nuevo a la función. Luego los pasos son:

  1. Demos un nombre a nuestra función
  2. Apoyándonos en el segundo parámetro de replace llamaremos a nuestra función
  3. Ahora, nuestra función necesita de un parámetro que le proporcionará replace.
  4. Cambiamos la lógica de la función. Si recibe un parámetro es que se invoca desde el replace y ejecutamos la generación del número aleatorio y si no viene informado dejamos continuar con ejecutando el replace de la plantilla del UUID.
Es decir, deberíamos obtener algo como el siguiente código anotado.

function b(
  a                  // contenedor
){
  return a           // si se pasa el parametro
    ? (              // se devuelve
      0 |            // entero
      Math.random()  // aleatorio
      * 16           // entre 0 to 15
      ).toString(16) // en formato hexadecimal
    : (              // en caso contrario
      "" +           // la cadena concatenada:
      1e7 +          // 10000000 +
      -1e3 +         // -1000 +
      -4e3 +         // -4000 +
      -8e3 +         // -80000000 +
      -1e11          // -100000000000,
      ).replace(     // reemplazando
        /1|0/g,      // unos y ceros con
        b            // dígitos hex aleatorios
      )
}


La versión compacta, con un ahorro de diez bytes, quedaría así:
function b(a){return a?(0|Math.random()*16).toString(16):(""+1e7+-1e3+-4e3+-8e3+-1e11).replace(/1|0/g,b)}


Byte a byte

Como cada byte cuenta, ahora toca otro truco para ahorrar un solo byte. Para poder generar la plantilla del UUID hemos utilizado esta expresión:

""+1e7+-1e3+-4e3+-8e3+-1e11

Hemos utilizado el ""+ para forzar la concatenación de los números. Para poder ahorrar un byte nos apoyaremos en la característica que tienen los arrays de realizar un toString implícito al sumarle otro elemento. Es decir, lo dejaremos así:

[1e7]+-1e3+-4e3+-8e3+-1e11

Acabamos de ahorrar algo más de un 1% de código.

La funcionalidad incompleta

No sé si has caído en la cuenta, pero hasta ahora no lo hemos hecho bien del todo. El UUID debe tener el formato xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx, donde y valdrá 8, 9, a o b y, sin embargo, lo que está ocurriendo es que "y" siempre vale 8. Para completar el código este volverá a crecer. Como se suele decir: un pasito pa lante, dos pasitos pa trás.

Lo primero es localizar el 8 en la plantilla para trabajar con él. Para ello lo inmediato sería utilizar algo como /0|1|8/g en la expresión regular. A continuación, tendremos que distinguir el ocho del cero y del uno, pero si revisas la documentación de replace, podemos anticipar esta distinción en la propia expresión regular escribiéndola así: /0|1|(8)/g

Entonces, si cambiamos la definición de la función de b(a) a b(a,c), resultará que el parámetro c vendrá informado a null o a 8, con lo que tenemos la palanca para poder discriminar.

Ahora vamos a complicarnos un poco la vida, que remedio.

Si se trata de reemplazar un 1 o un 0, no hay que hacer nada, pero si se trata del 8, hay que hacer lo siguiente:
  1. Generar un número aleatorio entre 0 y 3
  2. Sumarle 8
  3. Pasarlo a hexadecimal
Vamos a intentar reaprovechar lo máximo posible, por lo que nos apoyaremos en el Math.random y el toString(16).

Para el primer paso, ¿cómo generar el aleatorio adecuado? Con el siguiente código:
Math.random() * 16 >>  c / 4

Analicemos las posibilidades:
  1. c = undefined. Es equivalente a c = 0, con lo que se genera un aleatorio entre 0 y 16, y se hace un shift a la derecha de cero bits, o sea, que se conserva la parte entera.
  2. c = 8. Sobre el aleatorio hacemos un shift a la derecha de dos bits, con lo que reducimos el valor a la cuarta parte, conservando un valor entre 0 y 3. Esto se debe a que el valor original en su forma binaria estaría entre 0000 y 1111 y si hacemos dos shifts a la derecha, el rango en su forma binaria quedará siempre entre 0000 y 0011, es decir, entre 0 y 3 como habíamos dicho. Ya tenemos la primera parte resuelta.
Para el segundo paso nos apoyamos en el "OR".

( c | Math.random() * 16 >>  c / 4 )

Si c = 8, estamos haciendo un OR entre 1000 del 8 y el 00xx del doble shift, el resultado es un valor entre 1000 y 1011 que es lo mismo que entre 8 y 11, o expresándolo de forma hexadecimal uno de 8, 9, a o b.


Recomponiendo el código quedaría así:
function b(
  a,                 // contenedor
  c                  // 8 o undefined
){
  return a           // si se pasa el parametro
    ? (              // se devuelve
      c |            // entero
      Math.random()  // aleatorio
      * 16           // entre 0 to 15
      >> c / 4   // o entre 8 y 11 si c = 8
      ).toString(16) // en formato hexadecimal
    : (              // en caso contrario
      "" +           // la cadena concatenada:
      1e7 +          // 10000000 +
      -1e3 +         // -1000 +
      -4e3 +         // -4000 +
      -8e3 +         // -80000000 +
      -1e11          // -100000000000,
      ).replace(     // reemplazando
        /0|1|(8)/g,  // unos y ceros con
        b            // dígitos hex aleatorios
      )
}

Ahora ya generamos los UUIDs correctamente

Y volvemos a avanzar. Más difícil todavía

Vamos a deshacernos del parámetro c y de cuatro bytes.
Si no hace falta c, la expresión regular se compacta a /[018]/g quitando un par de bytes, y otro par en la definición de la función al quedar de nuevo como b(a).

Para seguir manteniendo la funcionalidad, en vez de utilizar las propiedades de OR nos apoyaremos en XOR en la generación de números aleatorios:

...
  return a           // si se pasa el parametro a
    ? (              // se devuelve
      a ^            // entero
      Math.random()  // aleatorio
      * 16           // entre 0 to 15
      >> a / 4   // o entre 8 y 11 si a = 8
      ).toString(16) // en formato hexadecimal
...


Veamos como se hace la magia. Hay tres casos posibles para los valores de a.
  1. Para el caso a=0 obtenemos 0^Math.random()*16>>0/4, y como >>0/4 es lo mismo que >>0, funcionará igual que Math.floor, como ya hemos visto. En esta situación, 0^ no hace nada.
  2. Para el caso a=1 tenemos: 1^Math.random()*16>>1/4, y >>1/4 sigue siendo >>0. Aquí 1^ cambia el bit menos significativo, es decir, 0 y 1 se intercambian, 2 con 3, y así sucesivamente. El efecto neto es que seguimos generando números aleatorios de 0 a 15.
  3. Para el caso a=8, tenemos 8^Math.random()*16>>8/4, >>8/4 se convierte en >>2.
    El máximo número de Math.random()*16 en forma binaria es 1111, por lo que nos moveremos entre 0000 y 1111. La hacer el shift a la derecha de 2 bit, el máximo número de Math.random()*16>>2 es 0011, y el rango 0000-0011, como habíamos visto esto genera los números aleatorios entre 0-3. Finalmente, como el bit más significativo es SIEMPRE 0, 8^ es en la práctica lo mismo que 8|, lo que asegura que el rango empieza por 8 como antes del cambio. Es decir, obtenemos 8 + {0, 1, 2, 3}.

Y así conseguimos finalmente un código de 111bytes que genera UUIDs aleatorios:
function b(a){return a?(a^Math.random()*16>>a/4).toString(16):([1e7]+-1e3+-4e3+-8e3+-1e11).replace(/[108]/g,b)}



Existe otra versión publicada por Alexey Silin (@LeverOne) que es cuatro bytes más corta y esta basada en iteración en lugar de en recursión. Tira mucho más de conceptos matemáticos. La tenéis aquí: https://gist.github.com/1308368






viernes, 23 de marzo de 2012

¿Qué es un polyfill?

Un "polyfill", también conocido como un "polyfiller", es una pieza de código o plugin que te permite trabajar con una tecnología que esperas que el navegador te proporcione de forma nativa.

Y me preguntarás: ¿esto no es un "shim"? Y estarás en lo cierto. Un "shim" es una pieza que intercepta una API de manera transparente, cambiando los parámetros, gestionando la operación directamente o redirigiéndola a otro sitio. Los "shims" se usan típicamente cuando una API cambia. Con un "shim" se puede conseguir, por ejemplo, que código nuevo pueda funcionar con una API antigua u obsoleta.

Por tanto, podemos decir que un "polyfill" es un "shim" pero centrado en proporcionar a navegadores legacy la compatibilidad con funcionalidades HTML5 y CSS3.

A continuación os presento un ejemplo de polyfill para ilustrar el concepto.

requestAnimationFrame

requestAnimationFrame es una nueva característica de los navegadores que permite indicarle al navegador que deseas realizar una animación. Básicamente lo que le dices con esta función al navegador es: "antes de pintar el siguiente frame en pantalla, aplica esta lógica del juego o procesa esta animación". El método recibe como argumento el callback que se tiene que invocar antes del repintado. Como te puedes imaginar, esta función viene genial para programar juegos en entorno web.

Las ventajas de utilizar requestAnimationFrame son varias:
  • Si queremos utilizar setInterval o setTimeout, para realizar una animación a una velocidad constante hay que estar recalculando contantemente la diferencia de tiempo transcurrido entre el último frame y el momento actual, porque el parámetro de tiempo que se pasa a estas funciones no se aplica estrictamente. Con requestAnimationFrame nos olvidamos de esto y conseguimos una tasa de refresco constante.
  • Gestionar tabs inactivas. Esta es una de las grandísimas ventajas que proporciona. Al permitir al navegador elegir el mejor intervalo entre frames, los usuarios podrían estar jugando a un juego muy intensivo en CPU y que al abrir otra pestaña o al minimizar la ventana el juego se pause, liberando recursos para otras tareas. El jsfiddle a continuación lo ilustra correctamente.

El uso de requestAnimationFrame sería en teoría tan sencillo como:



Los problemas de requestAnimationFrame son (al menos) estos dos:
  1. Navegadores antiguos. No existe por lo que hay que tirar de un setInterval o setTimeout.
  2. Navegadores actuales. La API no está estable por lo que es necesario añadir el dichoso prefijo de los navegadores.
Así que necesitamos un polyfill. En este caso, es tan sencillo como lo que ves en el siguiente gist. Nos abstraemos de las implementaciones de los navegadores y tenemos un fallback a setTimeout:



Si quieres una versión más precisa o inteligente de este polyfill, aquí tienes otra versión de Erik Möller, ingeniero de Opera: http://my.opera.com/emoller/blog/2011/12/20/requestanimationframe-for-smart-er-animating. Básicamente, escoge el delay más adecuado entre 4ms y 16ms para intentar conseguir una tasa de refresco lo más parecida a 60fps y prepara también el método contrario cancelAnimationFrame. Aquí tienes un gist ligeramente optimizado sobre la versión del artículo: https://gist.github.com/2174491

¡Quiero más polyfills!

Pues estás de suerte, el equipo de Modernizr mantiene un pequeño índice de polyfills en:
https://github.com/Modernizr/Modernizr/wiki/HTML5-Cross-Browser-Polyfills

Y, por si te animas, Addy Osmani (está en el equipo de Google desde hace un par de días) ha escrito esta guía sobre como escribir polyfills:
http://addyosmani.com/blog/writing-polyfills/



ACTUALIZACIÓN (25-mar-2012):
Basándome en un ejemplo de 140byt.es aquí te presento otro gist con un polyfill de requestAnimationFrame ultracompacto:




sábado, 3 de marzo de 2012

Atractor de Lorenz en 101bytes

El atractor de Lorenz es uno de los ejemplos más conocidos en la teoría del caos. Para los que no tengan muy claro de que va esto de la teoría del caos, como resumen muy somero se puede decir esta teoría trata de estudiar sistema deterministas (es decir, no aleatorios) que son extremadamente sensibles a las condiciones iniciales. Pequeñas variaciones en las condiciones iniciales (si hablamos de un sistema físico podrían ser posición, temperatura, velocidad, presión o cualquier otra variable relevante del modelo) implica grandes diferencias en el comportamiento observado, dificultando enormemente la predicción a largo plazo (como pasa al intentar predecir el tiempo dentro de un mes).

Volviendo al atractor de Lorenz, este fué estudiado por  Ed N. Lorenz, un meteorólogo al que le debe el nombre, alrededor de 1963. Este sistema deriva de un modelo simplificado de la convección de la atmósfera. También emerge de manera natural a partir de modelos de láseres y dinamos.

El atractor tiene este aspecto:
Vemos que la figura tiene a orbitar alrededor de dos puntos, dibujando una especie de ocho retorcido.

El atractor se expresa de manera habitual como tres ecuaciones diferenciales no lineales acopladas.

$$\frac{dx}{dt} = a (y - x) \\ \frac{dy}{dt} = x (b - z) - y \\ \frac{dz}{dt} = x y - c z $$
El comportamiento está parametrizado por las tres constantes de las ecuaciones  "a", "b" y "c". Un conjunto habitual de valores suele ser:
$$ a = 10 \\ b = 28 \\  c = 8 / 3 $$
Otro conjunto también bastante habitual es:
 $$ a = 28 \\ b = 46.92 \\ c = 4 $$

El parámetro "a"es conocido como el número de Prandtl y "b" como el número de Rayleigh.

La serie no llega nunca a un estado estable, sino que es un ejemplo de caos determinista, siempre cambiante. Al igual que ocurre en otros sistemas caóticos, el sistema de Lorenz es muy sensible a las condiciones iniciales. Dados dos estados iniciales, no importa lo cercan que estén uno del otro, antes o después acabarán divergiendo.

Encontré una solución para implementar el atractor de Lorenz con solo 101 bytes. Lógicamente, el sitio para encontrar algo así es 140byt.es, un portal donde se publican snippets de código javascript que quepan en un twit, o sea, de 140 o menos bytes. Aquí tenéis el código:


El mérito del código es de Martin Kleppe (@aemkei). En GitHub podéis ver muchos otros snippets curiosos de menos de 140 bytes (https://github.com/aemkei).

Aquí tenéis una versión del código anotado, que sin duda es algo más inteligible :) :



Aquí tenéis un fiddle en el que ver el atractor en acción. Se ha usado una visualización en 2D dibujando la coordenada Z como el tamaño de cada punto. VER JSFIDDLE CON EJEMPLO





En este otro ejemplo podeis ver dos atractores, en los que se ha modificado ligeramente una de las condiciones iniciales. Al principio, los dos atractores (azul y verde) evolucionan de manera parecida, pero llegado un punto, los comportamientos son totalmente diferentes. VER EJEMPLO DE LOS DOS ATRACTORES




UPDATE(06/03/2012): Actualizados los enlaces a los jsfiddle que estaban un poco bailados.