Dificultad:

Lecciones anteriores:

ninguna

Resumen:

Vamos a ver que cómo hacer para que un programa mida automáticamante cuánto tiempo tarda en ejecutarse. Además vamos a hacer que vaya mostrando en la pantalla el tiempo transcurrido. De paso, vamos a discutir algunas formas de mostrar información en la pantalla sin que el programa sea mucho más lento.

Introducción:

Este tema no tiene que ver mucho con la matemática a primera vista, pero muchas veces la diferencia entre un buen algoritmo y uno malo es el tiempo que tardan en resolver el problema. En la mayoría de los casos el tiempo se puede estimar, incluso calcular como depende de los parámetros principales.

Por ejemplo los métodos más simples para ordenar una lista de números tardan un tiempo proporcional a n², o sea que si en vez de ordenar 1000 números ordenamos 10000, el programa tardará unas 100 veces más. Sin embargo se pueden escribir programas que tarden un tiempo proporcional a n*log(n), así que en el ejemplo anterior tardaría solo unas 13 veces más.

El calculo teórico es en general difícil, así que una posibilidad para tener una idea aproximada es probar el programa y ver cuanto tarda con diferentes ejemplos. Esto también es útil para aproximar cuanto tiempo le falta a un programa para terminar. Por ejemplo si tenía que buscar los números menores que 10000, que cumplen alguna condición y para los primeros 100 números tarda 10 minutos, probablemente el programa tarde demasiado (por ejemplo más de las 3 horas de la prueba).

La presición de estas mediciones es poca, el reloj disponible en D.O.S. cambia cada 1/18 de segundo. Así que no es posible utilizarlo para medir tiempos cortos.

Midiendo los tiempos:

Como ejemplo vamos a ver el método para medir el tiempo que tarda un programa que que suma dos números. Esta operación tarda muy poco así que la vamos a repetir 10000000 veces. Dependiendo de la velocidad de la computadora hay que agrandar o achicar este número hasta obtener un tiempo de ejecución razonable (por ejemplo entre 5 o 10 segundos).

En los programas guardo la hora de inicio en la variable Inicio, y la hora de finalización en la variable Final. En Pascal y C++ se obtiene el tiempo separado en horas, minutos y segundos, así que hay que juntarlos en un sólo número que represente la cantidad de segundos, multiplicando por 60 varias veces.

Basic :

Defint A-Z
Cls ' Borro pantalla
Dim Inicio As Single
Dim Final As Single
Const Repeticiones = 10000000
Inicio = Timer
Dim I As Long
For I = 1 To Repeticiones
    X = 7 + 3
    ' Print I, Timer-Inicio
Next I
Final = Timer
Print Final-Inicio

Pascal :

uses
    Crt{para ClrScr},
    Dos{para GetTime};
var
inicio, final, ahora: real;
i,X:longint;

h, m, s, c : Word;
const
    repeticiones = 10000000;
begin
    ClrScr;
    
    GetTime(h,m,s,c);
    inicio := c/100+s+m*60+h*60*60;
    
    FOR i := 1 TO repeticiones do
        begin
        X:=7+3;
        
        { GetTime(h,m,s,c);
        ahora := c/100+s+m*60+h*60*60;
        
        writeln(i,' ',ahora-inicio;}
    end ;
    
    GetTime(h,m,s,c);
    final := c/100+s+m*60+h*60*60;
    
    writeln( final-inicio);
end.

C++ :

#include <dos.h> //para gettime
#include <conio.h> // para clrscr
#include <iostream.h> // para cout
Int main(void)
{
  float inicio, final, ahora;
  long i,X;
  struct time t;
  #define repeticiones 10000000
  clrscr();
  
  gettime(&t);
  inicio = t.ti_hund/100.+t.ti_sec+t.ti_min*60+t.ti_hour*60*60;
  
  for ( i = 1 ; i<=repeticiones ; i++ )
  {
    X=7+3;
    
    //gettime(&t);
    //ahora = t.ti_hund/100.+t.ti_sec+t.ti_min*60+t.ti_hour*60*60;
    
    //cout <<i<<" "<<ahora-inicio<<"\n";
  }
  
  gettime(&t);
  final = t.ti_hund/100.+t.ti_sec+t.ti_min*60+t.ti_hour*60*60;
  
  cout <<final-inicio;
}

Otra posibilidad es agregar unas líneas para ver el avance del programa. Estas líneas aparecen como comentarios en los ejemplos, pruébenlas.

Como habrán visto ahora es muchísimo más lento. En general todo lo que tiene que ver con pantalla es medio lento. Sobre todo si la pantalla debe moverse para arriba para que aparezcan las nuevas líneas.

Una forma de mejorar eso es no imprimir la información en todas las pasadas, sino por ejemplo cada 100000 pasadas. Para ello debemos reemplazar en cada caso estas las líneas que muestran la información en la pantalla por

Basic:

If I Mod 100000=0 Then
    Print I, Timer-Inicio
End If

Pascal:

if i Mod 100000=0 Then
    begin
        GetTime(h,m,s,c);
        ahora := c/100+s+m*60+h*60*60;
        writeln(i,' ',ahora-inicio;}
    end ;

C++:

if ( i%100000 == 0 )
{
  gettime(&t);
  ahora = t.ti_hund/100.+t.ti_sec+t.ti_min*60+t.ti_hour*60*60;
  cout <<i<<" "<<ahora-inicio<<"\n";
}

En estos ejemplos usamos división entera que es más rápida que la normal.

Ejercicios:

1. En otras lecciones anteriores quedaron varios ejercicios propuestos, en los que se pedía comparar los tiempos de ejecución, ¿los hicieron a todos?
   
   
2. Comparar el tiempo que tardan en realizarse operaciones con números enteros y con números reales. Comparar también las distintas operaciones entre sí (Por ejemplo, cambiar la suma por una multiplicación.).
   
   
3. Escribir un programa que genere un vector con N números al azar y luego los ordene. Probarlo para distintos N y ver que el tiempo que tarda es proporcional a N². ¿Se te ocurre por qué?
   
   
4. El manejo de cadenas de texto también es lento. Hacer un programa que busque la última cifra de un número usando cadenas de texto y usando división y compararlos.

Lecciones siguientes:

Cuadrado lleno de múltiplos de 17
Un problema difícil, con una solución que tarda mucho. Medimos el tiempo que tarda para poder comparar distintas mejoras al programa.

Probador de Funciones DCM
Un programita para medir el tiempo que tardan distintos métodos para calcular el divisor común menor entre dos números.

Cuánto va a tardar en CyM-Wiki
Algunos métodos para poder estimar de tiempo que va a tardar un programa sin ejecutarlo.