feb 11 2012

Fuciones publicas vs privilegiadas

Hace tiempo que encontré este texto de Douglas Crockford sobre las funciones privadas en JavaScript. En el explica como crear funciones privadas de un objeto. Estas son declaradas en el constructor pero no se le asignan al objeto this. De esta manera solo las funciones dentro del mismo ámbito (el del constructor) tienen el privilegio de acceder a ellas.

function myKlass(){
   var privateValue=0;
   function privateFunction(){
      return ++privateValue;
   }
   //Esta funcion tiene el privilegio de acceder a privateFunction
   this.pivileged=function(){
      return "Ejecución nº "+ privateFunction();
   }
}
var obj = new myKlass();
obj.pivileged();//Ejeción nº 1
obj.pivileged();//Ejeción nº 2
obj.pivileged();//Ejeción nº 3

Si extendemos el prototipo de la función myKlass podemos obtener una clase más rica, con muchas más funciones publicas que estarán en todos los objetos creados con la sentencia new.
Hasta aquí nada nuevo, porque esto es posible en javascript ya desde hace mucho. Pero el diferenciar entre Publica y Privilegiada es algo que no me acaba de gustar.

Toda función puede tener ciertos privilegios.

Las funciones creadas dentro del constructor tienen acceso a todas las funciones dentro del mismo ámbito. Sí, esto es un privilegio, pero estas funciones no tienen acceso a, por ejemplo, terceras funciones internas a otra funcion privilegiada (o publica).
Así que en realidad solo tiene privilegio a un ámbito, que casualmente es el del constructor. Es muy sencillo crear otro ábito y declarar alli una gran cantidad de funciones privadas y asignarselas al prototipo. En este nuevo ámbito podriamos tener otras funciones privilegiadas que solo tuviesen acceso a este ámbito. Veamoslo:

myKlass.prototype.otherPrivileged=(function(){
   var otherVariable=0;
   function otherExecution(){
      return otherVariable+=100;
   }
   return function(){
      return "Aqui vamos a "+otherExecution();
   }
})();
obj.otherPrivileged();//Aqui vamos a 100
obj.otherPrivileged();//Aqui vamos a 200

Aqí tenemos una función que también tiene ciertos privilegios. No tiene acceso a privateValue o a privateFunction, pero solo ella tiene acceso a otherVariable y otherExecution.

Para una función está muy bien. Pero ¿y si queremos un grupo de funciones ‘privilegiadas’?. Pues nuestro ámbito de privilegios debe devolver no una sola función, sino un objeto con las funciones que deseemos y extender el prototipo de nuestra ya muy nutrida clase con ellos.

var superFunctions=(function(){
   var v1=0,v2=2000,v3=775;//...
   function fprivate1(){/*...*/}
   function fprivate2(){/*...*/}
   function fprivate3(){/*...*/}

   function fpublic1(){/*...*/}
   function fpublic2(){/*...*/}
   function fpublic3(){/*...*/}
   return {
      fpublic1: fpublic1,
      fpublic2: fpublic2,
      x: fpublic3
   }
})();

for(fun in superFunctions){
    myKlass.prototype[fun]=superFunctions[fun];
}

new myKlass();
/* Cuidado con los nombres de las funciones, serán los del objeto devuelto
x	fpublic3()
fpublic1	fpublic1()
fpublic2	fpublic2()
otherPrivileged	function()
pivileged	function()
*/

Con una funcion para extender prototypos de funciones se habría quedado un código más legible, pero en definitiva esto es lo que se debe hacer.

Sea como sea, podemos hacer que cualquier función publica sea en cierta medida privilegiada. Por eso prefiero no hacer distinción entre las funciones de un objeto. Cada una puede implementar su funcionalidad con acceso a otros métodos o no, eso no importa.


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.