avatar Bite 194. Add caching to a Fibonacci function

In this Bite you will learn about memoization: In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. (source).

In Python you can implement this technique using the functools.lru_cache decorator.

First write a simple fibonacci sequence calculator called cached_fib. It takes an argument n and returns the sum of the previous two values in the sequence (or the nth value of the Fibonacci sequence), so:

When n is 0, its fib value is n : fib(0) = 0
When n is 1, its fib value is n : fib(1) = 1
When n is 2, you add fib(1) and fib(0) : fib(2) = (1 + 0) = 1
When n is 3, you add fib(2) and fib(1) : fib(3) = (1 + 1) = 2
When n is 4, you add fib(3) and fib(2) : fib(4) = (2 + 1) = 3
When n is 5, you add fib(4) and fib(3) : fib(5) = (3 + 2) = 5
When n is 6, you add fib(5) and fib(4) : fib(6) = (5 + 3) = 8

The first test checks you return the correct result.

Next you speed it up using @lru_cache. The second test checks if your implementation is indeed faster than a classic fibonacci we wrote. As the fibonacci code is part of the spec we've hidden the tests to not give away too much.

Good luck and remember: keep calm and code in Python!

Thanks to @clamytoe for teaming up to deliver you this Bite.

Login and get coding
go back Intermediate level
Bitecoin 3X

Will you be Pythonista #106 to crack this Bite?
Resolution time: ~30 min. (avg. submissions of 5-240 min.)
Pythonistas rate this Bite 2.75 on a 1-10 difficulty scale.
» You can do it! 😌

Focus on this Bite hiding sidebars, turn on Focus Mode.