Ir ao conteúdo
  • Cadastre-se
AdSoNaTuRaL

Obter tempo de execução em milisegundos

Recommended Posts

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.

  • Curtir 1

Compartilhar este post


Link para o post
Compartilhar em outros sites

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.

  • Curtir 1

Compartilhar este post


Link para o post
Compartilhar em outros sites

@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.

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×