Algorithms For Dummies

Leveraging memoization

Memoization is the essence of dynamic programming. You often find the need to 

use it when scripting an algorithm yourself. When creating a function, whether 

recursive or not, you can easily transform it using a simple command, a decorator, 

which is a special Python function that transforms functions. To see how to 

---

306

 

   

  PART 5 

 Challenging Difficult Problems

work  with  a  decorator,  start  with  a  recursive  function,  stripped  of  any  print 

statement:

def fib(n):

    if n==0:

        return 0

    elif n == 1:

        return 1

    else:

        return fib(n-1) 

+ fib(n-2)

When using Jupyter, you use IPython built-in magic commands, such as 

timeit

, 

to measure the execution time of a command on your computer:

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

14930352

1 loop, best of 1: 15.5 s per loop

The output shows that the function requires about 15 seconds to execute. How-

ever, depending on your machine, function execution may require more or less 

time. No matter the speed of your computer, it will certainly take a few seconds to 

complete, because the Fibonacci number for 36 is quite huge: 14930352. Testing 

the same function for higher Fibonacci numbers takes even longer.

Now it’s time to see the effect of decorating the function. Using the 

lru_cache

 

function from the 

functools

 package can radically reduce execution time. This 

function is available only when using Python3. It transforms a function by auto-

matically adding a cache to hold its results. You can also set the cache size by 

using the 

maxsize

 parameter (

lru_cache

 uses a cache with an optimal replace-

ment strategy, as explained in the Chapter 15). If you set 

maxsize=None

, the cache 

uses all the available memory, without limits.

from functools import lru_cache

@lru_cache(maxsize=None)

def fib(n):

    if n==0:

        return 0

    elif n == 1:

        return 1

    else:

        return fib(n-1) 

+ fib(n-2)

---

CHAPTER 16