quinta-feira, 24 de outubro de 2013

[Python] - Fibonacci Recursivo - Várias versões

Olá pessoal. No curso Python para Zumbis, eu vi uma aula bem interessante sobre recursão que trazia três implementações de fibonacci recursivo. Uma delas, para quem já viu recursão, é bastante conhecida que é a implementação mais comum.

Outras duas implementações são bem legais, principalmente a que usa a função lru_cache. Otimiza bastante já que a implementação comum (trivial) demora muito para obter o resultado para números muito grandes como 100, 200, 300 etc. Resolvi colocar um código com as três implementações. A execução do código gera o tempo de cada uma das implementações. Para modificar o número é só alterar o valor da variável "numero", eu coloquei 35. Executem numa versão do Python 3.x.

# Varias versoes de Fibonacci Recursivo

# Versao trivial
def fib_trivial(n):
    if n == 1 or n == 2:
        return 1
    return fib_trivial(n-1) + fib_trivial(n-2)

# Versão com cache
cache = {}
def fib_cache(n):
    if n == 1 or n == 2:
        return 1
    else:
        if n not in cache:
            cache[n] = fib_cache(n-1) + fib_cache(n-2)
        return cache[n]

# Versão utilizando função, decorator
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_func(n):
    if n == 1 or n == 2:
        return 1
    return fib_func(n-1) + fib_func(n-2)

# numero que que será passado por parâmetro
numero = 35

print('Tempos para o número %d ...' %numero)

# importação do módulo time para pegar o tempo de cada execução
import time

# obtendo o tempo de Fibonacci Trivial
antes = time.time() # obtém o tempo antes da chamada da função
fib_trivial(numero) # chama a função fib_trivial
depois = time.time() # obtém o tempo depois da chamada da função
diff = depois - antes # obtém a diferença
print('Tempo Fibonacci trivial: %f segundos' %diff) # mostra o resultado

# iremos fazer coisa semelhante com as outras funções

# Obtendo o tempo de Fibonacci com cache
antes = time.time()
fib_cache(numero)
depois = time.time()
diff = depois - antes
print('Tempo Fibonacci com cache: %f segundos' %diff)

# Obtendo o tempo de Fibonacci com lru_cache
antes = time.time()
fib_func(numero)
depois = time.time()
diff = depois - antes
print('Tempo Fibonacci usando lru_cache: %f segundos' %diff)


Nenhum comentário: