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...
I have done it without recursion but I do not know if that'd be a problem. Also, don't know if it makes sense to hold the full cache of all numbers if the problem statement asks for the nth Fibbonaci number. My below solution only holds latest two and calculates.
`defmodule Cache do
def start_value do
%{:first => 0, :second => 1}
end
def init() do
Agent.start_link(fn -> start_value end, name: :cache)
end
def init({:error, _}) do
Cache.init
end
def init({:ok, _}) do
end
def get(key) do
Agent.get(:cache, fn(keymap) -> keymap |> Map.get(key) end )
end
def update(key, value) do
Agent.update(:cache, fn(keymap) -> keymap |> Map.put(key, value) end)
end
def reset() do
Agent.update(:cache, fn(keymap) -> start_value end)
end
end
defmodule fibocached do
def fibbonaci(0) do Cache.get(:first) end
def fibbonaci(1) do Cache.get(:second) end
def fibbonaci(n) do
Cache.reset
range = 2..n
|> Enum.map(&step/1)
Cache.get(:second)
end
def step(number) do
first = Cache.get(:first)
Cache.update(:first, Cache.get(:second))
Cache.update(:second, Cache.get(:second) + first)
end
def run(n) do
Cache.init
FiboCached.fibbonaci(n)
end
def print_cache do
IO.puts("First is #{Cache.get(:first)} Second is #{Cache.get(:second)}")
end
end`
Thanks @praddave for the awesome course ! Continuing with further modules with lots of enthusiasm..