Introducción

Sin duda, uno de los temas más apasionantes dentro de la computación es el diseño y desarrollo de algoritmos. Como objeto de estudio, son una parte fundamental de la informática al permitir manipular datos mediante una secuencia organizada de pasos o procedimientos.

Este artículo quiere ser una introducción a los algoritmos en Javascript pero, por extensión, lo que estudiemos es aplicable a prácticamente cualquier otro lenguaje de programación.

Los puntos que trataremos en este artículo son:

• Definición de algoritmo
• Analizando la complejidad de un algoritmo
• Entendiendo la notación Big-O: órdenes principales y ejemplos
• Herramientas para medir la complejidad de un algoritmo en Javascript

Definición de algoritmo

Hemos escuchado esta palabra muchas veces; sabemos que es importante en programación, pero no tengo claro cúal es su definición exactamente.

Bien; en primer lugar habría que aclarar que no estamos tratando con algo exclusivo de la programación; los algoritmos están presentes por todas partes. En nuestra vida cotidiana los utilizamos frecuentemente en una u otra actividad.

Los algoritmos son en definitiva una serie de pasos bien definidos y ordenados que son utilizados en secuencia para realizar una tarea específica.

Por lo general, en computación un algoritmo sirve para pasar un sistema de un estado a otro; por sistema entedemos variables, funciones, objetos, etc…

El ejemplo más simple de algoritmo podemos encontrarlo por ejemplo en el proceso de multiplicación. Como bien sabemos, un producto puede ser interpretado como la suma sucesiva de sus factores. Esto quiere decir que 3 x 4 se corresponde en realidad con 3 + 3 + 3 + 3 (o 4 + 4 + 4 si aplicamos la propiedad conmutativa). Esta operación puede traducirse en términos de algoritmia de la siguiente forma: dados dos enteros A y B, podemos decir que el producto resultante de A x B corresponde a la suma de B consigo mismo A veces.

Eso sería un algoritmo que, traducido a código Javascript, daría:

function product(a, b){
  var result = 0;
  if( b == 0 ) return result;
 
  for(var x = 0; x < b; x++){
    result += a;
  }
 
  return result;
}
 
console.log( product( 3, 5 ) ); // 15
console.log( product( 7, 0 ) ); // 0

El ejemplo anterior es sumamente sencillo (además de ideal para practicar algo de TDD si estamos iniciándonos en ese arte), pero se trata en definitiva de un algoritmo.

Llegados a este punto en el que hemos definido un conjunto de operaciones para realizar una tarea concreta (una multiplicación en este caso), cabe preguntarse sobre cuánto de eficiente es el algoritmo que hemos escrito; para eso, tenemos que estudiar su complejidad y efectividad.

Comprendiendo la complejidad de un algoritmo

Uno de los puntos claves tras el diseño de un algoritmo es comprobar su eficiencia pero, ¿cómo se determina si un algoritmo es eficiente?

Existen para esto varios criterios no excluyentes que vamos a considerar.

Tamaño

Sin duda, uno de los primeros aspectos que puede llevarnos a medir la eficiencia de un algoritmo es el número de líneas que lo componen: un código más pequeño parece siempre más elegante e inteligente pero, ¿significa necesariamente que es más eficiente?

La función que hemos escrito más arriba podemos acortarla un poco:

function product(a, b){
  for(var result = 0, x = 0; x < b; x++) result += a;
  return result;
}
 
console.log( product( 3, 5 ) ); // 15
console.log( product( 7, 0 ) ); // 0

Bien; tenemos menos líneas; pero como se puede intuir a simple vista, el rendimiento debería ser similar al anterior ya que nos hemos dedicado únicamente a compactar el código un poco.

Eficiencia

Para obtener criterios de medición más realistas, debemos preguntarnos en primer lugar qué significa eficiciencia. ¿Estamos hablando de tiempo de procesado por la CPU, de la memoria requerida, de I/O, etc… ?

Uno de los errores más frecuentes a la hora de analizar la eficiencia de un algoritmo es confundir términos como rendimiento (cantidad de CPU/memoria/disco utilizado) con complejidad (cómo escala el algoritmo). Y es en este segundo punto donde se encuentra la clave: la escalabilidad.

