If you're up for a challenge…
The classic Fibonacci implementation is
def fib(0), 0
def fib(1), 1
def fib(n), fib(n-1) + fib(n-2)
This has a worst case performance of \( O( 1.6^{n+1} ) \). For large \( n \), this is a big number (20 digits or so long for \( n = 100 \)). This means it is slow, and it burns through stack space at an alarming rate.
However, you can make the function perform in linear time by
implementing a simple cache. An Elixir map is a good data structure
for this. Initialize it with %{ 0 => 0, 1 => 1 }
, and add new values
to it as you discover them.
Write a module that implements the cache. It should use an agent, and that agent's state should be the map.
Then write a Fibonacci module that uses this cache.
Try calculating fib(100)
. If it comes back without crashing your
machine, and before the sun has expanded to consume the Earth, then
your cache worked...
Here is the code for my first iteration. Basically, I'm using the cache as a map, nothing fancy. More or less the code is like:
It's similar in some points to the proposed solution. But I get some interesting ideas from the proposed solution:
complete_if_not_found
is the first parameter. That allows you to use the pipe operator, and the code gets cleaner that mine. Very nice. Same forCache.set
.@pragdave - Question: is there a reason to compute
n-2
first atCachedFib.cached_fig
?