La importancia de un buen algoritmo

por:

 

La importancia de un buen algortimo

 

Hacía tiempo que no dedicábamos una entrada específica relacionada con el mundo de la programación. Hoy vamos a hablar sobre los algoritmos, las distintas maneras de crearlos y los comportamientos de unos frente a otros.

Podríamos resumir el término algoritmia, como la ciencia que estudia los algoritmos, tanto su creación como su análisis. Para conseguir mejoras y seleccionar el más efectivo para cada tarea.

La algoritmia : la base de un buen programa

Muchos usuarios cuando empezamos a programar, utilizamos la típica frase de “lo importante es que funcione”, claro que es importante que el programa funcione. Pero si hay cuatro programas que cumplen con el objetivo, seguramente los cuatro no afronten el problema de la misma manera.

Para resolver un problema, se pueden utilizar múltiples métodos y algoritmos ya creados, aunque normalmente estos los tenemos que utilizar como base para crear nuestro algoritmo. El algoritmo debe ser refinado tanto como sea posible para agilizar el tiempo que tarde en ejecutarse nuestro programa.

Por ejemplo, si partimos de un programa que gestione facturas con unas 1000 líneas de código, no hay que buscar la optimización línea por línea, sino mirar que parte es la que tarda más tiempo, por ejemplo la ordenación y afrontar esta parte del programa, buscando mejorar su algoritmo. Hay algunos algoritmos que son difícilmente mejorables y otros que simplemente no se pueden mejorar, pero la mayoría de ellos suelen tener mejoras muy interesantes.

La creación de un algoritmo : un sencillo problema

Supongamos el problema: quiero que me hagas una lista de los números múltiplos de 4 y de 5 al mismo tiempo que hay en el rango 1-1.000.000

Lo primero que piensa un usuario, principalmente si es novato es utilizar el típico método de fuerza bruta:

#include <stdio.h>
#include <stdlib.h>
 
int main(){
int i;
int flag=0;
    for(i=1;i<1000001;i++){
        if(i%4==0){
            flag=1;
        }
        if(i%5==0 && flag==1){
            printf("%d\n",i);
        }
    }

return 0;
}

Este es el típico ejemplo de “pero si ya funciona, para que lo voy a mejorar”. Lo importante es que este sistema hace 3.000.000 comparaciones, por cada número compara si es múltiplo de 4 y si es de 5 y si cumple las dos condiciones, lo muestra.

Refinando el algoritmo

Seguro que alguno de nuestros lectores ha encontrado una sencilla manera de mejorar el código:

#include <stdio.h>
#include <stdlib.h>

int main(){
    int i;
    for(i=1;i<1000001;i++){
        if(i%4==0 && i%5==0){           
            printf("%d\n",i);           
        }
    }
return 0;

}

Este sencillo arreglo evita un gran número de comparaciones, porque si el número no es múltiplo de 4 para que vamos a calcular si es múltiplo de 5, si ya no cumple la propiedad que nos pide el problema.

Repensando el algoritmo

Muchas veces nos quedamos atascados pensando que nuestra manera, es la mejor forma de afrontarlo. Pero después de unas horas desconectados del problema, se nos ocurre lo siguiente:

#include <stdio.h>
#include <stdlib.h>

int main(){
    int i=5;
    while(i<1000001)
        if(i%4==0){         
            printf("%d\n",i);           
        }
        i+=5;
    }
return 0;

}

Esta última solución es bastante mejor, que lo planteado, ya no vamos probando todos los números, sino que generamos una lista de múltiplos de 5 y de esos múltiplos miramos cuales son también múltiplos de 4.

Resumiendo

Midiendo el tiempo, con un cronómetro, he conseguido darme cuenta que entre la solución primera y la tercera hay una mejora (en mi máquina de dos segundos). Esto podría parecer poco, pero si pensamos en que el rango que nos pidan sea entre 1 y un trillón, lo mismo la mejora no se mide en segundos, sino en minutos. Por eso y con este ejemplo, he intentado aclararlo, es muy importante mejorar nuestros algoritmos.

 

6 comentarios en “La importancia de un buen algoritmo”

  1. Roberto

    Basta con hacer:

    int i = 20

    while(i<1000001)
    {
    printf("%d\n",i);
    i += 20;
    }

    Sólo los múltiplos de 20 son múltiplos de 4 y de 5 a la vez…

    Responder
    • MiRoot

      La verdad esta es la solución mejor que he encontrado al problema. Pero la queríamos explicar en otro artículo que hablase de la algoritmia y las matemáticas.

      Un saludo y gracias por la respuesta.

      Responder
  2. Víctor López

    Buena reflexión, pero hay que hacer un pequeño apunte respecto al primer y segundo algoritmo. El tiempo de ejecución debiera ser similar (dependiendo del compilador), ya que la comprobación con el & cortocircuitado produce el mismo efecto que los dos ifs anidados.
    No hay duda de que la legibilidad es mucho mejor en el segundo caso, cosa que hace que sea mejor por siempre, pero la justificación ya es distinta 🙂 .

    Un saludo.

    Responder
    • MiRoot

      La verdad es que tienes razón, nos hemos equivocado al insertar el fragmento de código, que debería ir en ese caso.
      Muchas gracias, ahora lo arreglamos.

      Responder
    • anonimo

      Pero en el segundo algoritmo no se hace la comprobación del 5 si no es múltiplo de 4, mientras que en el primero se hace siempre. La diferencia es pequeña por la potencia de los ordenadores y el rango pequeño, ppero a mayor escala debería notarse.

      Responder
      • SomosBinarios

        Si, al evaluarse en cortocircuito algunas de las comparaciones no se realizan y agiliza el código. Creo que a raíz del comentario de Victor modificamos algo si mal no recuerdo así que me imagino que el estaría en lo cierto en la versión anterior y nosotros en lo cierto en la actual.

        Un saludo.

        Responder

Deja una Respuesta