Hace unos años presencié una discusión entre dos programadores sobre la «eficiencia de los programas«. Ellos discutían sobre la manera de especificar el problema en la herramienta CASE que utilizaban, para que el programa generado fuera más «eficiente«. La discusión era acalorada y tenían visiones muy diferentes del asunto (yo, al no conocer ni de cerca la herramienta en cuestión, no entendía ni media palabra de sus argumentos).
Hasta que en un momento no pude contenerme y decidí meter el dedo en el ventilador: A ver, una pregunta, ¿cuándo un programa es más eficiente que otro? – les dije. Para mi asombro (aunque debería haberlo intuído), ambos me respondieron al unísono: ¡Cuando es mas corto!.
No soñaría por un instante que la mayoría de los programadores viven en tal ignorancia, pero sin embargo muchos no tienen demasiada claridad acerca de este asunto. Más aún, ni siquiera son conscientes de la enorme diferencia que puede haber, a la hora de la ejecución, entre dos programas equivalentes pero de diferente complejidad temporal. Pensando en esto, recordé un ejemplo utilizado por dos de mis mejores profes en un artículo llamado «La perplejidad como recurso didáctico«.
Este ejemplo muestra cómo un cambio aparentemente sutil en un algoritmo puede impactar tremendamente en el rendimiento del programa resultante.
El problema
Supongamos que tenemos que escribir un programa para calcular potencias naturales de 2. Para ello podemos usar las operaciones aritméticas de suma y producto.
Una solución posible sería calcular:
- 20 = 1
- 2n = 2 * 2n – 1, para n > 0
Una alternativa sería considerar el caso «n > 0″ de forma diferente: sumando dos veces 2n – 1 en vez de multiplicando por 2. Esto es:
- 20 = 1
- 2n = 2n – 1 + 2n – 1, para n > 0
Puede verse claramente que ambas soluciones son matemáticamente equivalentes.
A continuación, el código en lenguaje pascal de las dos soluciones (pow1 y pow2, respectivamente). Por simplicidad se ha declarado el exponente a calcular como una constante igual a 10:
pow1.pas
program pow1;
const exp = 10;
function pow(n: integer): integer;
begin
if n = 0 then
pow := 1
else
pow := 2 * pow(n-1);
end;
begin
writeln(pow(exp));
end.
pow2.pas
program pow2;
const exp = 10;
function pow(n: integer): integer;
begin
if n = 0 then
pow := 1
else
pow := pow(n-1) + pow(n-1);
end;
begin
writeln(pow(exp));
end.
Complejidad temporal
Sin entrar en demasiados detalles técnicos (ver los enlaces al final del artículo), analizaremos la eficiencia de cada uno de estos programas.
Primero vamos a suponer que el costo en tiempo de realizar las llamadas recursivas es despreciable y que el costo de realizar una suma o una multiplicación es una unidad de tiempo (luego veremos que esto no afecta el resultado que nos interesa destacar).
En el caso de pow1 vemos que la primera llamada a pow se hace asignando a n el valor inicial exp, y luego en cada llamada recursiva este valor se decrementa en 1. Esto significa que para calcular 2n se harán n llamadas recursivas (multiplicando en cada caso el valor resultante por 2), lo cual insumirá n unidades de tiempo.
En el caso de pow2 la situación es diferente: en cada llamada a pow se hacen dos nuevas llamadas recursivas, para luego sumar los resultados. Esto significa que para calcular 2n se harán 2n llamadas recursivas (sumando en cada caso los valores resultantes), lo cual insumirá 2n unidades de tiempo.
De este análisis se desprende que pow1 requiere de un tiempo del orden de n (lineal), en tanto que pow2 requiere de un tiempo del orden de 2n (exponencial).
¿Y todo esto qué significa?
En términos prácticos todo esto significa, ni más ni menos, que pow1 es un programa que resuelve el problema de forma razonable (aunque podría ser mucho más eficiente), en tanto que pow2 es (al menos si pensamos en valores grandes de n) una porquería.
Supongamos que tenemos una computadora capaz de ejecutar 1.000 operaciones por segundo. La siguiente tabla muestra aproximadamente cuánto tardaría la ejecución de cada uno de nuestros programas para distintos valores de n.
| n | pow1 | pow2 |
|---|---|---|
| 10 | 0,01 seg | 1 seg |
| 20 | 0,02 seg | 17 min |
| 30 | 0,03 seg | 12 días |
| 40 | 0,04 seg | 34 años |
| 50 | 0,05 seg | 35.700 años |
| 100 | 1 seg | 3.000 millones de veces la edad del universo |
Si bien 1.000 operaciones por segundo no parece una velocidad razonable para una computadora de estos tiempos, podríamos multiplicarla por varios millones y aún no podríamos calcular 2100 usando el programa pow2.
Lo más notable es que no importa si la computadora que utilicemos es «2 veces», «10 veces» o «100 veces» más rápida: el salto en las diferencias de tiempo, pasado determinado valor de n se mantendrá de todas formas.
Amén de que se trata de un ejemplo arbitrario (pero contundente), vale para mostrar la gran importancia que puede tener sobre la eficiencia de un programa una pequeña modificación sobre el algoritmo utilizado. Lamentablemente no es poco común ver programas que se ejecutan razonablemente bien con una pequeña cantidad de datos, pero cuyo funcionamiento se vuelve intolerable cuando estos crecen.
Cada vez que pienso en esto, me pregunto qué será de aquellos dos programadores y los usuarios de sus sistemas…
Lecturas adicionales
A continuación, algunos enlaces con información sobre complejidad computacional:
Juas. Pow1 y pow2 fueron parte de un examen de programación que hice… Nos daban pow2 y nos pedían que optimizaramos el programa, siendo pow1 la solución que pedían.
Buen articulo. ;)
Muy buen artículo Javier.
Yo me dedico a la informática desde hace ya bastantes años y siempre en grandes instalaciones por lo que el ‘performance’ es muy importante y sí, por desgracia hay gente que opina que el mejor programa es el mas corto.
Mi granito de arena es que otra cosa que hace que un programa sea bueno, es que sea legible por otra persona que no sea quién lo codificó!
Un saludo ;)
Ilustrativo, y me gustaría agregar que cuando se analiza la complejidad de un algoritmo lo que se hace básicamente es contabilizar la operación «más gastadora» (ya sea en tiempo, memoria o ancho de banda) o el cojunto de «operaciones gastadoras» que se realizan cuando el programa recibe una entrada de tamaño «n» .
Y me sorprende bastante que haya gente que se dedique profesionalmente al desarrollo de software sin conocer este tema, es básico, en tercer semestre en ciencias de la computación se lleva todo esto junto con estructuras de datos y después en quinto semestre se lleva «análisis de algoritmos» a donde se analiza cuando un problema es NP completo, entonces es interesante porque podrías retar a un programador que alardee de ser muy bueno para que resuelva un problema NP completo con una entrada «n» grande en corto tiempo, y usen las herramientas que usen para optimizar código no podrá resolverlo en un tiempo razonable.
Creo que es un tema muy muy importante, porque no entiendo como es que alguien al que le paguen por programar entregue un programa que tenga complejidad exponencial, o sea, ¿como es posible que no se los avienten en la cara si el programa se tarda dos horas resolviendo algún problema?
Interesante artículo, sobre todo porque el área de los algoritmos y la complejidad temporal es algo que no se ve habitualmente en muchos sitios.
También aprovecho para, si se me permite, expresar el desagrado que me causa ver el uso de ciertos anglicismos, como «la performance», cuando existen términos adecuados y correctos en español, como «el rendimiento».
En primer curso de Ingenieria Informatica se hace hincapie en este tema y se utilizan varias formulas y tecnicas para medir la complejidad temporal. Es un asunto que no debe tomarse a la ligera, sobretodo si pretendemos ser buenos programadores.
Buen articulo ( y yo que pense que lo de la complejidad no servia para nada¡).
Pena que a la hora de currar esto ni se mire ni se valore. El tiempo apremia y no quieren que lo dediques a pensar estas cosas :/
Un interesante artículo que resume toda una asignatura de informática. Enhorabuena por la sencillez y brevedad de la explicación. Tendrías que ser profesor.
Excelente artículo.
Hace ya bastantes años en los que me dedico a esto de programar y ciertamente he visto pasar delante mía a muchos programadores (y muchos jefes) para los cuales lo mejor es lo mas corto, sin llegar a comprender que lo mejor es lo más eficiente.
Yo creo que es un problema de pereza. Sí, sí, de pereza.
Un dia en la cafeteria de la empresa donde trabajo debatiamos un tema similar y como contrarreplica a mi interlocutor le hice el siguiente simil:
-«Vamos que para hacerte la tortilla ahora solo necesitas cascar un huevo, el resto te lo hace la cocina totalmente sola. ¿Genial no?»
-«Sí, si que lo es.»
-«¿Aunque te mueras de hambre antes de que acabe?»
Un saludo.
¿¿era imprescindible utilizar «performance» en lugar de rendimiento??
Antes que nada, agradezco todos los comentarios y el tiempo dedicado a la lectura de este artículo.
Con respecto a las críticas por el uso del anglicismo «performance», tienen toda la razón.
Normalmente pongo especial cuidado en este tipo de errores (nuestro idioma es lo suficientemente rico como para tener que usar estos recursos), pero esta vez se me pasó. Ya está corregido.
sisiP!!
Ultimamente la programacion se ha convertido en uno de los sucesos mas grandes de la historia…
no se si eso esta bien o mal en este mundo.. pero con el correr de los años la informatica ha ido avanzando progresivamente….
Desde España Un saludo Muy Grande!!
=)
Adios y hasta la proxima!!!
YoP
no lo lei pero a mi punto de vista no me gusta nada
no te creas lo que no sos
Buen ejemplo.
Pero no creo que los informáticos sean tan tontos.
Sin ir más lejos, los mismos compiladores que usan tienen siempre una opción de «Optimizar por tamaño» y «Optimizar por velocidad», y eso ya dá una idea de que algo pasa, no?
También hasta el más bruto sabe que si, en vez de hacer un bucle que se ejecute 3 veces, se copia 3 veces seguidas el código, será más largo, pero más rápido, no?
Salut.
Hola, comentas un articulo: «La perplejidad como recurso didáctico», este tipo de textos me atraen mucho, cuando un profesor te impresiona es genial. Por casualidad no lo tendras contigo, lo he buscado por inet sin exito y quizas tu me lo puedas pasar.
Muchas gracias y un saludo.
me parece bueno el ejemplo me gustaria mas infpormacion acerca del tema analisis de eficincia y comlpjidad de la solucion
«¡Cuando es mas corto!» Joder, ¿Y donde han aprendido a programar?; siendo yo de FP nunca diria tal chorrada
Gracias por el artículo, fue divertido leerlo.
Conclusión…
La eficiencia no es hacer más con menos es hacer lo mejor con lo que se requiere :D.
P.D.: No soy profesional en sistemas pero ando de metiche.