Dynamic Programming

Bien, hoy lei un poco de Dynamic Programming, es bacancito, de una pense en un decorator en Python, no es complicado, ahi esta el ejemplo:

1) Fibonacci normal:

#!/usr/bin/python
import sys

def fib(x):
    if x==0:
        return 0
    if x==1:
        return 1
    return fib(x-1)+fib(x-2)

print fib(int(sys.argv[1]))

Este codigo tiene un comportamiento como lo muestra la grafica (N vs segundos)



2) Ahora con un decorator implementando Dynamic Programming.

#!/usr/bin/python
import sys

map={}
def dynamic_programming(func):
  def decorator(*args, **kwargs):
      if (func,args) in map:
          return map[(func,args)]
      else:
          r = func(*args, **kwargs)
          map[(func,args)] = r
          return r
  return decorator


@dynamic_programming
def fib(x):
  if x==0:
      return 0
  if x==1:
      return 1
  return fib(x-1)+fib(x-2)


print fib(int(sys.argv[1]))

Como pueden ver el codigo de la funcion fib no se cambio, solo se le agrego un decorator, el cual busca primero si el argumento esta en un diccionario, para no recalcularlo. (kwargs es un dict, y no puedo usarlo como un key en otro dict, toco sacarlo del key :))

No pondre grafica de este solo esto:


$ time ./fib2.py 499
86168291600238450732788312165664788095941068326060883324529903470149056115823592713458328176574447204501

real 0m0.029s
user 0m0.024s
sys 0m0.004s