Tomemos como ejemplo un algoritmo que necesita 10 milisegundos para procesar 100 registros. Cuando hablamos de escalabilidad, nos referimos a cómo se comportará esta función si el número de registros se incrementa.

En nuestro caso, si tenemos que un algoritmo necesita 10 milisegundos para operar sobre 100 registros y otro necesita 20 milisegundos para la misma cantidad, parece que deberíamos calificar al primero como mejor. Sin embargo, si ampliamos el objeto de estudio diez veces (1000 registros) y el primero necesita 100 milisegundos (10 veces más) mientras que el segundo ahora solo necesita 80, deberíamos reconsiderar nuestra afirmación.

Complejidad

De forma coloquial, la complejidad de un algoritmo mide la cantidad de recursos necesarios para realizar una función dada; esto es complejidad en términos de memoria, CPU, etc. Sin embargo, para ser precisos, habría que redefinir el concepto para hablar de complejidad como el número de cómputos o cálculos necesarios para realizar una función concreta.

¿Y cómo calculamos ese tipo de recursos? Pues ayudándonos de una gran O.

Entendiendo la Notación Big-O (o notación O Grande)

La idea detrás de este sistema de medición es calcular el coste de recursos relativo de dos o más algoritmos para el resolver el mismo problema en relación a su factor de crecimiento o escalado.

La complejidad de un algoritmo se define en términos de ‘magnitud de orden‘. Esta escala se mide con una O mayúscula que se corresponde con ‘Order of‘ seguido de una expresión que representa el crecimiento relativo al tamaño del problema y que se corresponde con la letra N.

La siguiente lista resume los órdenes más frecuentes que serán explicados más adelante en detalle:

• O(1): Pronunciado «orden 1» y que se corresponde con una función que corre en una línea de tiempo constante.
• O(N): Pronunciado «orden N» y que se corresponde con una función que corre en un tiempo lineal.
• O(N²): Pronunciado «orden N cuadrático» y que se corresponde con una función que corre en un tiempo cuadrático.
• O(log N): Pronunciado «orden N logarítmico» y que se corresponde con una función que corre en un tiempo logarítmico.
• O(N log N): Pronunciado «orden N logarítmico de N» y que se corresponde con una función que corre en un tiempo proporcional al tamaño del problema y del tiempo logarítmico.
• O(N!): Pronunciado «orden N factorial» y que se corresponde con una función que corre en un tiempo factorial.

Existen varios órdenes más además de los citados arriba pero con estos será suficiente para describir la complejidad de los algoritmos en programación.

Analizando los distintos órdenes

Veamos ahora cada uno de los órdenes anteriores en detalle:

Tiempo Constante: O(1)

Este orden pocas veces es alcanzable y se corresponde al Santo Grial de los algoritmos. Significa que un algoritmo siempre requiere el mismo tiempo para realizar una operación independientemente del tamaño del problema. Esto quiere decir que el rendimiento de un proceso no se ve afectado por el número de elementos sobre el que opera.

Resulta complejo encontrar ejemplos de este tipo en el mundo real; quizá solo aquellos más simples, como las asignaciones de dirección de memoria, pueden clasificarse como O(1).

Localizar un elemento concreto en un array y operar sobre él puede servir como ilustración:

function double_last_item_array( my_arr ){
  return my_arr[ my_arr.length - 1 ] * 2;
}
 
console.log( double_last_item_array( [1, 2, 3, 4, 5, 6, 7, 8, 9 ] )) ; // 18
console.log( double_last_item_array( [1, 2, 3, 4, 5, ..., 99996, 99997, 99998, 99999 ] ) ); // 199998

En Javascript, acceder a un elemento concreto de una matriz requiere el mismo tiempo de proceso independientemente del tamaño de ésta.

NOTA: Hay que señalar que este tipo de algoritmos no significa que necesariamente sean muy rápidos sino que siempre son igual de rápidos. Una función que requiere varios minutos para operar sobre un conjunto, más allá del número de éste, puede considerarse completamente inútil.

Tiempo lineal: O(N)

Pese a que al igual que el orden anterior es muy difícil de alcanzar, ésta debería ser nuestra aspiración durante el diseño de un algoritmo.

Un algoritmo se considera de tiempo lineal cuando el número de operaciones que requiere para realizar una función es directamente proporcional al número de elementos que van a ser procesados.

