Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Exemplo da aula 2: possível melhoria na eficiência?

+1 voto
28 visitas
perguntada Mar 18 em Programação Computacional por Lucas Lourenço (6 pontos)  
editado Mar 19 por Lucas Lourenço

No exemplo da aula 2, que verifica se um dado número é primo, me parece que podemos melhorar a eficiência do código ao introduzir um break dentro do loop assim que a função já sabe que o número em questão não é primo. Assim, poupamos algumas iterações.

Utilizando o módulo timeit e propositadamente fazendo um teste com um número muito grande (16 dígitos), obtive na minha máquina a seguinte diferença de tempo de computação com e sem o break: 14.74 segundos vs 0.0002 segundos.

Resta saber o que acontece com o tempo de cálculo naqueles casos em que o número é primo. Como nesses casos o break não é utilizado, esperamos que o tempo seja similar ou um pouco pior, dado que acrescentamos uma linha de código. Utilizei o número primo 67.231 e defini 1000 iterações. Não houve diferença significativa no tempo (0.15 segundos em ambos os casos).

Acham a ideia de acrescentar o break em loops válida?

Abraço

Segue o código completo, com e sem o break:

import timeit
mycode = '''
def prime(x):
count=2
sqrx=x**(1/2)
prime=True
while(count<=sqrx):
    if x%count==0:
        prime=False
        break
    count=count+1
if(prime):
    print(x,"is a prime number")
else:
    print(x,"is not a prime number")
prime(67280421310721)
'''
print (timeit.timeit(stmt = mycode, number = 1))



mycode = '''
def prime(x):
count=2
sqrx=x**(1/2)
prime=True
while(count<=sqrx):
    if x%count==0:
        prime=False         
    count=count+1
if(prime):
    print(x,"is a prime number")
else:
    print(x,"is not a prime number")
prime(67280421310721)
'''
print (timeit.timeit(stmt = mycode, number = 1))
Compartilhe
comentou Mar 19 por danielcajueiro (6,046 pontos)  
Acho que é bom colocar o código original na pergunta para a comparação. As pessoas não sabem o que vc está perguntando.
comentou Abr 2 por Stuart Mill (1,434 pontos)  
Sugiro também dar uma olhada nesta solução:
http://prorum.com/?qa=4578/programa-buscar-numeros-intervalo-programacao-funcional&show=4578#q4578

Nesse caso o return elimina a necessidade de ter o break no código. Além do mais, é possível reduzir as operações de divisão pela metade pulando os números pares.

Lembrando que há formas de deixar o algoritmo melhor usando mais matemática. Veja por exemplo o Crivo de Erastótenes: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

1 Resposta

0 votos
respondida Mar 19 por danielcajueiro (6,046 pontos)  

Nao tenho certeza se você esta comparando o tempo corretamente. Você removeu o "prime" da condição do while. Então nesse caso você estará fazendo o loop todo (sem o break) o que é bastante ineficiente. Se você colocar na condição o break (veja o codigo original) a diferença deve ser muito pequena - nao pode ser 14 segundos (so se tiver um erro). "14s" deve ser o tempo inteiro do loop, ou seja, um desastre.

Vamos voltar ao ponto do "Break". Evitamos usar o "break" em programação estruturada, pois ele age como se fosse um "goto". O codigo fica desestruturado. Por que? Note que olhando para o codigo, saimos do while sem controle do while. A ideia é que você explicite essa condição no while e foi isso que ocorria no código original.

comentou Mar 19 por Lucas Lourenço (6 pontos)  
Obrigado pela resposta professor. Entendi a ideia do prime dentro do while, que é justamente a de interromper o loop para não fazer iterações desnecessárias. De fato o "break" é uma saída bem menos elegante.
comentou Mar 19 por danielcajueiro (6,046 pontos)  
A pergunta é interessante pois o break é mais direto, mas desestrutura o programa. Talvez você possa colocar os codigos na pergunta para ficar mais claro.
comentou Mar 19 por Lucas Lourenço (6 pontos)  
Atualizei o código na pergunta original.
...