Decorators
A decorator is a functor that transforms each function call into something else.
def fibnaive(n):
if n <= 1:
return 1
else:
return fibnaive(n-1) + fibnaive(n-2)
What do you think about that example?
First example: write the calls
Our goal is to write a line at each call of the function into the terminal.
Bad solution: Hack the function itself
def fibnaive(n):
print("fibnaive(", n, ")")
if n <= 1:
return 1
else:
return fibnaive(n-1) + fibnaive(n-2)
fibnaive(3)
fibnaive( 3 )
fibnaive( 2 )
fibnaive( 1 )
fibnaive( 0 )
fibnaive( 1 )
3
It works but it is not reusable.
Write a functor
def printed(f):
def printerVersion(*args):
print(f.__name__, "(", *args, ")")
return f(*args)
return printerVersion
def fibnaive(n):
if n <= 1:
return 1
else:
return fibnaive(n-1) + fibnaive(n-2)
fibnaive = printed(fibnaive)
fibnaive(3)
fibnaive ( 3 )
fibnaive ( 2 )
fibnaive ( 1 )
fibnaive ( 0 )
fibnaive ( 1 )
3
Writing the decorator
@printed
def fibnaive(n):
if n <= 1:
return 1
else:
return fibnaive(n-1) + fibnaive(n-2)
fibnaive(3)
fibnaive ( 3 )
fibnaive ( 2 )
fibnaive ( 1 )
fibnaive ( 0 )
fibnaive ( 1 )
3
Writing a class instead of a functor
class Printed:
def __init__(self, f):
self.f = f
def __call__(self, *args):
print(self.f.__name__, "(", *args, ")")
return self.f(*args)
@Printed
def fibnaive(n):
if n <= 1:
return 1
else:
return fibnaive(n-1) + fibnaive(n-2)
fibnaive(3)
fibnaive ( 3 )
fibnaive ( 2 )
fibnaive ( 1 )
fibnaive ( 0 )
fibnaive ( 1 )
3
Second example: printing the running time
We want measure how fibnaiveis slow.
Bad solution
import time
def fibnaive(n):
if n <= 1:
return 1
else:
return fibnaive(n-1) + fibnaive(n-2)
begin = time.time()
fibnaive(30)
end = time.time()
print("Total time: ", end - begin)
Total time: 0.3410148620605469
The above code is ugly and not reusable.
Writing a functor
The code below is nice because it can be reused for any function.
def timedfunction(f):
def timedf(*args, **kwargs):
begin = time.time()
result = f(*args, **kwargs)
end = time.time()
print("Total time: ", end - begin)
return result
return timedf
fibnaive = timedfunction(fibnaive)
fibnaive(3)
Total time: 1.1920928955078125e-06
Total time: 0.000152587890625
Total time: 4.76837158203125e-07
Total time: 1.430511474609375e-05
Total time: 0.0001938343048095703
Total time: 0.00020623207092285156
Total time: 2.384185791015625e-07
Total time: 1.4781951904296875e-05
Total time: 0.0002486705780029297
Total time: 0.000263214111328125
3
Attempt to write the decorator with the functor
Instead of writing timedfunction(fibnaive) which is combersome, we try to decorate the function before its definition.
@timedfunction
def fibnaive(n):
if n <= 1:
return 1
else:
return fibnaive(n-1) + fibnaive(n-2)
fibnaive(3)
Total time: 2.384185791015625e-07
Total time: 4.76837158203125e-07
Total time: 4.673004150390625e-05
Total time: 2.384185791015625e-07
Total time: 6.651878356933594e-05
3
def timedfunction(f):
def timedf(*args, **kwargs):
begin = time.time()
result = f(*args, **kwargs)
end = time.time()
print("Total time: ", end - begin)
return result
return timedf
@timedfunction
def fibnaive(n):
if n <= 1:
return 1
else:
return fibnaive(n-1) + fibnaive(n-2)
fibnaive(3)
Total time: 7.152557373046875e-07
Total time: 1.1920928955078125e-06
Total time: 0.00017786026000976562
Total time: 4.76837158203125e-07
Total time: 0.00021576881408691406
3
Write the decorator with a class
class Timed:
def __init__(self, f):
self.f = f
self.__name__ = f.__name__
self.inside = False
def __call__(self, *args):
if not self.inside:
self.inside = True
begin = time.time()
result = self.f(*args)
end = time.time()
print("Total time: ", end - begin)
self.inside = False
return result
else:
return self.f(*args)
@Timed
def fibnaive(n):
if n <= 1:
return 1
else:
return fibnaive(n-1) + fibnaive(n-2)
fibnaive(32)
Total time: 2.3227994441986084
3524578
Memoization
The code for computing Fibonnaci numbers with a recursive function is so beautiful...
fibnaive(35)
Total time: 9.01091194152832
14930352
... but is so slow.
Direct code for memoized Fibonacci
It consists in storing the values already computed in a hashmap.
def fibmemo(n):
valuesAlreadyComputed = {}
def fibrec(n):
if n in valuesAlreadyComputed:
return valuesAlreadyComputed[n]
if n <= 1:
return 1
else:
valuesAlreadyComputed[n] = fibrec(n-1) + fibrec(n-2)
return valuesAlreadyComputed[n]
return fibrec(n)
fibmemo(35)
14930352
The previous code is ugly. And it handles two responsabilities: to compute the Fibonacci number, and to perform memoïsation. It should be seperated...
First attempt to write a decorator with a high-order function
def memo(f):
valuesAlreadyComputed = {}
def fmemo(*args):
if args not in valuesAlreadyComputed:
valuesAlreadyComputed[args] = f(*args)
return valuesAlreadyComputed[args]
return fmemo
def fibnaive(n):
if n <= 1:
return 1
else:
return fibnaive(n-1) + fibnaive(n-2)
fibnaive = memo(fibnaive)
fibnaive(35)
14930352
@memo
def fibnaive(n):
if n <= 1:
return 1
else:
return fibnaive(n-1) + fibnaive(n-2)
fibnaive(35)
14930352
class Memoize:
def __init__(self, f):
self.f = f
self.__name__ = f.__name__
self.valuesAlreadyComputed = {}
def __call__(self, *args):
if args not in self.valuesAlreadyComputed:
self.valuesAlreadyComputed[args] = self.f(*args)
return self.valuesAlreadyComputed[args]
@Memoize
def fib(n):
if n <= 1:
return 1
else:
return fib(n-1) + fib(n-2)
fib(35)
14930352
Combining decorators
@Printed
@Timed
@Memoize
def fib(n):
if n <= 1:
return 1
else:
return fib(n-1) + fib(n-2)
fib(35)
fib ( 35 )
fib ( 34 )
fib ( 33 )
fib ( 32 )
fib ( 31 )
fib ( 30 )
fib ( 29 )
fib ( 28 )
fib ( 27 )
fib ( 26 )
fib ( 25 )
fib ( 24 )
fib ( 23 )
fib ( 22 )
fib ( 21 )
fib ( 20 )
fib ( 19 )
fib ( 18 )
fib ( 17 )
fib ( 16 )
fib ( 15 )
fib ( 14 )
fib ( 13 )
fib ( 12 )
fib ( 11 )
fib ( 10 )
fib ( 9 )
fib ( 8 )
fib ( 7 )
fib ( 6 )
fib ( 5 )
fib ( 4 )
fib ( 3 )
fib ( 2 )
fib ( 1 )
fib ( 0 )
fib ( 1 )
fib ( 2 )
fib ( 3 )
fib ( 4 )
fib ( 5 )
fib ( 6 )
fib ( 7 )
fib ( 8 )
fib ( 9 )
fib ( 10 )
fib ( 11 )
fib ( 12 )
fib ( 13 )
fib ( 14 )
fib ( 15 )
fib ( 16 )
fib ( 17 )
fib ( 18 )
fib ( 19 )
fib ( 20 )
fib ( 21 )
fib ( 22 )
fib ( 23 )
fib ( 24 )
fib ( 25 )
fib ( 26 )
fib ( 27 )
fib ( 28 )
fib ( 29 )
fib ( 30 )
fib ( 31 )
fib ( 32 )
fib ( 33 )
Total time: 0.002529621124267578
14930352
Exercices
- Apply Dynamic Programming to solve Knapsack problem. Then apply memoization.
- Write factorial in imperative form, recursive form and recursive with tail recursion and compare the running time.