Fibonacci with Cache - Can this code be improved?

Questions / Help
1

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
    Agent.start_link(fn -> state end)
  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
2

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
3

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
4

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
5

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
6

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 :slight_smile:

3 Likes
7

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
8

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 :slight_smile: