Na aula passada (Parte I), desenvolvemos um algoritmo para encontrar números primos a partir do número 2. Fornecemos um número máximo a ser testado e encontramos todos os números primos que são menores que o número fornecido. Abaixo está o código do nosso algoritmo:
calcula_primos = function(num_max){
v_num = seq(3,num_max,by=2);
v_primos = NULL;
v_primos[1] = 3;
count = 1;
while(count<=length(v_num)){
testa_primo = T;
for(i in 1:length(v_primos)){
if(v_num[count]%%v_primos[i]==0){
testa_primo = F;
break;
}
}
if(testa_primo==T) v_primos = c(v_primos,v_num[count]);
count = count + 1;
}
v_primos = c(2,v_primos)
return(v_primos)
}
Vamos relembrar: criamos um vetor de números ímpares (v_num) até o valor máximo fornecido e verificamos se cada um deles é primo. Isto é, para cada número testado, verificamos a divisão por cada número primo no vetor de números primos v_primos. Caso haja alguma divisão exata, o número testado não é primo, caso contrário, é primo e o acrescentamos no vetor v_primos.
Porém, nosso algoritmo tem um ponto ineficiente: o teste de divisão é realizado por todos os números do vetor v_primos para todo número testado. Mas isso não é necessário. De fato, podemos parar a verificação no número primo mais próximo da raiz quadrada do número testado. Vamos entender.
Suponha que queremos testar se o número 36 é primo. Começamos pela divisão por 2, por 3 e assim por diante. Porém, não precisamos testar a divisão por 7, por 11 e nenhum número maior que a raiz quadrada de 36, que é 6. Por que isso acontece? Vamos chamar nosso número de n. Se n é um número composto e realizamos sua decomposição, haverá pelo menos um fator menor ou igual que a raiz quadrada de n. No caso do 36, podemos escrevê-lo como 6*6 = 2*3*2*3. Outro exemplo: 64 = 8*8 = 2^6. E se o número não for escrito da forma m^2, em que m é um número inteiro que representa a raiz quadrada de n? Podemos pegar o menor inteiro mais próximo de m. Por exemplo, o número 35 tem como raiz quadrada um valor aproximado de 5,91. Decompondo 35 em fatores primos, temos 35 = 5*7. Se verificamos a divisão por 5, concluímos que 35 não é número primo.
Em outras palavras, se não há divisão exata de um número por fatores primos menores que sua raiz quadrada, então esse número é primo.
Dessa forma, evitamos (e muito) a computação do nosso algoritmo quando um número é primo. Por exemplo, o número 997 é primo e, para concluir esse fato pelo nosso algoritmo, testamos a divisão de 997 por 167 números primos abaixo dele. Porém, a raiz quadrada de 997 é aproximadamente 31,57, o que nos indica que a verificação é necessária até o número 31, que corresponde a 11 números primos. Percebe a diferença? Estamos excluindo muitas verificações desnecessárias, tornando o algoritmo mais eficiente.
Então, vamos implementar essa melhoria. E será fácil: basta implementar uma condição em que o algoritmo para quando a verificação considerar um número primo maior que a raiz quadrada do número testado. Vejamos:
for(i in 1:length(v_primos)){
if(v_primos[i]>sqrt(v_num[count])) break;
if(v_num[count]%%v_primos[i]==0){
testa_primo = F;
break;
}
Em termos de tempo, será que nossa otimização fez diferença? Vamos testar. Primeiro, vamos usar um número pequeno: 100, lembrando que o algoritmo vai encontrar todos os números primos de 2 a 100. Para análise de tempo, utilizaremos a função benchmark() do pacote rbenchmark.
library(rbenchmark)
numero = 100;
benchmark(calcula_primos(numero),calcula_primos2(numero),replications = 1000,
columns = c("test", "replications", "elapsed","relative"))
> benchmark(calcula_primos(numero),calcula_primos2(numero),replications = 1000,
+ columns = c("test", "replications", "elapsed","relative"))
test replications elapsed relative
1 calcula_primos(numero) 1000 0.20 1.176
2 calcula_primos2(numero) 1000 0.17 1.000
A função benchmark() fez 1000 replicações das funções desejadas e calculou o tempo médio de execução. Podemos ver que nossa otimização melhorou o algoritmo, sendo o tempo relativo da primeira função 1,176 vezes o tempo da segunda função. O tempo apresentado está em segundos.
Mas para números pequenos, ambas funções são rápidas. O que acontece se aumentamos o número de teste? Vamos realizar o teste com os números 1000 e 9000.
numero = 1000;
> benchmark(calcula_primos(numero),calcula_primos2(numero),replications = 1000,
+ columns = c("test", "replications", "elapsed","relative"))
test replications elapsed relative
1 calcula_primos(numero) 1000 4.81 2.628
2 calcula_primos2(numero) 1000 1.83 1.000
numero = 9000;
> benchmark(calcula_primos(numero),calcula_primos2(numero),replications = 1000,
+ columns = c("test", "replications", "elapsed","relative"))
test replications elapsed relative
1 calcula_primos(numero) 1000 184.79 8.294
2 calcula_primos2(numero) 1000 22.28 1.000
Perceba que, quanto maior for o número, mais tempo nosso algoritmo precisa para executar. Isso ocorre porque o vetor de números primos aumenta e, assim, a verificação da divisão por cada um demorará mais. Note que quando executamos o algoritmo com o número 9000, tivemos uma redução de cerca de 8 vezes de tempo com a função otimizada, passando de 184,79 segundos para 22,28 segundos.
Esse resultado nos mostra a importância da boa programação e de não realizar etapas desnecessárias. Tornar os algoritmos mais eficientes significa obter resultados em menor custo, seja ele de tempo e/ou de memória. Então, apesar de duas funções retornarem o mesmo resultados, é importante escolher a mais eficiente. Sempre tenham isso em mente.
Na próxima aula, vamos implementar um algoritmo interativo, que pergunta ao usuário se, quando chega no final do número fornecido, ele deseja continuar encontrando números primos até um próximo número máximo fornecido. Assim, poderemos encontrar números primos além do primeiro valor máximo fornecido sem ter que recalcular os números primos já encontrados.
Então, até a próxima aula!
Nenhum comentário:
Postar um comentário