Algorithms For Dummies

  Relying on Dynamic Programming 

     307

Note that the function is the same as before. The only addition is the imported 

lru_cache

 (

https://docs.python.org/3.5/library/functools.html

), which 

you call by putting an @ symbol in front of it. Any call with the @ symbol in front 

is an annotation and calls the 

lru_cache

 function as a decorator of the following 

function.

Using decorators is an advanced technique in Python. Decorators don’t need to be 

explained in detail in this book, but you can still take advantage of them because 

they are so easy to use. (You can find additional information about decorators at 

http://simeonfranklin.com/blog/2012/jul/1/python-decorators-in-

12-steps/

 and 

https://www.learnpython.org/en/Decorators

.) Just remember 

that you call them using annotations (@ + decorator function’s name) and that you 

put them in front of the function you want to transform. The original function is 

fed into the decorator and comes out transformed. In this example of a simple 

recursive function, the decorator outputs a recursion function enriched by 

memoization.

It’s time to test the function speed, as before:

%timeit -n 1 -r 1 print(fib(36))

14930352

1 loop, best of 1: 60.6 

µs per loop

Even  if  your  execution  time  is  different,  it  should  decrease  from  seconds  to 

milliseconds. Such is the power of memoization. You can also explore how your 

function uses its cache by calling the 

cache_info

 method from the decorated 

function:

fib.cache_info()

CacheInfo(hits=34, misses=37, maxsize=None, currsize=37)

The output tells you that there are 37 function calls that don’t find an answer in 

the cache. However, 34 other calls did find a useful answer in the cache.

Just by importing 

lru_cache

 from 

functools

 and using it in annotations in front 

of your heavy-duty algorithms in Python, you will experience a great increase in 

performance (unless they are greedy algorithms).

---

308