Siguiendo en la línea anterior, un ejemplo puede ser el tomar cada elemento de un array y operar sobre él:

function double_each_item_array( my_arr ){
  for( var x = 0, i = my_arr.length; x < i; x++){
    my_arr[x] *= 2;
  }
  return my_arr;
}
 
console.log( double_each_item_array( [1, 2, 3, 4, 5, 6, 7, 8, 9 ] )) ; // [2, 4, 6, 8, 10, 12, 14, 16, 18]
console.log( double_each_item_array( [1, 2, 3, 4, 5, 99996, 99997, 99998, 99999 ] )) ; // [2, 4, 6, 8, 10, ..., 199992, 199994, 199996, 199998]

En el ejemplo anterior, el tiempo de proceso que el intérprete necesitará para cada conjunto es directamente proporcional al número de elementos que lo contienen: hablamos aquí de un orden O(N).

Tiempo cuadrático: O(N²)

Para que un algoritmo se considere de orden cuadrático, el número de procesos requerido para un grupo de tamaño N debe ser (N² – N) / 2. Como la notación Big-O descarta las constantes (en este caso el 2), lo reducimos a (N² – N). Pero podemos ir más allá: si observamos la siguiente tabla, cuando el conjunto de N crece, la substracción de N a N² se vuelve cada vez más insignificante por lo que finalmente podemos despreciarla para acabar hablando sólo de una complejidad O(N²).

Todo lo anterior viene a decir que un algoritmo cuadrático es aquel cuyo número de operaciones a realizar corresponde al cuadrado del número de elementos sobre el que opera. Este orden supone una pesadilla para los desarrolladores: cualquier función que presente una complejidad de O(N²) puede considerarse inútil para resolver un problemas a excepción de aquellos más pequeños.

En Javascript, este tipo de algoritmos suele concluir con un desbordamiento de pila, lo que los hace aún menos eficientes. En un artículo reciente, La optimización de cola y porqué es necesaria, tratábamos una función que calcula la posibilidad de acertar en la lotería utilizando recursión. Ese primer ejemplo que indicábamos, tiene una complejidad de O(N²):

function odds(n, p) {
  if( n == 0 ) {
    return 1;
  } else {
    return ( n / p ) * odds( n - 1, p - 1 );
  }
}
 
odds(5, 56);
 
// Internamente, esta función se procesa del siguiente modo:
// (5/56) * odds(4, 55)
// (5/56) * (4/55) * odds(3, 54)
// (5/56) * (4/55) * (3/54) * odds(2, 53)
// (5/56) * (4/55) * (3/54) * (2/53) * odds(1, 52)
// (5/56) * (4/55) * (3/54) * (2/53) * (1/52) * odds(0, 51)
// (5/56) * (4/55) * (3/54) * (2/53) * (1/52) * 1

El número total de operaciones se incrementa de cuadrática: para 5 elementos (argumento n), el número de operaciones necesarias es 25 (5×5).

Tiempo logarítmico: O(log N) y O(N log N)

El tiempo de ejecución de un algorirmo logarítmico se incrementa con el logaritmo (en la mayoría de los casos un logaritmo de base 2) del tamaño del problema. Esto significa que incluso cuando el tamaño del conjunto de datos se incrementa por un factor de un millón, el tiempo de proceso sólo se incrementa por su factor logarítmico ( 20 ).

Este tipo de algoritmo suele requerir que se descarten grandes cantidades de datos durante el proceso. Por lo general, la mayoría de algoritmos que se clasifican bajo este orden pertenecen a búsquedas de algún tipo. Un ejemplo en Javascript puede ser la implementación de un quicksort:

function quicksort(arr){
    if (arr.length == 0)
        return [];
 
    var left = new Array();
    var right = new Array();
    var pivot = arr[0];
 
    for (var i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
           left.push(arr[i]);
        } else {
           right.push(arr[i]);
        }
    }
 
    return quicksort(left).concat(pivot, quicksort(right));
}
 
console.log( quicksort( [2,4,5,63,4,5,63,2,4,43] ) ); // [2, 2, 4, 4, 4, 5, 5, 43, 63, 63]

