Obter tempo de execução em milisegundos

[AdSoNaTuRaL]

Galera! 

 

To com um problema, tenho o seguinte código do problema da mochila binária em programação dinâmica e tenho que contar o tempo de execução desse algoritmo.

 

O código é esse:

// Uma solução baseada em programação dinâmica para o problema da mochila binária
#include<stdio.h>
#include<time.h>

// Uma função util que retorna o maximo de dois inteiros
int max(int a, int b) { return (a > b)? a : b; }

// Retorna o valor máximo que pode ser colocado em uma mochila de capacidade W
int Mochila(int cap_mochila, int peso[], int val[], int n)
{

   int i, w;
   int K[n+1][cap_mochila+1];

   
   // Constoi a tabela K[][] de forma bottom up
   for (i = 0; i <= n; i++)
   {
       for (w = 0; w <= cap_mochila; w++)
       {
           if (i==0 || w==0)
               K[i][w] = 0;
           else if (peso[i-1] <= w)
                 K[i][w] = max(val[i-1] + K[i-1][w-peso[i-1]],  K[i-1][w]);
           else
                 K[i][w] = K[i-1][w];
       }
   }

   return K[n][cap_mochila];
}

int main()
{

    int val[] = {60, 100, 120, 60, 100, 120, 60, 100, 120, 60, 100, 120,
	60, 100, 120, 60, 100, 120, 60, 100, 120, 60, 100, 120, 60, 100, 120,
	60, 100, 120};
    int peso[] = {10, 20, 30, 10, 20, 30, 10, 20, 30, 10, 20, 30, 10, 20, 30,
	10, 20, 30, 10, 20, 30, 10, 20, 30, 10, 20, 30, 10, 20, 30};
    int  cap_mochila = 500;
    int n = sizeof(val)/sizeof(val[0]);
    printf("Maximo inserido na mochila: %d\n", Mochila(cap_mochila, peso, val, n));
    return 0;

}

Alguém poderia me dar uma mão. Eu sei que tenho que usar a biblioteca <time.h>, mas não sei quais os lugares corretos para colocar os parâmetros de iniciar e finalizar a contagem de tempo e de como exibir o resultado com um printf, no main.

[vangodp]

http://stackoverflow.com/questions/10192903/time-in-milliseconds

 

#include<stdio.h>
#include <sys/time.h>

// Uma função util que retorna o maximo de dois inteiros
int max ( int a, int b ) { return ( a > b ) ? a : b; }

// Retorna o valor máximo que pode ser colocado em uma mochila de capacidade W
int Mochila ( int cap_mochila, int peso[], int val[], int n ) {

    int i, w;
    int K[n + 1][cap_mochila + 1];
    
    
    // Constoi a tabela K[][] de forma bottom up
    for ( i = 0; i <= n; i++ ) {
        for ( w = 0; w <= cap_mochila; w++ ) {
            if ( i == 0 || w == 0 )
                K[i][w] = 0;
            else if ( peso[i - 1] <= w )
                K[i][w] = max ( val[i - 1] + K[i - 1][w - peso[i - 1]],  K[i - 1][w] );
            else
                K[i][w] = K[i - 1][w];
        }
    }
    
    return K[n][cap_mochila];
}

int main() {

    int val[] = {60, 100, 120, 60, 100, 120, 60, 100, 120, 60, 100, 120,
                 60, 100, 120, 60, 100, 120, 60, 100, 120, 60, 100, 120, 60, 100, 120,
                 60, 100, 120
                };
    int peso[] = {10, 20, 30, 10, 20, 30, 10, 20, 30, 10, 20, 30, 10, 20, 30,
                  10, 20, 30, 10, 20, 30, 10, 20, 30, 10, 20, 30, 10, 20, 30
                 };
    int  cap_mochila = 500;
    int n = sizeof ( val ) / sizeof ( val[0] );
    

    struct timeval stop, start;
    gettimeofday ( &start, NULL );
    
    //do stuff
    printf ( "Maximo inserido na mochila: %d\n", Mochila ( cap_mochila, peso, val, n ) );

    gettimeofday ( &stop, NULL );
    printf ( "took %lu\n", stop.tv_usec - start.tv_usec );
    
    return 0;
    
}

Ambas variáveis stop e start do tipo struct timeval guardarão 2 valores que provavelmente são o tempo em milissegundos... e desde um ponto fixo no tempo como Unix Era, para uma vez obtido o tempo inicial(start) e o tempo final(stop), chegar através de simples operação de subtração, ao resultado que nada mais é que diferença de tempo entre ambos pontos no tempo.
Imagine que Era Unix foi exatamente 5 minutos atrás, vamos entender como funciona. O start toma esse tempo, o que passou desde 5 minutos atrás, start=5, fazemos o que queremos fazer e medimos novamente o tempo, jogando ele no stop desta vez, porém já haveria passado algo mais de tempo, vamos imaginar 7 minutos esta vez. Restando 7 de 5 sobra 2, esse é o tempo que passou ao executar o programa, porém aqui falamos de minutos, no exemplo que lhe passei está em milissegundos, e Era Unix não foi a 5 minutos atrás se não 1 de janeiro de 1970 a meia noite, é desde esse ponto que se faz ambas medições, e a da maioria dos sistemas atuais de medição de tempo, ignoro se existe outro sistema.

[1freakday]

@AdSoNaTuRaL Boa noite, então, acredito que o tempo de execução é sempre a ultima informação a ser 'mostrada' ao usuário, portanto, o printf ficaria antes de return 0; da função main. E no inicio da função main, você iniciaria a contagem da biblioteca time.h.

 

Segue minha versão:

#include <stdio.h>//io
#include <stdlib.h>//system
#include <sys/time.h>//time

//(fim*x+ms) - (inicio*x+ms) = tempo
#define GET_MS(ini, fim)  ((fim.tv_sec * 1000000 + fim.tv_usec) \
			- (ini.tv_sec * 1000000 + ini.tv_usec))

struct timeval inicio, fim;

int main(){
  //Aqui inicia a contagem
  gettimeofday(&inicio, NULL);
  
  
  //Codigo qualquer....
  system("pause");

  
  //Obtem tempo final
  gettimeofday(&fim, NULL);
  
  
  //Fim de execução
  printf("Tempo de execução: %ld ms\n\n", GET_MS(inicio, fim));
  return 0;
}

Perceba que é multiplicado por 1000000, para alcançar os segundos. 

Se você compilar e comparar o tempo de execução com o do compilador, o compilador terá um tempo maior, pois ele conta desde a inicialização, até o encerramento do programa, aqui só conta depois que é executado o gettimeofday inicial, e termina com o gettimeofday final.