Introducción
En el artículo Introducción al diseño de algoritmos en Javascript habíamos repasado algunos de los conceptos fundamentales a la hora de programar funciones eficientes en Javascript. En concreto, habíamos estudiado cómo la complejidad de un algoritmo determina su calidad mediante el sistema de notación Big-O. Sin embargo, tal y como advertimos, medir la complejidad de un código no siempre es una tarea sencilla; necesitamos tener claros cuáles son los criterios que determinan esa característica.
Para ayudarnos en la evaluación, tenemos que necesariamente recurrir a métricas: una serie de reglas establecidas por convención que vienen a determinar diferentes índices presentes en una determinada porción de software.
En esta ocasión, vamos a revisar una de las más extendidas y más sencillas de comprender: la métrica de complejidad ciclomática.
Concepto
Por complejidad ciclomática, entedemos el valor obtenido tras el recuento del número de caminos lógicos individuales que un programa debe evaluar hasta obtener un resultado o, dicho de otro modo, es el cálculo metódico de la complejidad lógica de un programa.
Este sistema, con una gran aceptación entre la comunidad, tiene la característica de que fue diseñado para aplicarse con independencia de los lenguajes de programación aplicados. Ésto, significa que, aunque a que aquí lo revisaremos desde la perspectiva de desarrolladores Javascript, es aplicable a cualquier otro entorno.
Durante su planteamiento, Thomas McCabe utilizó la teoría y flujo de grafos para determinar el grado de complejidad ciclomática de un programa o algoritmo: así, cada porción de código a evaluar representa un grafo independiente donde cada instrucción se identifica con un nodo y cada posible vía de ejecución una arista.
Tomemos el siguiente ejemplo:
var foo = 0, // 1 bar = 10; if( foo == 0 ){ // 2 if( bar == 10){ // 3 console.log( 'foo = 0'); // 4 console.log ('bar = 10'); }else{ console.log('Only foo = 0'); // 5 } } |
Los números colocados en los comentarios, representan las instrucciones, nodos o sentencias a cumplir por el programa. La presencia de dos condicionales determinan que existen 3 caminos posibles para completar la secuencia que cubre desde el nodo 1 al 6:
- Camino 1: ambos condicionales se cumplen; se ejecutan las sentencias 1,2,3,4 y 5
- Camino 2: se cumple el primer condicional pero no el segundo; se ejecutan las sentencias 1, 2 y 5
- Camino 3: no se cumplen ninguno de los condicionales; se ejecuta únicamente la sentencia 1
Como veremos más adelante, la complejidad ciclomática de este fragmento tendría un valor de 3, lo que indica que estamos ante un programa simple con un índice de riesgo bajo.
Aplicando la complejidad ciclomática en Javascript
Este tipo de métricas puede aplicarse tanto a porciones de software como a programas completos. Resulta más frecuente dentro de la algoritmía el primer caso, bien sea para una función concreta si estamos utilizando el paradigma funcional o bien en un objeto si estamos trabajando con POO. Para este último caso, si los objetos son muy grandes, aplicaríamos la medición a cada uno de sus métodos.
En este artículo vamos a analizar un caso práctico aplicado al contexto de una función Javascript. Tomaremos un ejemplo clásico, el Algoritmo de Euclides, cuya finalidad es obtener el máximo común divisor de dos de números dados.
El Algoritmo de Euclides (en su versión tradicional) determina que al dividir a entre b (números enteros), se obtiene un cociente q y un residuo r. Es posible demostrar que el máximo común divisor de a y b es el mismo que el de b y r. Es importante tener en cuenta que el máximo común divisor de cualquier número a y 0 es precisamente a. Para fines prácticos, la notación MCD(a,b) significa máximo común divisor de a y b.
Según lo antes mencionado, para calcular el máximo común divisor de 2366 y 273 se puede proseguir de la siguiente manera:
Paso | Operación | Significado |
---|---|---|
1 | 2366 dividido entre 273 es 8 y sobran 182 | mcd(2366,273) = mcd(273,182) |
2 | 273 dividido entre 182 es 1 y sobran 91 | mcd(273,182) = mcd(182,91) |
3 | 182 dividido entre 91 es 2 y sobra 0 | mcd(182,91) = mcd(91,0) |
La secuencia de igualdades anterior concluye que MCD(2366, 273) = 91. Todo este proceso, transcrito a una fórmula, sería MCD( A, B ) = MCD( B, A mod B ).
Como podemos intuir comprobar a simple vista, se trata de un algoritmo de tipo recursivo. Portado a pseudo-código obtendríamos:
gcd( a, b ){ if( ( a mod b ) > 0 ) { result = gcd( b, a mod b ); } else { result = b; } return result; } |
A partir de este esquema, podemos crear fácilmente la función Javascript:
function GCD(a,b){ var result; if(a % b > 0){ result = GCD( b, a % b ); }else{ result = b; } return result; } |
Y con esto, tenemos una función recursiva compuesta por un condicional completo (if…else). Veamos ahora la complejidad de nuestro algoritmo aplicando el criterio ciclomático.
Aplicando la complejidad ciclomática
Si pasamos el código anterior a un diagrama de grafo, obtenemos la siguiente estructura:
Tenemos así 5 nodos o instrucciones (los globos amarillos) y 5 aristas (identificadas con las flechas). Aplicamos ahora la fórmula clásica de complejidad ciclomática:
V(G) = e – n + 2
Donde:
- e es el número de posibles ramificaciones que el programa puede adoptar (aristas)
- n es el número de nodos
Para nuestro caso de estudio:
V(G) = 5 – 5 + 2
Por lo que tendríamos que nuestro algoritmo tiene una complejidad ciclomática 2 ( 5 – 5 + 2 = 2 ). Este valor, si lo cruzamos con la tabla orientativa elaborada a partir de los análisis de McCabe, nos da como resultado un programa evaluado como de poco riesgo:
Complejidad Ciclomática | Evaluación del riesgo |
---|---|
1-10 | Programa Simple, sin mucho riesgo |
11-20 | Más complejo, riesgo moderado |
21-50 | Complejo, Programa de alto riesgo |
+50 | Programa no testeable, Muy alto riesgo |
Podemos por tanto concluir que nuestro algoritmo no presenta una profundidad excesiva y sería fácilmente gestionable.
Herramientas de medición online
Para medir la complejidad ciclomática de un algoritmo o función Javascript podemos recurrir a herramientas online que se encargan de analizar el código siguiendo diversos criterios. Un ejemplo de este tipo de utilidades es JsMeter.
JsMeter nos permite pegar una porción de código para evaluarla según el número de condicionales anidados que presente. El resultado podemos comprobarlo tanto en un cuadro resumen como en una gráfica:
El resultado obtenido con nuestro Algoritmo de Euclides es, según este sistema, de una complejidad ciclomática 3.
Midiendo la complejidad de jQuery
Como curiosidad, hemos cogido el código de la última versión de jQuery (la 1.6.1 en el momento de escribir este artículo) y hemos sometido diversos métodos al test para comprobar su complejidad ciclomática. Estos son los resultados obtenidos:
Método / Módulo | Complejidad Ciclomática |
---|---|
Sizzle | 49 |
init | 38 |
Add | 24 |
Extend | 20 |
Each | 10 |
Como es previsible, el motor de selección Sizzle es la porción que mayor complejidad presenta seguida por el método de inicialización (init) y la asociación de eventos (add). En líneas generales, podemos concluir que jQuery presenta un nivel moderado de complejidad ciclomática con un mantenimiento general del sistema que roza el alto riesgo.
Conclusión
En esta ocasión, hemos abordado un sistema de medición de complejidad que podemos aplicar tanto a nuestros algoritmos, a funciones o a determinadas porciones de código. El objetivo de estos análisis es contar con más herramientas para evaluar la eficiciencia y calidad de un programa así como el riesgo potencial de posibles fallos durante su ejecución.
La conclusión es lógica: un algoritmo o función resulta más eficiente cuanto menor sea su complejidad. Este sistema que hemos analizado, y que data de mediados de los 70, es uno de los que mayor aceptación tienen entre la comunidad de desarrolladores y puede resultar interesante conocer tanto su concepto como la forma de aplicarlo a nuestros diseños.
Genial e interesante post Carlos!
Por si no me he enterado bien ¿la conclusión que sacamos en el testeo de jQuery es que su código es complejo, poco eficiente y de difícil mantenimiento?
Sería muy interesante ver una comparativa con otras librerías, por ejemplo, Dojo y Mootols.
Un saludo!
Bueno; la conclusión que podemos sacar sería parecida a la que comentas, pero hay que tener en cuenta de que siempre estamos hablando desde un nivel teórico. Me explico: analizando algunas funciones de jQuery, encontramos que según los sistemas de medición de complejidad (en este caso sólo uno, aunque el más aceptado), su estructura general es efectivamente de una complejidad moderada/alta. Esto no significa que sea poco eficiente; esa medida es siempre relativa: aunque resulta obvio y natural comparar complejidad con rendimiento, las distintas formas en que se estructura la lógica (la arquitectura) determina el grado real de optimización. jQuery, como todos presuponemos, es muy eficiente dada su complejidad porque hace uso de numerosos patrones de diseños y técnicas que han demostrado repetidamente su eficiencia.
Finalmente, el tema del mantenimiento tiene ‘truco’: si tomamos por ejemplo la función init, nos encontramos con una importante batería de if…else(s) que van condicionando consecuentemente el flujo. Esto resulta extremadamente difícil de mantener dado que hay multitud de caminos posibles a evaluar. Detectar un error dentro de esta estructura puede resultar una pesadilla… pero eso es según la teoría más tradicional de un desarrollo. jQuery, buscando precisamente evitar este problema y haciendo uso de las metodologías modernas, está programando siguiendo el paradigma del TDD (aplicado con QUnit) con una cobertura de código cercana al 100%. Esto quiere decir que existen tests unitarios que se encargan de comprobar prácticamente cada línea de código haciendo que la detección de errores sea fácil y rápida.
Como vemos, el conocimiento de estas técnicas, metodologías, prácticas y métricas permite aplicar un desarrollo responsable de un software y evitar los futuros problemas derivados del mantenimiento, escalabilidad y rendimiento.
Queda pendiente esa comparación entre las bibliotecas más populares.
Saludos!
Digamos entonces que sometiendo a TDD’s un código muy complejo nos aseguramos un mantenimiento y detección de bugs más que óptimo, y por supuesto, sin mermar el rendimiento, ¿no?
Tengo que tomarme en serio los TDD’s… xD
Muchas gracias por la respuesta Carlos, y por tu tiempo 🙂