«tutor»:e4p~basic-processes~fib

00-question.md

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...

fib_cache.exs

defmodule Cache do

  @moduledoc """
  We implement a simple key/value cache. State is stored in an Agent, in
  the form of a map.

  The function `lookup` tries to look the value up in the cache, and then
  calls `complete_if_not_found`. This takes two forms. If there was
  no value in the cache, it calls the function passed in by the client
  to supply it, updating the cache at the same time.

  Otherwise, it simply returns the cached value.
  """

  @doc """
  Start the cache, run the supplied function, then stop the cache.
  
  Eventually we'll be able to do better than this.
  """
  
  def run(body) do
    { :ok, pid } = Agent.start_link(fn -> %{ 0 => 0, 1 => 1 } end)
    result = body.(pid)
    Agent.stop(pid)
    result
  end
 
  def lookup(cache, n, if_not_found) do
    Agent.get(cache, fn map -> map[n] end)
    |> complete_if_not_found(cache, n, if_not_found)
  end

  defp complete_if_not_found(nil, cache, n, if_not_found) do
    if_not_found.()
    |> set(cache, n)
  end

  defp complete_if_not_found(value, _cache, _n, _if_not_found) do
    value
  end
  
  defp set(val, cache, n) do
    Agent.get_and_update(cache, fn map ->
      { val, Map.put(map, n, val)}
    end)
  end
end


defmodule CachedFib do

  def fib(n) do
    Cache.run(fn cache ->
      cached_fib(n, cache)
    end)
  end

  defp cached_fib(n, cache) do
    Cache.lookup(cache, n, fn ->
      cached_fib(n-2, cache) + cached_fib(n-1, cache)
    end)
  end

end

@pragdave @reneweteling

Could you explain why there's a race race condition with Agent.update() vs none with Agent.get_and_update()?

That's right. It's kinda a big deal, though. Being a language that encourages concurrency, that kind of nontransactional update can cause problems more easily than in most. Thanks for the kind words. Dave
…
On Mon, Oct 14, 2019 at 2:17 AM Rene Weteling @.***> wrote: @pragdave https://github.com/pragdave so that would be in in the: Agent.update(pid, fn state -> Map.put(state, n, calculated) end) It should probably be Agent.get_and_update to make it sequential? Like you mentioned it did not affect the result so I didn't notice it. And I must say, I'm enjoying myself immensely with the course, its funny, insightful and great to do. It has taken me quite some time to start, I was intrigued by the language by your talk in Amsterdam, and now finally started working with Elixir, it's great. Thanks for the course! Can't wait to continue tonight 👍 — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://gist.github.com/f8c7684b69d235269139bad0a2419273?email_source=notifications&email_token=AAACTGA6OKOIGC7ACTBJMSTQOQMJ3A5CNFSM4HQCVAUKYY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAF2NXG#gistcomment-3054451, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAACTGAT5H2BPKCFUCL3RO3QOQMJ3ANCNFSM4HQCVAUA .

Using || can remove all the explicit testing against nil, and it's very convenient having your update function return the new value.

defmodule Cache do

  def start(initial_map = %{}) do
    {:ok, pid } = Agent.start_link(fn -> initial_map end)
    pid
  end

  def put(pid, key, value) do
    Agent.update(pid, &Map.put(&1, key, value))
    value
  end

  def get(pid, key) do
    Agent.get(pid, &Map.get(&1, key))
  end

end

defmodule FibCache do

  def fib(n) do
    Cache.start(%{ 0 => 0, 1 => 1 })
    |> fib_iter(n)
  end

  defp fib_iter(cache, n) do
    Cache.get(cache, n) ||
      Cache.put(cache, n, fib_iter(cache, n-1) + fib_iter(cache, n-2))
  end

end