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

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

+1 voto
8 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 (5,956 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.

1 Resposta

0 votos
respondida Mar 19 por danielcajueiro (5,956 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 (5,956 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.
...