Los algoritmos O(N log N) son mejores que los O(N&exp;2) pero inferiores a los O(N).

Tiempo factorial: O(N!)

No es frecuente encontrarse este tipo de algoritmos por el enorme coste en proceso que suponen. Como es de suponer, pertenecen a la familia más pobre, por detrás incluso del O(N&exp;2).

Un algoritmo O(N!) implica que el número de procesos que requiere para completar una tarea crece de forma factorial con respecto al tamaño del conjunto sobre el que opera.

La siguiente tabla compara el número de operaciones necesarias para una serie de conjuntos con los órdenes cuadrático y factorial:

Como es fácilmente visible, a medida que el número de elementos (N) crece, el de operaciones necesarias se incrementa de forma insostenible. No es necesario decir que en Javascript, el desbordamiento de pila está asegurado con pocos elementos por lo que este tipo de algoritmos no resulta útil ni con conjuntos muy reducidos.

Herramientas para medición en Javascript

Actualmente, gracias a la popularidad de Javascript, existen muchas herramientas que permiten bien de forma directa, bien indirecta, medir el rendimiento de nuestros algoritmos atendiendo a los factores citados más arriba.

Test manual

La forma de medición más sencilla es la manual. Esto es, calculando el tiempo transcurrido desde el inicio hasta la conclusión de un número de ciclos dado.

Así tendríamos:

var d1 = new Date();
 
// How many times has to run the algorithm?
var num_cicles = 1000;
 
for( var x = 0; x < num_cicles; x++ ){   
  // The algorithm goes here... 
} 
 
var d2 = new Date(); 
m1 = d1.getMilliseconds(); 
m2 = d2.getMilliseconds(); 
s1 = d1.getSeconds(); 
s2 = d2.getSeconds(); 
if(s1 > s2){
  var minitotal = s1-s2;
  var total = 60 - minitotal;
  var s2 = s2 + total;
}
 
militotal1=s1 * 1000 + m1;
militotal2=s2 * 1000 + m2;
 
var total = militotal2 - militotal1;
 
console.log( total );

El código es algo largo y confuso en cuanto a estructura pero plenamente funcional.

Firebug

Una forma más limpia sería utilizando nuestra herramienta para el debug por excelencia: Firebug. Como vimos en el artículo Consola de Firebug al detalle, podemos usar los métodos time y timeEnd para realizar mediciones precisas:

var num_cicles = 1000;
 
console.time('Checking Normal');
for( var x = 0; x < num_cicles; x++){
  // the algorith goes here...
};
console.timeEnd('Checking Normal');

Mucho más simple; sin embargo, este test se realiza exclusivamente sobre Firefox y no siempre éste es el escenario real final. Con tanto navegador y motor Javascript independiente, tenemos que tener en cuenta que la eficiciencia de un algoritmo puede variar de una plataforma a otra. Esto hace que resulte interesante realizar los tests en el mayor número de ellas posible.

JsPerf

Una de los recursos online más interesante con los que cuenta el desarrollador Javascript es JsPerf, una herramienta de medición (benchmark) que permite comprobar el número de ciclos que un script ejecuta durante un tiempo dado. Tiene como limitación el que no podemos configurar el número de iteraciones que queremos testear, pero como ventaja, contamos con la facilidad de ejecutar los tests en cuantas plataformas deseemos mediante un acceso simple a la URL donde se guarda el test.

Varias veces hemos utilizado este servicio para comparar el rendimiento de varios scripts. Por ejemplo, cuando pusimos a prueba el dispositivo Duff, o cuando generamos secuencias sin utilizar bucles ni condicionales.

Conclusión

En esta introducción hemos presentado algunas de las nociones básicas a la hora de diseñar algoritmos: hemos dado una definición sencilla de qué son y estudiado cómo evaluar su eficiencia a través de un sistema de medición como Big-O. También hemos repasado algunas de las herramientas más utilizadas para consultar los tiempos de ejecución y hemos puesto algunos ejemplos sencillos.

Aunque el tutorial está diseñado sobre Javascript, todo lo visto es fácilmente portable a cualquier otro lenguaje de programación.

En próximas entregas, haremos hincapié en conceptos más avanzados de optimización y refactorizado además de mostrar algunos de los algoritmos más inteligentes que podemos encontrar en Javascript.