# Fibonacci with Cache - Can this code be improved?

As per challenge in the PragDave course we must use a Cache mechanism via Agents in order to solve the Fibonacci challenge:

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…

My Fibonacci module:

``````defmodule Fibonacci do
@moduledoc """
# Fibonacci Sequence

As per challenge in the PragDave course we must use a Cache mechanism via Agents

Check exercise at https://codestool.coding-gnome.com/courses/take/elixir-for-programmers-2/texts/29542517-agents-an-abstration-over-state

My first pass at this used a Map as per the exercise recommendation, but then
I realized that I was converting it into a list and then reversing it on every
time I retrieved it from the cache for finding the next number in the sequence,
therefore I refactored the code to just use a list to store the state in the
cache and got a much nicer and clean implementation.

In the first edition of the course I think I solved this exercise and just by
using a list that would be passed as an accumulator while doing the recursion.
"""

@doc """
## Calculate the Fibonacci sequence

Run from iex:

iex> Fibonacci.fib 1000
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]
:ok

The returned list is conform the Fibonacci sequence listedin Wikipedia: https://en.wikipedia.org/wiki/Fibonacci_number

"""
def fib(number) when number <= 0 do
IO.puts("Please provide a number greater then 0")
end

def fib(number) do
{:ok, cache} = FibonacciCache.start_cache([1, 0])
_fib(cache, number, 1)
end

# The exit condition
defp _fib(cache, number, current_number) when number <= current_number do
Agent.get(cache, fn state -> state end)
|> Enum.reverse()
|> IO.inspect()

Agent.stop(cache)
end

defp _fib(cache, number, 1) do
FibonacciCache.update(cache, 1)
_fib(cache, number, 2)
end

defp _fib(cache, number, 2) do
FibonacciCache.update(cache, 2)
_fib(cache, number, 3)
end

defp _fib(cache, number, _current_number) do
[n1, n2 | _tail] = FibonacciCache.get(cache)

current_number = n1 + n2

cache
|> _update_cache(number, current_number)
|>_fib(number, current_number)
end

defp _update_cache(cache, number, current_number) when current_number <= number do
FibonacciCache.update(cache, current_number)
cache
end

defp _update_cache(cache, _, _), do: cache

end
``````

My Fibonacci Cache:

``````defmodule FibonacciCache do

@moduledoc """
# Fibonacci Cache

As per challenge in the PragDave course we must use a Cache mechanism via Agents

Check exercise at https://codestool.coding-gnome.com/courses/take/elixir-for-programmers-2/texts/29542517-agents-an-abstration-over-state

"""

def start_cache(state) do
end

def update(cache, number) do
Agent.get_and_update(cache, fn state -> new_state = [number | state]; { new_state, new_state } end)
end

def get(cache) do
Agent.get(cache, fn state -> state end)
end

end
``````

Please bear in mind that I know I can solve this without using an Agent to cache the the numbers in the Fibonacci sequence, and with that in mind I would like to ask you this question:

What would you improve and/or make different in the `Fibonacci` or `FibonacciCache` modules?

2 Likes

I guess the first think I’d change would be the implementation of the state from a list that will grow the execution exponentially in time, to a map.

3 Likes

Why do you say so?

I ask, because both the map and the list will have to grow, and I am accessing the head of the list in each recursion, while using the map I would have to do more work to get the last two number for the sequence.

2 Likes

Because you can re-use the already calculated state as persistent cache for multiple runs of `Fibonacci.fib`. Then you only have to further calculate the sequence for the values not already in the cache.

3 Likes

Perhaps this is outside of your question, but check out the memoize module on github.

The same ideas can be used for this problem, thought I’d be wary of the Agent has a pid.

3 Likes

That makes a lot of sense, and I feel now stupid for not thinking properly on it.

Maybe I have not realised that because I am stopping the Cache after being done with the calculation, just like PragDave does in is solution.

My first solution with the use of Maps was not stopping the Cache after being done with the calculation, but was always doing the calculation, thus not taking advantage of your suggestion.

Thanks for the clarification 3 Likes

An important general performance tip with Agents: returning the entire state from `get` means copying the entire structure from the Agent’s heap to the caller’s heap. Most of the time, you don’t actually want the whole state:

``````  defp _fib(cache, number, _current_number) do
[n1, n2 | _tail] = FibonacciCache.get(cache)
``````

A more efficient way to write the above would be with a new function on `FibonacciCache`:

``````def top_two(cache) do
Agent.get(cache, fn [n1, n2 | _rest] -> {n1, n2} end)
end
``````

and then the implementation simplifies to:

``````defp _fib(cache, number, _current_number) do
{n1, n2} = FibonacciCache.top_two(cache)
# etc
``````
5 Likes

Thanks for remembering me of this, because I completely had forgotten that in the BEAM this occurs due to it being immutable in the way it treats data persistence in memory.

Yes, I believe that in most situations we will not need the entire state to be returned from the Agent.

I though in getting only the last two as you suggested but then I felt that I was moving logic to the Cache and haven’t tried to do it, but now with your help I see that I was not thinking clearly about it.

Many thanks for your opening eyes reply 