UnderscoreJS, funciones de delay

Me han parecido muy interesantes que veo necesario comentar. Salidas de underscore js que es una librería que cada vez me está gustando más. Es un conjunto de funcionalidades que se puede decir que «completan» el javascript básico de cualquier navegador.

-Delay-

Retrasar una funcion, wrapping del setTimeout ya existe en javascript. Es muy sencilla, pero solo por abstraer el temporizador se merece una mención.

// Delays a function for the given number of milliseconds, and then calls
// it with the arguments supplied.
_.delay = function(func, wait) {
    var args = slice.call(arguments, 2);
    return setTimeout(function(){ return func.apply(null, args); }, wait);
};

-Debounce-

Devuelve una función que mientras parecida a ‘_.delay‘. Si la función se vuelve a ejecutar antes del tiempo indicado la cuenta vuelve a empezar.
Cuántas veces has querido volver a empezar la cuenta atrás para alguna acción que has lanzado. Tiene mucho más sentido si son métodos asociados a eventos del usuario. Un pequeño retraso en algo a veces, como que aparezca/desaparezca info extra cuando se hace hover/blur da muy buena experiencia al usuario (solo es un ejemplo de uso, seguro que hay mil más).

// Returns a function, that, as long as it continues to be invoked, will not
// be triggered. The function will be called after it stops being called for
// N milliseconds. If `immediate` is passed, trigger the function on the
// leading edge, instead of the trailing.
_.debounce = function(func, wait, immediate) {
    var timeout;
    return function() {
    var context = this, args = arguments;
    var later = function() {
        timeout = null;
        if (!immediate) func.apply(context, args);
    };
    if (immediate && !timeout) func.apply(context, args);
        clearTimeout(timeout);
        timeout = setTimeout(later, wait);
    };
};

Así si ejecutamos:

function x(){
    return "executed";
}
var x_debounced = _.debounce(x, 60*1000);

x_debounced();// 00:00:00
x_debounced();// 00:00:10
x_debounced();// 00:00:21

//el resultado será:
"executed" // 00:01:21

Además la función incluye el parámetro ‘immediate‘. En caso de querer que la ejecución sea anterior al tiempo de espera solo debemos ponerlo a true.
De este modo el tiempo indicado es el tiempo tras la ejecución en el que no podrá volver a ejecutarse la función.

Un ejemplo sería:

function x(){
    return "executed";
}
var x_debounced = _.debounce(x, 60*1000, true);

x_debounced();// 00:00:00 : "executed"
x_debounced();// 00:00:10
x_debounced();// 00:00:21
x_debounced();// 00:00:46
x_debounced();// 00:01:47 : "executed"

//bloqueado hasta 00:02:47

-Throttle-

Devuelve una función que sólo se puede ejecutar una vez en un periodo de tiempo. Es similar al concepto de semáforos con un recurso, solo que el recurso es la propia función.

Internamente usa ‘_.debounce‘ para liberar la ejecución.

Mantiene un control de si se ha vuelto a ejecutar la función durante el periodo de bloqueo para ejecutarla de nuevo al final.

// Returns a function, that, when invoked, will only be triggered at most once
// during a given window of time.
_.throttle = function(func, wait) {
    var context, args, timeout, throttling, more, result;
    var whenDone = _.debounce(function(){ more = throttling = false; }, wait);
    return function() {
        context = this; args = arguments;
        var later = function() {
            timeout = null;
            if (more) func.apply(context, args);
            whenDone();
        };
        if (!timeout) timeout = setTimeout(later, wait);
        if (throttling) {
            more = true;
        } else {
            result = func.apply(context, args);
        }
        whenDone();
        throttling = true;
        return result;
    };
};

Del mismo modo, si ejecutamos:

var x_throttled = _.throttle(x, 60*1000);
x_throttled();// 00:00:00 “executed”
x_throttled();// 00:00:10
x_throttled();// 00:00:21

// 00:01:00"executed"

Ante un uso masivo de la función nos aseguramos que solo se ejecutará realmente en los periodos indicados.

Para tu toolkit

Podemos incluir las funciones entre los métodos de Function, así como en su prototipo, para que cualquier función herede este método y podamos generar funciones delay, debounce y throttle en modo inline.

Hacer esto es tan sencillo como:

Function.delay = function(func, wait) {
    var args = slice.call(arguments, 2);
    return setTimeout(function(){ return func.apply(null, args); }, wait);
};
Function.prototype.delay = function(wait) { return Function.delay(this,wait); };

