memoize_fibonacci, Python 3

Language: Layout:

# coding=utf8

"""
 Code illustrating a lecture on memoization
 given by Clément Aubert.
 Cf. https://lacl.fr/~caubert/RH/
 01/23/2016
 Code inspired from
 http://www.python-course.eu/python3_memoization.php
 http://stackoverflow.com/a/14731729
"""

# We'll measure the time using the timeit library
# https://docs.python.org/2/library/timeit.html
# and a custom "measure_fib" function.

import timeit

def measure_fib(fun_test):
    start = timeit.default_timer()
    value = 35 # The Fibonacci number we want to compute.
    fun_test(value)
    end = timeit.default_timer()
    time_elapsed = end - start
    print("{:>13} took {:>8f} s to compute the {}th value of the Fibonacci sequence."
          .format(fun_test.__name__, time_elapsed, value))

# Fibonacci Sequence, no optimization

def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

measure_fib(fib)

# Fibonacci Sequence, using a dictionary

dict = {}

def fib_dict(n):
    if n == 0 or n == 1:
        return n
    elif n not in dict:
        dict[n] = fib_dict(n - 2) + fib_dict(n - 1)
    return dict[n]

measure_fib(fib_dict)

# Fibonacci Sequence, using a decorator

def memoize(f):
    cache = {}

def fib_decorator(args):
        if args in cache:
            return cache[args]
        else:
            cache[args] = f(args)
        return cache[args]
      
    return fib_decorator

@memoize
def fib(n):
    if n == 0 or n == 1:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

measure_fib(fib)

# Fibonacci Sequence, using the functools library
# https://docs.python.org/3/library/functools.html
# Available only for Python >= 3.2

try:
    import functools

@functools.lru_cache(maxsize=None)
    def fib_functools(n):
        if n == 0 or n == 1:
            return n
        else:
            return fib_functools(n - 1) + fib_functools(n - 2)

measure_fib(fib_functools)
except:
    print("(You can't use functools with your version of Python.)")

[ + ] Show input
Absolute running time: 4.64 sec, cpu time: 4.51 sec, memory peak: 6 Mb, absolute service time: 4,65 sec