dic 23 2011

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.


may 8 2011

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.


may 6 2011

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.


mar 14 2011

Dibujando rutas en Google Maps

Dibujando rutas

Puedes consultar las partes anteriores del manual de Google Maps Api 3:
Primera parte del manual

Segunda parte del manual

Tercera parte del manual

Este servicio es interesante, a demás podemos usar coordenadas o direcciones directamente, ya que el servicio las traducirá por sí solo.
Las clases principales son: google.maps.DirectionsService que es la que ejecuta la peticion del servicio al servidor y nos devuelve los datos, y google.maps.DirectionsRenderer que es la encargada de mostrar la ruta en nuestro mapa.
El ejempo básico de inicialización es el siguiente:

directionsService = new google.maps.DirectionsService();
directionsDisplay = new google.maps.DirectionsRenderer();

directionsDisplay.setMap(map);

La llamada a route tiene el formato “directionsService.route(request, function(result, status)”. Hay que generar un objeto request primero(DirectionRequest) que solo es necesario rellenar los campos que no sinteresan. Despues la funcion de callback es la que a partir del status tratamos los reultados.

var request = {
  origin:start,
  destination:end,
  travelMode: google.maps.DirectionsTravelMode.DRIVING
};

La llamada y el tratamiento del objeto result. Comprobamos que el status es OK, si no no hay nada que hacer, salvo mostrar el tipo de error.

directionsService.route(request, function(result, status) {
  if (status == google.maps.DirectionsStatus.OK) {
    directionsDisplay.setMap(map);
    var mystr="";
    for(var i in result.routes){
      var mylegs=result.routes[i].legs
      for(var j in mylegs){
        mystr += mylegs[j].distance.text;
        mystr += " " + mylegs[j].duration.text+ " <br/>";
      }
      mystr+="<br/>";
      $(“#infoRecorrido).html(mystr);
    }
    directionsDisplay.setDirections(result);
  }
});

Lo que realmente dibuja el mapa es ‘directionsDisplay.setDirections(result)’ ¿y todo lo demas? pues bien, google nos envia un objeto con bastante información. Los margenes en que se visualizará el mapa, las coordenadas de los puntos de incio y fin, y otras cosas entre ellas la distancia y tiempo de recorrido.
La distancia se encuentra en “result.routes[0..n-1].legs[0..n-1].duration”. Se puede visualizar en texto en tiempo ya tranformado en horas:minutos:segundos con ‘.text’ o directamente en el numero de segundos con ‘.value’.
La respuesta contiene bastante información y se le puede sacar mucho partido (ver: http://code.google.com/intl/es/apis/maps/documentation/directions/ )

bounds = new google.maps.LatLngBounds();
for(var l in markers){
  bounds.extend( markers[l].getPosition() );
}
map.fitBounds(bounds);

visto en: http://blog.shamess.info/2009/09/29/zoom-to-fit-all-markers-on-google-maps-api-v3/

Finalmente y por experiencia propia recomiendo re posicionar los margenes con cierto retardo con una función como esta:

function rebounds(){
  setTimeout(recReBounds,250,(6));
}

function recReBounds(veces)
  if(!veces){
    return false;
  }
  try{
    bounds = new google.maps.LatLngBounds();
    for(var l in markers){
    bounds.extend( markers[l].getPosition() );
  }
  map.fitBounds(bounds);
  }
  catch(e){
    setTimeout(recReBounds,250,(veces-1));
  }
}

rebounds();

A veces la velocidad del navegador que esté utilizando el cliente no carga las imágenes del mapa con mucha velocidad. Si ejecutamos el reajuste de margenes una vez recogidos los datos puede que se reajusten los margenes antes de pintar el mapa, con lo cual el reajuste no tiene efecto. Con un retardo de un cuarto de segundo el usuario siente interacción de la web y el reajuste tiene efecto.


ene 5 2011

Metodos de instancia y de clase

En JavaScript no existen clases, se simulan las clases con objetos funcion que hacen las veces de constructor. Pero a pesar de ello a los desarrolladores backend les sigue gustando usar clases. En general a todo el mundo que venga de otro lenguaje OO le gusta seguir utilizando clases, o algo que las simule, para instanciar los objetos que van a utilizar.
En la documentacion de Prototype JS clasifican los métodos de una “clase” en dos categorías: métodos de instancia () y métodos de clase (). Por ejemplo la clase Element que se usa para trabajar con el DOM.

El caso de jQuery es bastante distinto. JQuery es un único objeto (lo que seria una clase para Prototype) con distintas propiedades. Cuando usamos el selector $, este nos devuelve un objeto instancia de jQuery, que referencia al elemento del DOM que le hallamos indicado. Este objeto instanciado, tiene propiedades comunes al objeto jQuery pero otras muy variadas. Esto es así porque en el objeto instanciado puede contener un array de elementos del DOM, todo el documento (con $(document)… ) o un div creado al vuelo y que no cuelga de ninguna rama del DOM aun; en general cualquier cosa, por eso tiene propiedades varias para trabajar con cualquier elemento posible.

La documentación de jQuery muestra los metodos de dos formas dependiendo de si son de instancia o de clase. Los métodos de clase aparecen con las nomenclatura “jQuery.metodo()” y los de instancia aparecen empezando por un punto: “.metodo()” que son los que normalmente para trabajar de forma ágil se usan del modo: “$(“#id”).metodo()“.

Documentación jQuery Prototype Style

Me preguntaba como sería ver la documentación de jQuery al estilo de la docu de PrototypeJS. En definitiva aparecería una sola clase (jQuery en si) seria algo parecido a lo que sigue:

Propiedades de jQuery: Class Method

prototype fn extend noConflict isReady ready bindReady isFunction
isArray isPlainObject isEmptyObject error parseJSON noop globalEval nodeName
each trim makeArray inArray merge grep map guid
proxy uaMatch browser support props cache expando noData
data removeData queue dequeue attrFn attr event Event
find expr unique text isXMLDoc contains filter dir
nth sibling fragments clean cleanData style css curCSS
swap get getScript getJSON post ajaxSetup ajaxSettings lastModified
etag ajax handleError active httpSuccess httpNotModified httpData param
speed easing timers fx offset

Propiedades del prototipo de jQuery (objeto jQuery): Instance Methods

init selector jquery length size toArray get pushStack
each ready eq first last slice map end
push sort splice extend data removeData queue dequeue
delay clearQueue attr removeAttr addClass removeClass toggleClass hasClass
val bind one unbind delegate undelegate trigger triggerHandler
toggle hover live die blur focus focusin focusout
load resize scroll unload click dblclick mousedown mouseup
mousemove mouseover mouseout mouseenter mouseleave change select submit
keydown keypress keyup error find has not filter
is closest index add andSelf parent parents parentsUntil
next prev nextAll prevAll nextUntil prevUntil siblings children
contents text wrapAll wrapInner wrap unwrap append prepend
before after remove empty clone html replaceWith detach
domManip appendTo prependTo insertBefore insertAfter replaceAll css serialize
serializeArray ajaxStart ajaxStop ajaxComplete ajaxError ajaxSuccess ajaxSend show
hide _toggle fadeTo animate stop slideDown slideUp slideToggle
fadeIn fadeOut offset position offsetParent scrollLeft scrollTop innerHeight
outerHeight height innerWidth outerWidth width
*si el objeto es un elemento del DOM también aparecerá en esta lista la propiedad ‘context’.

Propiedades Comunes de jQuery y de su prototipo.

En general los métodos de instancia y de clase comunes son los siguientes:

extend ready error each map data removeData queue
dequeue attr find text filter css get offset

En este articulo no me voy a meter con la diferencia entre una librería y otra, eso ya quedaría para otro momento. Pero en cuanto a documentaciones se refiere me gusta bastante el estilo claro de la de Prototype. Aunque ya hace tiempo que me acostumbré a buscar en la documentación de jQuery, veo que no pueden hacer toda la documentación en una sola página. Su documentación sigue la misma filosofía que la librería pero puede ser confuso para quienes empiezan a trabajar con ella, y todo viene de que hay que cambiar la forma de pensar cuando se cambia de lenguaje. JavaScript is diferent. XD


dic 28 2010

Dos tipos de herencia en JavaScript

JavaScript arrastra con sigo una gran parte de sintaxis de los lenguajes clasicos orientados a objetos, sin embargo la orientación a objetos de JS es un tanto distinta, ya que aunque se puede considerar que todo son objetos como en Java, en JS no existen las clases, lo cual los distancia bastante.
Una parte muy confusa es la herencia entre objetos, no entre clase porque que no existen, y que un objeto herede de otro es un tanto extraño.
Para empezar, como deciamos, todo son objetos incluidas las funciones. Las funciones son objetos ejecutables, y se pueden ejecutar de dos formas, de la forma tradicional o con la instruccion ‘new’. De la manera tradicional la funcion devuelve lo que devuelva mediente return. Con ‘new’ la funcion se puede ver como un constructor (de hecho lo es) que devuelve un objeto al que se puede hacerse referencia dentro de la propia funcion con ‘this’; en este caso el ‘return’ es implicito y no hace falta que aparezca la instruccion ‘return this’.

function A(){
 this.nombre="aaaaaa";
 this.apellido="111111";
}

var aa=new A();

aa instanceof A;//true
aa.nombre;//aaaaaa
delete aa.nombre;
aa instanceof A;//true
aa.nombre;//undefined

Para implementar herencia entre objetos la primera instrucción que debe aparecer en el constructor es la llamada al constructor del padre. Esto se conoce como alquilar el constructor.

Podemos imvocar cualquier funcion con los métodos ‘call‘ o ‘apply‘.
A parte de las diferencias de rendimiento entre uno y otro en los distintos navegadores, lo que distingue a estos dos métodos es que ‘apply‘ debe ser invocado con los todos parámetros dentro de un array; en ‘call’ los parámetros pueden aparecer del mismo modo que en la llamada normal a la funcion.
En los dos métodos el primer argumento debe ser el objeto al que se aplica la funcion. En nuestro caso el objeto es ‘this‘ ya que desde nuestro constructor invocamos al constructor de otro objeto.

function B(){
A.apply(this,arguments);
this.nombre="bbbbbb";
this.apellido="222222";
}

Como el prototipo de la funcion puede ser extendido fuera de esta debemos de añadir todas sus propiedades al prototipo del objeto heredero. Esto se puede hacer de varias formas pero las dos más interesantes son las siguientes:
B.prototype=new A()  vs.  B.prototype=A.prototype
Con cualquiera de las dos elecciones el metodo ‘instanceOf’ de un objeto creado mediante ‘new B()’ nos devoveria verdadero para el objeto original y para el heredado, pero a parte de esto el resultado interno no es el mismo en los dos casos.
B.prototype=new A()
En este caso hay que tener en cuenta que el prototype de B es una instancia de A, y que su constructor ha sido ejecutado no solo en el constructor sino tambien para crear el prototipo de manera que si una propiedad o funcion no existe o es borrada en el objeto hijo, puede aun existiendo en la clase padre si se definió en su constructor. Esto es así porque al no encontrar cierta propiedad la maquina virtual de JavaScritp continua la cadena de prototipos para encontrarla antes de devolver un error y terminar con la ejecucion bruscamente. No siempre esto es malo, en ocasiones preferimos que las propiedades repetidas para usar la del padre en caso que quisieramos. Solo hay que tenerlo en cuenta

B.prototype=new A();
var bb=new B();

La propiedad ‘__proto__’, o lo que es lo mismo el prototype del constructor de bb (bb.constructor.prototype === bb.__proto__), está apuntando a una instancia del objeto A, la cual apuntará a través de su constructor al metodo ‘A’, se van generando dos saltos en cada herencia entre objetos.
En este caso sucede que:

bb.constructor.prototype === bb.__proto__ //false

bb.constructor.prototype === A.prototype //true
//pero
bb.__proto__ === A.prototype //false

B.prototype=A.prototype;

B.prototype=A.prototype;
var bb=new B();

Aquí la propiedad ‘__proto__’ del objeto bb apunta directamente a la funcion ‘A’, y no a un objeto instanciado de esta.

bb.constructor.prototype === bb.__proto__ //true
bb.constructor.prototype === A.prototype //true
bb.__proto__ === A.prototype //true

En este caso hay que tener en cuenta que el prototype de B el prototype A, por lo tanto una vez eliminado un elemento o funcion de nuestro objeto, quedará borrado para siempre y su lectura devolveria ‘undefined’.

B.prototype=new A();

bb instanceof A; bb instanceof B;// true true
bb.nombre;//bbbbbb
delete bb.nombre;
bb instanceof A; bb instanceof B;// true true
bb.nombre;//aaaaaa
delete bb.nombre;
delete bb.nombre;
bb instanceof A; bb instanceof B;// true true
bb.nombre;//aaaaaa

Más grados de herencia
¿Que pasa con la jerarquía de herencia?. Hay muchas maneras de crear herencia a partir de estas dos básicas. Uno de los patrones de herencia intenta crear un objeto intermedio entre el objeto hijo y el objeto padre.
En el siguiente ejemplo el objeto C utiliza como prototipo intermedio al objeto BtoC, de esta manera aunque hagamos un “delete C.nombre” los objetos creados a partir de un “new C()” seguiran teniendo la propiedad “nombre” de B.

function BtoC(){
 B.apply(this,arguments);
};
BtoC.prototype=new B();

function C(){
 BtoC.apply(this,arguments);
 this.nombre="cccccc";
}
C.prototype=BtoC.prototype;

var cc=new C();

cc instanceof A; cc instanceof B; cc instanceof C;// true true true
cc.nombre; cc.apellido; //cccccc 222222
delete cc.nombre; delete cc.apellido;
cc instanceof A; cc instanceof B; cc instanceof C; // true true true
cc.nombre; cc.apellido; //aaaaaa 111111
delete cc.nombre;delete cc.apellido;

Podemos decir que si utilizamos “prototype=new Clase()” rompemos la cadena de busqueda por los prototipos de la maquina virtual de JS. Los objetos en sí no tienen la propiedad prototype, por defecto solo la tienen los objetos Function. Así que emplear un tipo de herencia u otra depende de nuestros propios objetivos.

En mozilla proponen la herencia con la extensión de propiedades de un prototipo con las de otro, en definitiva es la misma extensión de un objeto con otro:

function extend(child, super){
 for (var property in super.prototype) {
  if (typeof child.prototype[property] == "undefined")
   child.prototype[property] = super.prototype[property];
  }
 return child;
}

https://developer.mozilla.org/en/JavaScript/Guide/Inheritance_Revisited
La extensión aunque permite tranferir las propiedades de un constructor a otro no nos es útil si en nuestro código vamos a utilizar el metodo “instanceOf” para verificar que nuestro objeto tiene ciertas propiedades por defecto. En el caso de este tipo de herencia habria que utilizar “propiedad in objeto” para comprobar que existe.

https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Function/prototype
https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Object/GetPrototypeOf
Javascript Patterns. Stoyan Stefanov.