Function.debounce = function(func, wait, immediate) {
    var timeout;
    return function() {
    var context = this, args = arguments;
    var later = function() {
        timeout = null;
        if (!immediate) func.apply(context, args);
    };
    if (immediate && !timeout) func.apply(context, args);
        clearTimeout(timeout);
        timeout = setTimeout(later, wait);
    };
};
Function.prototype.debounce = function(wait, immediate){ return Function.debounce(this,wait,immediate); };

Function.throttle = function(func, wait) {
    var context, args, timeout, throttling, more, result;
    var whenDone = Function.debounce(function(){ more = throttling = false; }, wait);
    return function() {
        context = this; args = arguments;
        var later = function() {
            timeout = null;
            if (more) func.apply(context, args);
            whenDone();
        };
        if (!timeout) timeout = setTimeout(later, wait);
        if (throttling) {
            more = true;
        } else {
            result = func.apply(context, args);
        }
            whenDone();
            throttling = true;
            return result;
    };
};
Function.prototype.throttle = function(wait) { return Function.throttle(this,wait); };

Más pixels aleatorios, esta vez con Canvas

Hace tiempo escribí un post acerca de los pixels aleatorios. Dibujaba una imagen en java para probar que no ser repetían patrones en la funcion random. Para hacer lo propio en javascript ahora gracias al html5 podemos usar la etiqueta canvas y pintar dentro de ella. Nos declaramos un canvas del tamaño que queramos, por ejemplo de 300 x 300

<canvas height="300" width="300" id="mycanvas"></canvas>

Antes de dibujar en nuestro lienzo tenemos que usar el contexto, en este caso en 2d.

Para dibujar pixel a pixel solo tienes que dibujar cuadrados de un pixel de tamaño. Empezamos por la cordenada (0,0) hasta la (299,299). En realidad puedes dibujar fuera del canvas, pero por supuesto no esperes que se vea.

function drawRandom(id){
	var canvas = document.getElementById(id);
	var ctx = canvas.getContext('2d');

	for(var j=0;j<300; j++){
		for(var i=0;i<300; i++){
			ctx.fillStyle = getRandColor();
			ctx.fillRect(i, j,i+1, j+1);
		}
	}
}

function getRandColor(){
	//Si quieres puedes usar solo blanco y negro para verlo más claro
	//var blanco="rgb(255,255,255)";
	//var negro="rgb(0,0,0)";
	return ("rgb("+(parseInt( (Math.random()*1000) % 256))+","
		+(parseInt( (Math.random()*1000) % 256))+","
		+(parseInt( (Math.random()*1000) % 256))+")");
}

drawRandom("mycanvas");

Puede que tarde un rato, o incluso que el navegador piense que tienes un bucle infinito en ejecución. Después te pintará una imagen tan «bonita» como esta:

canvas con pixels de colores aleatorios
canvas con pixels de colores aleatorios

Para este ejemplo sencillo vemos que la funcion Math.random( ) se comporta bastante bien en cuanto al grado de aleatoriedad. Pero si quieres profundizar en hacer dibujos con canvas puedes ver más cosas aquí. Si ya lo has hecho en otros lenguajes (no como yo) no te resultará complicado hacerlo en javascript.

Two ways to create custom objects

Visto en JSAPI User Guide una tan sencilla como complicada segunda opción

Hay dos formas de crear objetos personalizados que el JS engine puede utilizar:

  • Escribir un script JS que crea un objeto, sus propiedades, métodos, y el constructor, y luego pasa la secuencia de comandos para el motor de JS en tiempo de ejecución.
  • Insertar el código de la aplicación que define las propiedades del objeto y los métodos, llame al motor para inicializar un objeto nuevo, a continuación, establezcalas propiedades del objeto a través de llamadas adicionales al motor. Una ventaja de estemétodo es que su aplicación puede contener métodos nativos que manipulen directamente la incrustación de objetos.

La desventaja del segundo método es que para escribir algo en javascript tienes que escribirlo en C++. Sencillez vs rendimiento.

Hace tiempo leí una cita sobre Unix que decía algo así como:  «UNIX es sencillo, solo que hace falta un genio para apreciar su sencillez». Creo que no solo le pasa a Unix.

Timsort. Porqué no había versión JavaScript

La ordenación de vectores es algo que se imparte desde los primeros años de carrera en informática con el método de la burbuja, inserción directa y alguno más con complejidad O(n^2). Más tarde cuando se profundiza en la algoritmia un poco llegamos a algoritmos más complejos de complejidad O(nLogn) se concluye que no hay nada mejor en la ordenación de vectores, y esas innovaciones son ya de hace bastante tiempo.

