Ir ao conteúdo
  • Comunicados

    • Gabriel Torres

      Seja um moderador do Clube do Hardware!   12-02-2016

      Prezados membros do Clube do Hardware, Está aberto o processo de seleção de novos moderadores para diversos setores ou áreas do Clube do Hardware. Os requisitos são:   Pelo menos 500 posts e um ano de cadastro; Boa frequência de participação; Ser respeitoso, cordial e educado com os demais membros; Ter bom nível de português; Ter razoável conhecimento da área em que pretende atuar; Saber trabalhar em equipe (com os moderadores, coordenadores e administradores).   Os interessados deverão enviar uma mensagem privada para o usuário @Equipe Clube do Hardware com o título "Candidato a moderador". A mensagem deverá conter respostas às perguntas abaixo:   Qual o seu nome completo? Qual sua data de nascimento? Qual sua formação/profissão? Já atuou como moderador em algo outro fórum, se sim, qual? De forma sucinta, explique o porquê de querer ser moderador do fórum e conte-nos um pouco sobre você.   OBS: Não se trata de função remunerada. Todos que fazem parte do staff são voluntários.
    • DiF

      Poste seus códigos corretamente!   21-05-2016

      Prezados membros do Fórum do Clube do Hardware, O Fórum oferece um recurso chamado CODE, onde o ícone no painel do editor é  <>     O uso deste recurso é  imprescindível para uma melhor leitura, manter a organização, diferenciar de texto comum e principalmente evitar que os compiladores e IDEs acusem erro ao colar um código copiado daqui. Portanto convido-lhes para ler as instruções de como usar este recurso CODE neste tópico:  
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.

Editado por vangodp
  • 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






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

×