Un ejemplo: el algoritmo de selección.

Veamos un ejemplo concreto de los pasos a dar para obtener la curva de tiempos experimental para el algoritmo de selección.

1. Creamos un programa que haga uso del algoritmo de selección y escriba la estimación de tiempo en su ejecución. El programa podría ser el siguiente:

   /* Fichero: programa.c */
   
   #include <stdio.h>
   #include <time.h>
   #include <string.h>
   
   #define MAXIMO 1000000
   int M[MAXIMO];
   
   int main (int argc, char *argv[])
   {
     int i,j,n,iteraciones;
     time_t tiempo_inicial,tiempo_final;
     int tiempo;
   
     if (argc!=3) {
       fprintf (stderr,"%s <entrada> <iteraciones>\n",argv[0]);
       return 1;
     }
     n= atoi (argv[1]);
     iteraciones= atoi (argv[2]);
     if (n>MAXIMO) return 1;
     fprintf (stderr,"Para un tama\~no de %d hacemos %d iteraciones\n",n,iteraciones);
   
     time(&tiempo_inicial);
     for (i=0;i<iteraciones;i++) {
       for (j=0;j<n;j++)
         M[j]=n-j;
       Seleccion(M,n);
     }
     time(&tiempo_final);
     tiempo= tiempo_final-tiempo_inicial;
   
     time(&tiempo_inicial);
     
     for (i=0;i<iteraciones;i++) {
       for (j=0;j<n;j++)
         M[j]=n-j;
     }
     time(&tiempo_final);
     tiempo-= (tiempo_final-tiempo_inicial);
     fprintf(stderr,"Se ha descontado %d\n",tiempo_final-tiempo_inicial);
   
     printf ("%d %f\n",n,tiempo/(float)iteraciones);
   
     return 0;
   }
   

   Nótese que no estamos siendo muy estrictos en medir estos tiempos. Primero, los tiempos son aproximados en segundos por lo que es necesario realizar bastantes iteraciones para conseguir cierta precisión en el tiempo. Segundo, tenemos que tener en cuenta que estamos en un sistema multiproceso y el tiempo que tarda nuestro sistema en ejecutar el algoritmo no corresponde por entero a éste. Para suplir en lo posible este problema, los experimentos se deben realizar en las mismas condiciones (los mismos programas ejecutando y sin que el usuario ejecute o use otros procesos en paralelo).

   Una solución más exacta podría ser utilizar otro método como el comando time de unix o la función clock para conocer el tiempo de usuario invertido en ese proceso o aún mejor, un depurador que nos permita realizar experimentos y obtener estadísticas y valores de tiempo para cada función del programa. El ejemplo anterior se puede modificar para hacer uso de la función clock dando lugar al siguiente código:

   /* Fichero: conclock.c */
   
   #include <stdio.h>
   #include <time.h>
   #include <string.h>
   
   #define MAXIMO 1000000
   int M[MAXIMO];
   
   int main (int argc, char *argv[])
   {
     int i,j,n,iteraciones;
     clock_t tiempo_inicial,tiempo_final;
     int tiempo;
   
     if (argc!=3) {
       fprintf (stderr,"%s <entrada> <iteraciones>\n",argv[0]);
       return 1;
     }
     n= atoi (argv[1]);
     iteraciones= atoi (argv[2]);
     if (n>MAXIMO) return 1;
     fprintf (stderr,"Para un tama\~no de %d hacemos %d iteraciones\n",n,iteraciones);
   
     tiempo_inicial=clock();
     for (i=0;i<iteraciones;i++) {
       for (j=0;j<n;j++)
         M[j]=n-j;
       Seleccion(M,n);
     }
     tiempo_final=clock();
     tiempo= tiempo_final-tiempo_inicial;
   
     tiempo_inicial=clock();
     
     for (i=0;i<iteraciones;i++) {
       for (j=0;j<n;j++)
         M[j]=n-j;
     }
     tiempo_final=clock();
     tiempo-= (tiempo_final-tiempo_inicial);
     fprintf(stderr,"Se ha descontado %d\n",tiempo_final-tiempo_inicial);
   
     printf ("%d %.10f\n",n,tiempo/(float)iteraciones);
     printf ("En segundos %.10f\n",tiempo/(float)iteraciones/CLOCKS_PER_SEC);
     printf ("El sistema tiene %d CLOCKS_PER_SEC\n",CLOCKS_PER_SEC);
   
     return 0;
   }
   

   Para los objetivos de esta práctica es suficiente con el programa presentado y por tanto este será el método que se use en todos los casos. Por supuesto, en cada experimento tendremos que indicar un número de iteraciones suficiente como para que el programa necesite varios segundos o incluso hasta del orden de minutos para que la medida sea bastante estable. Obviamente, el alumno puede utilizar cualquier otro método más exacto si lo desea.

2. Compilamos el programa: gcc -c -o programa.o programa.c.
3. Enlazamos los dos ficheros en un ejecutable: gcc -o ejecutable programa.o algoritmos.o.
4. Realizamos distintas ejecuciones para obtener distintas parejas de valores.
5. Se guardan en un fichero ascii todas las parejas ordenadas de menor a mayor. Por ejemplo en el fichero ``seleccion.txt''.