Bom pessoal, meu problema é o seguinte, preciso pegar o tempo de execução de um determinado Algoritmo para fazer um gráfico em função do tempo e chamadas que o mesmo faz.
A parte para gerar o gráfico está tranquila, falta apenas eu pegar o tempo de execução de cada algoritmo.
Alguém poderia me dar uma idéia de como eu poderia fazer isso?
Meus algoritmos são os seguintes abaixo.
public class ExercicioCanaQ1
{
public static void main(String[] args)
{
int n = 1000;
System.out.println("Recursivo: " + algRecursivo(n));
System.out.println("Dinâminco: " + algDinamico(n));
}
public static int nCount;
public static ArrayList l1 = new ArrayList();
//Algoritmo Recursivo
public static int algRecursivo(int n)
{
nCount++;
l1.add(nCount);
//l1.size();
if (n < 5){ return 0; }
int x = algRecursivo(n/2);
int y = algRecursivo(n/2 + 1);
int z = algRecursivo(n/2 + 2);
System.out.println(nCount);
return x + y + z + n;
}
public static int[] v;
//Algoritmo Dinâmico
public static int algDinamico(int n)
{
nCount++;
v = new int[n+1];
v[0] = 0;
v[1] = 0;
v[2] = 0;
v[3] = 0;
v[4] = 0;
for (int i = 5; i < v.length; i++)
{
int x = i/2;
int y = i/2 + 1;
int z = i/2 + 2;
v[i] = v[x] + v[y] + v[z] + i;
}
return v[n];
}
}
Para um algoritmo tão rápido quanto o mostrado ,você deve fazer o seguinte:
a) Usar uma função de medição mais precisa, como System.nanoTime
b) Rodar seu algoritmo pelo menos 1000 vezes (para dar tempo de o Just-In-Time compiler do Java compilar seu código - antes disso ele o rodará interpretado, distorcendo os resultados) e só a partir daí medir o tempo
c) COmo o algoritmo é rápido, você não pode medir o tempo isolado de sua execuçao, e sim 100 vezes desse algoritmo (por exemplo), e então você divide o tempo por 100 (a rigor você deveria fazer uma análise estatística dos tempos de execução para desprezar os tempos que ficaram “fora da curva” mas isso é coisa mais avançada).
[quote=jeovane.reges]Pessoal, como que eu faria a formatação do tempo usando ‘System.nanoTime()’?
Porque deixando da seguinte maneira ‘System.out.println(new SimpleDateFormat(“mm:ss”).format(new Date(timeFinal - timeInicio)));’
Me é retornando um tempo da seguinte maneira ‘17:28’ o que está totalmente errado.
Alguém poderia por favor me dizer como que faço essa formatação?
Desde de ja obrigado por todos.[/quote]
O que lhe passaram está obviamente errado
System.nanotime lhe retorna um tempo em nanossegundos (um bilionésimo de segundo).
Faça as contas para transformar isso em um valor razoável para você medir.
[quote]1) O que lhe passaram está obviamente errado
2) System.nanotime lhe retorna um tempo em nanossegundos (um bilionésimo de segundo).
Faça as contas para transformar isso em um valor razoável para você medir. [/quote]
Eu implementei da seguinte forma abaixo, tem algo errado?
public static int algDinamico(int n)
{
//Pega o inicio de execução do tempo
long timeInicio = System.nanoTime();
nCount++;
v = new int[n+1];
v[0] = 0;
v[1] = 0;
v[2] = 0;
v[3] = 0;
v[4] = 0;
for (int i = 5; i < v.length; i++)
{
int x = i/2;
int y = i/2 + 1;
int z = i/2 + 2;
v[i] = v[x] + v[y] + v[z] + i;
}
//Pega o tempo final do algoritmo
long timeFinal = System.nanoTime();
//Imprime o tempo de execução
System.out.println(new SimpleDateFormat("mm:ss").format(new Date(timeFinal - timeInicio)));
return v[n];
}
Ainda não está. new Date(long) recebe um valor em milissegundos, mas para formatar diferenças de tempo, você nunca deve usar SimpleDateFormat. Para provar isso, passe o valor 0 para new Date(). Deve mostrar o valor “03:00” (se seu fuso horário for o de Brasília).
Tentei fazer da seguinte maneira abaixo, no entanto tenho um resultado meio estranho.
Por exemplo para uma entrada igual a 1000 me é retornado o seguinte valor 687728.
Esse tempo tá em segundo ou o que? Caso não, como que faço agora pra ele ele ser retornado em segundos?
public static int algDinamico(int n)
{
//Pega o inicio de execução do tempo
long timeInicio = System.nanoTime();
nCount++;
v = new int[n+1];
v[0] = 0;
v[1] = 0;
v[2] = 0;
v[3] = 0;
v[4] = 0;
for (int i = 5; i < v.length; i++)
{
int x = i/2;
int y = i/2 + 1;
int z = i/2 + 2;
v[i] = v[x] + v[y] + v[z] + i;
}
//Pega o tempo final do algoritmo
long timeFinal = System.nanoTime();
long elapsTime = timeFinal - timeInicio;
System.out.println(TimeUnit.NANOSECONDS.convert(elapsTime, TimeUnit.NANOSECONDS));
return v[n];
}
Um nanossegundo é um bilionésimo de um segundo, logo se você tiver um tempo de 123456 nanossegundos, você terá um tempo de 123456.0 / 100000000.0 segundos. Use double para as contas; isso dá 0,000123456 segundos. Talvez o Java imprima em notação científica, isso irá representar o número 1.23456E-4, ou seja, 1.23456 x 10 elevado a -4.
Na verdade, quando se faz comparação entre algoritmos, você precisa, mais que os tempos absolutos, dos tempos relativos. Por exemplo, digamos que um algoritmo leve 123456 nanossegundos e outro leve 234567 nanossegundos. O segundo algoritmo leva, em relação ao primeiro, 234567 / 123456 * 100% = 190% , ou seja, 90% a mais de tempo que o primeiro algoritmo.
É isso mesmo, mas como eu havia dito antes, é necessário rodar seu algoritmo cerca de 1000 vezes (isole-o em um método, para que ele seja compilado separadamente - o JIT (Just-In-Time compiler) não gosta muito de compilar métodos grandes, mas prefere métodos pequenos) e então é que você deve medir o tempo de várias execuções desse mesmo algoritmo, e tirar a média. Se precisar de resultados mais estatisticamente significativos, despreze os tempos que ficaram muito fora da média (os famosos “pontos fora da curva”) e recalcule a média com os tempos, excluindo os pontos fora da curva.
Para saber se o JIT efetivamente compilou seu método, use o parâmetro -XX:+PrintCompilation para ver se o método efetivamente foi compilado.
Fazendo alguns teste no Netbeans para uma entrada n = 30000, obtive os seguintes resultados.
Como podem ver o tempo foi diferente para os dois, o que é normal, pois o recursivo leva um maior tempo.
Mais também ambos os temos parecem-me serem maior do que o tempo que o Netbeans dá de execução que é de 1 segundo.
Isso estar correto?
Algoritmo Recursivo
Tamanho da Entrada: 30000
Resultado: 22467257
Chamadas: 2576866
Tempo: 3.73582141
Algoritmo Dinâmico
Tamanho da Entrada: 30000
Resultado: 22467257
Chamadas: 29996
Tempo: 0.9821151
CONSTRUÍDO COM SUCESSO (tempo total: 1 segundo)
