The goal of today's exercise is to implement a basic caching system in order to improve performance of a function. We will be working on a simple recursive version of the Fibonacci Sequence calculator.
Simple recursive function
Consider the following code in Python:
def fib(n):
if n <= 1:
return n
else:
return fib(n-1)+fib(n-2)
Let's forget for a second that the python interpreter has a limit to the depth of recursion (a limit that
can easily be changed).
There is a major problem with the performance of the above code, and it is apparent when looking at the execution stack.
Without looking at the order of execution of the recursive calls, here's what the interpreter will have to calculate:
fib (10)
= fib(9) + fib (8)
= fib(8) + fib(7) + fib(7) + fib(6)
= fib(7) + fib(6) + fib(6) + fib(5) + fib(6) + fib(5) + fib(5) + fib(4)
= ...
As you can see, a lot of calculations are repeated several times.
fib(6) for instance is calculated 4 times. The number can be much higher for greater arguments.
However
fib is a function that consistently returns the same value for a specific argument.
fib(6) always returns
13 no matter how many times you execute it. These functions are called
side-effect free.
Instead of calculating
fib(6) each time, we can optimize the function by making it remember which arguments it has already calculated and manage an internal database of which key/values can be returned immediately and which should be calculated again.
A reusable caching system
Before you get to coding, there are further requirements to the exercise.
We want to set a caching system that is somewhat reusable throughout the code. It doesn't need to be very complex or performant, but we should be able to add this behavior to any function in the program.
Basically what I'm saying is that you should implement the caching system without modifying the above
fib() function.
There are several ways to do this, more or less obvious depending on the language you are using. I will show you how to do it using Python decorators. We could maybe explore this using other languages.
A short presentation of Python decorators
Decorators are a lot less scary than what they look like. In order to understand them, you'd have to understand one simple concept:
In Python, functions are objects just like any other.
This means that functions can be given as arguments to other functions, functions can return functions and functions can be declared inside another function.
Just like any other regular object. For instance:
>>> a = abs # 'a' and 'abs' refer to the same function object.
>>> a
<built-in function abs>
>>> abs
<built-in function abs>
>>>
>>> print a(-4)
4
Once you understood that, you understood decorators that are nothing more than syntactic sugar for the following. Imagine you have defined a function called
foo() that takes a function as argument and returns a function. The two following codes are equivalent:
@foo
def bar(n):
return n+1
or
def bar(n):
return n+1
bar = foo(bar)
The exercise is then about creating a
@cached decorator that can modify (decorate) the way our fib function executes to add caching to it.
I will be working on this and post my solution as soon as I'm done.
Feel free to work in any language you want using any construct you want. I gave decorators as one example of achieving this, I'm sure there are others.
