Memoization
===========

.. toctree::
   :maxdepth: 1


Indices and tables
------------------

* :ref:`genindex`
* :ref:`modindex`
* :ref:`search`

.. _section_heading-Memoization:

Overview
--------
* Memoization is a programming technique used to increase the speed of program execution by storing function results so that they can be used later on.

Factorial Example
^^^^^^^^^^^^^^^^^
* Consider the following function used to calculate factorials:

  .. code-block:: python
     :linenos:

     #!/usr/bin/python3

     def factorial(k):
         if k < 2:
             return 1
         return k * factorial(k - 1)

* Since this is a recursive function, it is easy to see how this function would get expensive for large values of 'k'. But what if we didn't have to recompute the results each time?
* We can 'memoize' the function:

  .. code-block:: python
     :linenos:

     #!/usr/bin/python3

     cache = {}
     def factorial(k):
         if k < 2:
             return 1
         if k not in cache:
             cache[k] = k * factorial(k - 1)
         return cache[k]

* The above example simply adds caching to the function itself. A more elegant solution, however, might be to wrap the function using a special 'Memoize' class

  .. code-block:: python
     :linenos:

     #!/usr/bin/python3

     class Memoize:
        def __init__(self, fn):
            self.fn = fn
            self.memo = {}
        def __call__(self, *args):
            if args not in self.memo:
	            self.memo[args] = self.fn(*args)
                return self.memo[args]

     @Memoize
     def factorial(k):
         if k < 2:
             return 1
         return k * factorial(k - 1)

  .. note:: The example above makes use of a decorator. This is equivalent to factorial = Memoize(factorial).
* Finally, Python actually has a built-in decorator in the functools module, 'lru_cache':

  .. code-block:: python
     :linenos:

     #!/usr/bin/python3

     import functools

     @functools.lru_cache
     def factorial(k):
         if k < 2:
             return 1
         return k * factorial(k - 1)

* This director has an optional maxsize argument which allows the programmer to specify the maximum size of the cache

Challenge
^^^^^^^^^
* Try memoizing this fibonacci sequence method in different ways. Compare them using the timeit module.

  .. code-block:: python
     :linenos:

     #!/usr/bin/python3

     def fibonacci(n):
         if n == 0:
             return 0
         elif n == 1:
             return 1
         else:
             return fibonacci(n - 1) + fibonacci(n - 2)