Métodos de ordenación de vectores

QuickSort,  MergeSort, HeapSort … hay muchos Sort’s por el mundo y todos tienen ventaja frente a otros. Los que he mencionado son de los más conocidos con complejidades de O(nLogn). Por lo que he estado viendo, el MergeSort es el que se suele utilizar más por su baja cantidad de operaciones de computo. Es muy sencillo, ya que mezclar listas ordenadas de elementos tiene complejidad lineal y no tiene mucha historia. Su principal desventaja, la gran cantidad de memoria temporal utilizada, tiene cada vez menos importancia gracias a que la memoria se va abaratando cada vez más. Pero…

¿Que pasa en los dispositivos que no tienen mucha memoria? Lo primero que viene a la mente es que siempre hay alguien que tiene un equipo en el que la memoria se mide en K’s, pero no van por ahí los tiros. Los smartphones y tablets son cada vez más populares, y por ahora lo que se considera normal en estos dispositivos es lo que se tenía en escritorio hace ya bastante tiempo.

TimSort

En esta visión del ahorro de memoria + mergeSort es donde surge el algoritmo TimSort. Lo ideó Tim Peters para la ordenacion en Python (donde se pueden programar librerias nativas en C) y lo bautizó con su propio nombre, como el dice: «eh, me lo he ganado».

El TimSort no mejora en complejidad a su padre, el MergeSort, pero si que tiene ciertas optimizaciones que lo hacen que ahorre mucha memoria en los casos medios. Cuando una parte del vector está «bastante» ordenada no sigue dividiendo el vector en partes hasta llegar a una lista de un elemento, sino que utiliza la inserción directa para ordenar todo ese trozo. Aunque la inserción directa sea de complejidad O(n^2) para listas muy pequeñas de elementos es muy rápido gracias a su sencillez.

Si un tramo del vector que estamos intentado ordenar de mayor a menor por ejemplo, se encuentra ordenado de menor a mayor, el algoritmo invierte este tramo y continua.

Con esto y ajustando los vectores temporales al mínimo requerido timsort consigue un ahorro de memoria y de rendimiento respecto de MergeSort en vectores parcialmente ordenados o con muchos repetidos.

Ejemplo de ordenación con Timsort

TimSort en C (Python) y en Java

Es por estas pequeñas cosas que el TimSort ha sido seleccionado para ser el tipo de ordenación de vectores por defecto en Java 7 (lanzamiento estimado en Julio de 2001) y en la plataforma para móviles Android (que se puede decir que es Java también)

También es la ordenación por defecto en Python, bastante lógico cuando el algoritmo se ideó en principio para este lenguaje. Esta implementación es nativa de Python, por eso está escrito en C (no todo lo nativo de Python está escrito en C pero sí es aconsejable para aumentar el rendimiento).

El TimSort de Tim lo puedes encontrar aquí (timsort.c) y una explicación de sus pruebas de rendimiento.

Otra implementación en java Josh Bloch con bastantes menos lineas de código.

Y … en JavaScript

Siendo un obsesionado del JavaScript me pregunté, ¿y no hay implementación en JavaScript?. En javascipt ya se pueden ordenar vecteres con el metodo nativo del Array sort(funcionDeComparacion) pero cada maquina viertual de JS utiliza la ordenación que más le conviene. Bueno en realidad la que han decidido sus desarrolladores. Pero de todas maneras, si los desarrolladores de una maquina virtual de JS decidieran implementarlo usarían el código ya existente si implementan en C/C++ como son el SpiderMonkey y el V8, o la versión Java para Rhino.

Utilizar una versión JavaScript para ordenar vectores en JavaScript sería una perdida de rendimiento, al menos en gran cantidad de los casos.

Mi pequeña contribución

Si aun así no te fias y quieres hacer tus propias pruebas de rendimiento he portado la versión Java del algoritmo a JavaScript (TimSort JavaScript), con algunas optimizaciones propias del lenguaje; intentando utilizar el mayor numero de métodos nativos del lenguaje, aunque estoy seguro de que se puede optimizar algo más hasta equipararse en rendimiento 1 a 1 al sort nativo (que puede que en cada implementación sea un algoritmo distinto). Actualmente solo supera en rendimiento al nativo en muy pocas ocasiones, cuando el vector tiene muy poca entropía; y en casos muy malos llega a duplicar el tiempo de computo de la versión nativa.

No he buscado mucho y no sé que algoritmos utilizan las maquinas virtuales de los navegadores de hoy en día así que indagaré un poco pero eso es otro post.