Lo deseable cuando escribimos cualquier algoritmo, es que este sea tan rápido como sea posible. Desafortunadamente, no siempre es lo más indicado, bien porque no se disponga de tiempo para codificarlo o bien porque supondría una complejidad adicional en el despliegue (ej. precálculos, caché, librerías) y/o en el propio código por cuestiones de legibilidad y mantenimiento.
Sin embargo, no cabe duda de que no sólo en aplicaciones con marcado carácter computacional (financieras, simulación física, graficación, juegos, etc…) es deseable la máxima optimización. Páginas web dinámicas, un fluido interface de usuario (Tablet, PC o navegador), procesos en segundo plano en nuestro servidor y en otras tantas situaciones podemos obtener múltiples beneficios (mejor experiencia de usuario, menor consumo de cloud contratado, no necesitar hardware adicional, etc…) si procuramos escribir un código eficiente.
Así, te invito a practicar conmigo en la optimización del código con un sencillo ejemplo. ¿Te animas?.
Breve introducción
Existen muchos tipos de optimización en los algoritmos. Éstos pueden ser de índoles muy diferentes. La optimización puede estar orientada al hardware como por ejemplo, el instalar un segundo disco para minimizar los bloqueos entre procesos que escriben y leen. Otras optimizaciones se centran en el lenguaje concreto sobre el que trabajamos, cambiando una “palabra” por otra, podemos obtener un mejor desempeño (eg. en Haskell, cambiando concat $ map por concatMap o en otros haciendo el cambio String por StringBuilder). Otras consisten en un cambio en la estrategia basada en una combinación de las anteriores (una típica es aquella que consiste en cambiar un tipo genérico Integer por uno concreto y más eficiente a nivel de compilador y hardware como Int32).
Pero sin duda, la mejor forma de optimizar un algoritmo es mejorándolo, reemplazándolo por otro en el que el número de operaciones requeridas para hacer el trabajo, sea menor que en el anterior.
Sin embargo, ésto último no siempre es cierto, “¿cómo?” te dirás, “¿usar un algoritmo más eficiente es peor que usar otro menos eficiente?”. Pues sí, la cuestión es que un algoritmo no siempre se comporta igual. Hay algoritmos que (es solo un ejemplo) funcionan igual de bien (o mal) con independencia de que deban procesar uno o miles de datos, otros sin embargo, funcionan bien para pocos datos pero con muchos se vuelven penosos, etc…
La eficiencia de los algoritmos es la materia de estudio de la Complejidad computacional, sin embargo, como es verano y hace calor, comentaré implícitamente algunos aspectos de dicha teoría revisando cuatro soluciones diferentes a un mismo problema.
El problema
Como es habitual, lo más fácil es plantear un problema “matemático”, esto es así porque de forma sencilla y concisa, se puede poner un problema que condense toda la dificultad que queremos mostrar sin tener que poner un ejemplo “empresarial” que sería largo y aburrido (recuerda el ejemplo de mi post de Microcódigo en mi código).
De todos modos, si se te ocurren problemas “cotidianos” que no tengan un enunciado demasiado largo, puedes postearlo en los comentarios o en Solveet.
El problema propuesto consiste en calcular todos los factoriones que existen, por simplificar un poco, vamos a suponer que nos indican que no existen factoriones mayores que un N dado. Bien, ¿qué es un factorión?:
Un factorión es un número natural (1, 2, 3, …) tal que, si tomamos todos sus dígitos decimales y sumamos sus factoriales, volvemos a obtener ese mismo número.
Por ejemplo, el número 1024 tiene por dígitos decimales a {1, 0, 2, 4}, los factoriales (recuerda que el factorial de n se denota n! y es igual al producto de los n primeros números naturales, es decir, n! = 1 × 2 x … x n) de esos dígitos son {1, 1, 2, 24} cuya suma total hace 28, y como no nos ha dado 1024, resulta que 1024 no es un factorión.
Por otro lado, el número 145 tiene por dígitos {1, 4, 5} cuyos factoriales son {1, 24, 120} y su suma es precisamente 145, luego 145 sí es un factorión.
Solución ingenua
Se suele llamar “solución ingenua” a la solución evidente, la que se escribe sin pensar. Es un término común en ciencias de la computación, no pienses que lo he puesto yo. Dicha solución, consiste en usar la potencia del ordenador para que revise, uno a uno, todos los números, aplicando directamente la definición sin pensar, ¡a veces es la mejor solución posible!.
Si usamos Python, una forma de escribir directamente una solución sería así:
¿Cómo se optimiza?
La forma de optimizar cualquier algoritmo, consiste en conocer y entender sus propiedades y las del problema a resolver, “¿propiedades?”, sí, sólo vamos a poder actuar sobre aquellas propiedades que conozcamos, por ejemplo, viendo el algoritmo en Python, se puede ver que para cada i estamos calculando una y otra vez los factoriales de los mismos dígitos (sólo hay 10 dígitos decimales, del 0 al 9), aunque sea una propiedad evidente, es una propiedad bien conocida que el factorial de 9 es siempre 362.880, si siempre es 362.880, nos podemos ahorrar las 8 multiplicaciones que requiere obtenerlo si lo dejamos precalculado en una matriz. Es decir, dejar en una matriz los 10 factoriales de los 10 dígitos posibles.
La propiedad de que el factorial de un número n no cambia es conocida e interesante. Una propiedad de la función rand() es justo la contraria, el valor devuelto puede tomar (o no) un nuevo valor diferente cada vez. Si no conocemos las propiedades de las cosas, no podremos controlarlas eficientemente.
Optimizar el código
Como decía en la introducción, una forma de optimizar la ejecución, es mejorando el código, aunque el algoritmo sea el mismo (técnicamente el algoritmo será diferente, pero el proceso teórico, el algoritmo teórico seguirá siendo el mismo). En nuestro ejemplo, una forma evidente es precalcular los factoriales de cada dígito, pero hay otra cosa que se puede hacer que creo te va a gustar.
Una propiedad que tiene la definición de factorión es que, si tengo calculada la suma de los factoriales de los dígitos del número n, para calcular la suma de los factoriales de los dígitos del número n + 1 sólo tengo que sumar y restar aquellos dígitos que sean diferentes ¡a que es genial! (esta propiedad ya no es tan evidente ¿eh?). Probablemente lo veas mejor con un ejemplo (es sencillo, ya verás):
Para n = 10321041, tenemos que hacer 1 + 1 + 1 * 2 * 3 + 1 * 2 + 1 + 1 + 1 * 2 * 3 * 4 + 1 = 37.
Para n = 10321042, tenemos que hacer 1 + 1 + 1 * 2 * 3 + 1 * 2 + 1 + 1 + 1 * 2 * 3 * 4 + 2 = 38.
¿En que se diferencian?, ¡únicamente en el dígito que cambia!, es decir, si tenemos calculada la definición para n = 10321041, para saber cuanto vale la de n = 10321042, únicamente tenemos que restar el factorial del dígito que sale (1) y sumar el factorial del dígito que entra (1 * 2 = 2).
“¿Y esta propiedad es interesante?”, mucho, porque significa que en 9 de cada 10 números de los millones que tengamos que revisar sólo tendremos que hacer una resta y una suma ¿no es genial un ahorro del 90%?. Nota: cuando el primer dígito pase del 0 al 1, del 1 al 2, …, del 8 al 9, podemos aplicar la propiedad anterior, cuando del 9 pase al 0 no, porque pasará a las centenas, pero en éstas, sólo serán 2 restas y 2 sumas y no será ¡hasta los miles! que deberemos calcular 3 restas y 3 sumas, etc… desde luego, un ahorro impresionante.
En la práctica, el código siguiente lo único que hace es contar de 0 a N, pero en lugar de usar el operador suma (n = n + 1), lo hace como en el cole, mantiene un array con dígitos que inicialmente valen 0 y va sumando “llevando una”. No detallaré el algoritmo por no aburrir demasiado, pero puedes usar los comentarios si quieres que aclare algo.
Aún se puede optimizar más el código, por ejemplo, una propiedad interesante del procedimiento que hemos establecido, es que siempre se resta y suman los mismos factoriales, por ejemplo, del dígito 0 siempre se pasa al 1, del dígito 1 siempre se pasa al 2, etc… en lugar de restar y sumar ¿porque no precalculamos esa resta y suma y así sólo hacemos una suma? ¡acabamos de reducir a la mitad el número de sumas (y restas)!.
No obstante, no merece la pena ahondar más aquí, ahora veremos una forma mejor.
Optimizar reescribiendo el algoritmo
Entre nuestro primer algoritmo ingenuo y el segundo, realmente no hay ninguna diferencia, son el mismo algoritmo, lo único que el segundo corre muchísimo más rápido. Digamos que tenemos que seguir yendo de Madrid a Barcelona, pero en lugar de a 50 Km/h lo hacemos a 1540 Km/h. Lo que vamos a hacer ahora es ¡un agujero de gusano para atravesar el espacio tiempo y teletransportarnos de Madrid a Barcelona! “¿cómo?”, conociendo las propiedades de los factoriones y aprovechándonos de ellas por supuesto.
Si volvemos a mirar como se calcula la definición que deben cumplir los factoriones:
Para n = 10321041, tenemos que hacer 1 + 1 + 1 * 2 * 3 + 1 * 2 + 1 + 1 + 1 * 2 * 3 * 4 + 1 = 37.
Nos fijamos que la suma tiene la propiedad conmutativa, ¿porqué es importante saber eso?, porque en cualquier objeto que cumpla dicha propiedad, podemos cambiar el orden de los elementos sin que afecte al resultado final, es decir, el número anterior, lo podemos reescribir como: 00111234. Es decir, todos los números que pueden escribirse con los mismos dígitos podemos calcularlos una única vez.
Si por ejemplo nos dicen que busquemos factoriones de 1 a 10.000.000, con los algoritmos anteriores tendríamos que revisar todos y cada uno de los 10 millones de números, sin embargo, si usamos la nueva propiedad únicamente tendremos que revisar 11.440 ¡hemos reducido el problema un 99,8856%! (ojo, antes reducíamos las operaciones en un 90% pero sólo de cada uno de los millones de números a revisar, es decir, teníamos que seguir revisando millones de números, ¡pero es que ahora hemos reducido el problema a sólo revisar unos pocos números!).
“¿Y como se usa esta propiedad?”, bueno, sólo tenemos que generar las combinaciones con repetición de los dígitos involucrados. Tampoco explicaré el código siguiente, cualquier aclaración por favor, siéntete libre de indicarla en los comentarios:
Éste código sin embargo, no es más rápido que el anterior en C para valores de N inferiores a unos tres millones, a partir de ahí, este último código en Haskell deja en pañales al de C.
Optimizando a lo Agente Smith
“¿Aún podemos optimizar más?”. ¡Claro!, igual que el Agente Smith en la pelicula Matrix, no sólo vamos a teletransportarnos instantáneamente de Madrid a Barcelona, además, ¡nos vamos a clonar para ser muchos simultáneamente!.
En general, no siempre podemos paralelizar nuestros algoritmos pero, una propiedad muy interesante de nuestro último algoritmo, es que el cálculo de las combinaciones con repetición se hace recursivamente y de forma independiente (en los algoritmos de Python y C, las variables y matrices eran compartidas para cada número a revisar), es decir, lo podemos paralelizar muy fácilmente añadiendo un simple parMap:
De todos modos, para números tan pequeños (decenas de millones) no merece la pena, porque hemos optimizado tanto y tan bien, que incluso en mi humilde Atom D510 sólo le lleva unos pocos milisegundos.
¿Se puede mejorar al Agente Smith
Pues sí, existen propiedades adicionales que no hemos explotado como por ejemplo, que la suma parcial de la definición debe ser menor o igual que el número que revisamos (algo evidente, claro). Es decir, si estamos verificando el número 999.999, vemos que cuando llevamos sumados los factoriales de tres dígitos ya nos da 1.088.640, por lo que no hace falta que sigamos sumando para saber que no es un factorión.
¿Sabías que el estudio de las propiedades (y relaciones) de las cosas es el objetivo de las matemáticas?.
Curiosidades sobre los algoritmos escritos
El código Python tiene un coste O(n) y es lento y aburrido.
El código C tiene un coste O(n) y es muy rápido ¡sólo unos 10 ciclos de reloj para cada número!.
El código Haskell sin paralelizar tiene un coste O(log n) y aunque no es rápido en ejecución, efectúa muchísimas menos operaciones que los anteriores.
El código Haskell paralelizado, tiene un coste O((log n) / c) donde ‘c’ es el número de hilos que le dejamos para ejecutar; si tenemos un AMD Phenom II X6 con seis cores, tardará seis veces menos que el Haskell anterior.
Conclusión
Como programadores debemos ser capaces de escribir un código eficiente, utilizar el algoritmo ingenuo es cómodo y tentador, pero hay muchas situaciones en las que un programador bien entrenado (no acomodado en que simplemente, funcione) puede fácilmente optimizar un código y obtener un producto mejor. Ni las mejoras son mínimas si las hemos ido realizando desde el principio del desarrollo, ni el código se complica innecesariamente si las hacemos de forma inteligente. A veces únicamente será cambiar la forma de aplicar una instrucción, otras declarar una pequeña matriz para precalcular algún resultado e incluso otras, complicaremos conscientemente el algoritmo asumiendo el coste de mantenimiento.
Si no hay una razón para no escribir un buen código, ¿porqué no hacerlo?.
En Genbeta Dev | Solveet.
Más información | Combinaciones con repetición.
Más información | Problema factorión.
Más información | Complejidad computacional.