In [ ]:
# Exercise:
# Evaluate with time the execution time of factorial function
from time import sleep
import simcache
def factorial(x):
sleep(0.1) # This sleep can not be removed!!
if x < 2:
return 1
return x * factorial(x - 1)
In [ ]:
import time
t_start = time.time()
print factorial(100)
t_end = time.time()
print "Ellapsed time: {}".format(t_end-t_start)
In [ ]:
# Exercise:
# Evaluate with timeit the execution time of new factorial function
def factorial(x):
sleep(0.1) # This sleep can not be removed!!
if x < 2:
return 1
res = simcache.get_key(x - 1)
if not res:
res = factorial(x - 1)
simcache.set_key(x - 1, res)
return x * res
In [ ]:
# How to evaluate the time with timeit: this module is __main__
print __name__
#import timeit
#print timeit.timeit(stmt='factorial(20)',
# setup='from __main__ import factorial',
# number=10)
In [ ]:
# Exercise: check fibonaccci execution time
def fibonacci(n):
"""Return the nth fibonacci number"""
if n < 2:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
In [ ]:
# Use this cell to measure
In [ ]:
real_fibonacci = fibonacci
def fibonacci(n):
res = simcache.get_key(n)
if not res:
res = real_fibonacci(n)
simcache.set_key(n, res)
return res
In [ ]:
t1_start = time.time()
print fibonacci(30)
t1_elapsed = time.time() - t1_start
print "fibonacci time {}".format(t1_elapsed)
t1_start = time.time()
print real_fibonacci(30)
t1_elapsed = time.time() - t1_start
print "fibonacci_real time {}".format(t1_elapsed)
In [ ]:
simcache.clear_keys() # Let's clean the cache
# Let's define the real fibonacci computation function
def fibonacci(n):
if n < 2:
return n
print "Real fibonacci func, calling recursively to", fibonacci, n
# Once the trick is done globals will contain a different function binded to 'fibonacci'
return fibonacci(n - 1) + fibonacci(n - 2)
In [ ]:
print fibonacci
print fibonacci(5)
In [ ]:
# Call graph of fibonacci for n=5
#
# __ 4 ---- 3 ----------- 2 ---- 1
# 5 __/ \__ 2 ---- 1 \__ 1 \__ 0
# | \__ 0
# \__ 3 ---- 2 ---- 1
# \__ 1 \__ 0
#
In [ ]:
# Let's save a reference to the real function
real_fibonacci = fibonacci
print real_fibonacci # Points to real fibonacci calculation function
In [ ]:
# Let's create a new function which will use memoization
def memoized_fibonacci(n):
# Try to retrieve value from cache
res = simcache.get_key(n)
if not res:
# If failed, call real fibonacci func
print "Memoized fibonacci func, proceeding to call real func",\
real_fibonacci, n
res = real_fibonacci(n)
# Store real result
simcache.set_key(n, res)
return res
print memoized_fibonacci # This is the new function with memoization
In [ ]:
# Let's replace the real function by the memoized version in module globals
fibonacci = memoized_fibonacci
In [ ]:
print fibonacci(5) # Let's see what happens now
In [ ]:
print fibonacci(5) # Let's try again
In [ ]:
print fibonacci(10) # Let's try with a bigger number
Do you remember functions are first class objects? They can be used as arguments or return values...
Do you remember we can declare functions inside other functions?
In [ ]:
def fibonacci(n):
if n < 2:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
def memoize_any_function(func_to_memoize):
"""Function to return a wrapped version of input function using memoization
"""
print "Called memoize_any_function"
def memoized_version_of_func(n):
"""Wrapper using memoization
"""
res = simcache.get_key(n)
if not res:
res = func_to_memoize(n) # Call the real function
simcache.set_key(n, res)
return res
return memoized_version_of_func
In [ ]:
fibonacci = memoize_any_function(fibonacci)
In [ ]:
print fibonacci(35)
In [ ]:
# Much nice if we do:
@memoize_any_function # This is the simplest decorator syntax
def fibonacci(n):
if n < 2:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
In [ ]:
print fibonacci(150)
In [ ]:
def timing_decorator(decorated_func):
print "Called timing_decorator"
def wrapper(*args): # Use variable arguments to be compatible with any function
"""Wrapper for time executions
"""
start = time.time()
res = decorated_func(*args) # Call the real function
elapsed = time.time() - start
print "Execution of '{0}{1}' took {2} seconds".format(decorated_func.__name__, args, elapsed)
return res
return wrapper
In [ ]:
@timing_decorator
@memoize_any_function # We can accumulate decorators
def fibonacci(n):
if n < 2:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
In [ ]:
simcache.clear_keys()
print fibonacci(5)
In [ ]:
print fibonacci
# Why is the wrapper? Can we maintain the original name ?
In [ ]:
import functools
def memoize_any_function(decorated_func):
"""Function to return a wrapped version of input function using memoization
"""
@functools.wraps(decorated_func) # Use functools.wraps to smooth the decoration
def memoized_version_of_f(*args):
"""Wrapper using memoization
"""
res = simcache.get_key(args)
if not res:
res = decorated_func(*args) # Call the real function
simcache.set_key(args, res)
return res
return memoized_version_of_f
In [ ]:
def timing_decorator(decorated_func):
@functools.wraps(decorated_func)
def wrapper(*args): # Use variable arguments to be compatible with any function
"""Wrapper for time executions
"""
start = time.time()
res = decorated_func(*args) # Call the real function
elapsed = time.time() - start
print "Execution of '{0}{1}' took {2} seconds".format(decorated_func.__name__, args, elapsed)
return res
return wrapper
In [ ]:
@timing_decorator
@memoize_any_function # We can accumulate decorators, and they are run in strict top-down order
def fibonacci(n):
if n < 2:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
In [ ]:
print fibonacci(100)
A callable which receives a funtion as only argument and returns another function. Typically the resulting function wrapps the first function executing some code before and/or after the first is called.
New in Python 2.4, they are the pythonic implementation of Decorator Pattern
It is possible to accumulate decorators
functools.wraps copies name, module and docstring of wrapped function to its wrapper
Use variable number of positional and keyword arguments for higher compatibility
Decorators are executed each time the decorated function is called
Typical uses:
In [ ]: