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






2 comentarios:

  1. La velocidad de esta solución está muy por detrás de la que se muestra en https://gist.github.com/1308368

    En una ejecución de 3.000 solicitudes de UUID estos son los resultados

    0.043 seconds using with https://gist.github.com/1308368

    0.354 seconds using with this code

    ResponderEliminar
  2. Cierto, y la solución de LeverOne además es más compacta (se presentó posteriormente a 140byt.es). Para el post usé esta porque su aproximación inicial y evolución es bastante más sencilla de seguir. La de LeverOne es un poco más "hardcore". Si tengo tiempo igual la desgrano en otro post para que sea más entendible por os que tengan un bajo nivel de js.

    ResponderEliminar