Skip to content

Instantly share code, notes, and snippets.

@pragdave
Last active July 16, 2022 23:35
Show Gist options
  • Save pragdave/f8c7684b69d235269139bad0a2419273 to your computer and use it in GitHub Desktop.
Save pragdave/f8c7684b69d235269139bad0a2419273 to your computer and use it in GitHub Desktop.
«tutor»:e4p~basic-processes~fib

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

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
@carloscasalar
Copy link

I know I should extract cache functions to another module but this is roughly my solution:

defmodule FibonacciWithCache do
  def fib(0), do: 0

  def fib(1), do: 1

  def fib(n) do
    cache_pid = init_cache()
    value = fib(cache_pid, n)
    clean_cache(cache_pid)
    value
  end

  defp fib(cache_pid, 0) do
    get_from_cache(cache_pid, 0)
  end

  defp fib(cache_pid, 1) do
    get_from_cache(cache_pid, 1)
  end

  defp fib(cache_pid, n) do
    calculate_fib_storing_in_cache(cache_pid, n, get_from_cache(cache_pid, n))
  end

  defp calculate_fib_storing_in_cache(cache_pid, n, nil) do
    value = fib(cache_pid, n - 1) + fib(cache_pid, n - 2)
    update_cache_and_get_value(cache_pid, n, value)
  end

  defp calculate_fib_storing_in_cache(_cache_pid, _n, value), do: value

  defp init_cache do
    {:ok, cache_pid} = Agent.start_link(fn -> %{0 => 0, 1 => 1} end)
    cache_pid
  end

  defp clean_cache(cache_pid) do
    Agent.stop(cache_pid)
  end

  defp update_cache_and_get_value(cache_pid, n, value) do
    Agent.get_and_update(cache_pid, fn cache_value ->
      {value, Map.merge(cache_value, %{n => value})}
    end)
  end

  defp get_from_cache(cache_pid, n) do
    Agent.get(cache_pid, fn cache_value -> cache_value[n] end)
  end
end

@herminiotorres
Copy link

My solution for a Fibonacci with Agent:

fibonacci_cached.exs:

defmodule FibonacciCached do
  def start() do
    Agent.start_link(fn -> %{0 => 0, 1 => 1} end)
  end

  def get(agent, key) do
    state = Agent.get(agent, fn state -> state end)
    Map.get(state, key)
  end

  def add(agent, key, value) do
    Agent.update(agent, fn state -> Map.put(state, key, value) end)
  end

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

fibonacci.exs:

defmodule Fibonacci do
  def start() do
    FibonacciCached.start()
  end

  def print(agent) do
    FibonacciCached.print(agent)
  end

  def calculate(_agent, 0), do: 0
  def calculate(_agent, 1), do: 1

  def calculate(agent, key) do
    case FibonacciCached.get(agent, key) do
      nil ->
        value = calculate(agent, key-1) + calculate(agent, key-2)
        FibonacciCached.add(agent, key, value)
        value
      cached_value ->
        cached_value
    end
  end
end

call IEx:

$ iex
iex> c "fibonacci_cached.exs"
[FibonacciCached]
iex> c "fibonacci.exs"       
[Fibonacci]
iex> {:ok, agent} = Fibonacci.start()
{:ok, #PID<0.125.0>}
iex> Fibonacci.calculate(agent, 10)
55
iex> Fibonacci.print(agent)        
%{
  0 => 0,
  1 => 1,
  2 => 1,
  3 => 2,
  4 => 3,
  5 => 5,
  6 => 8,
  7 => 13,
  8 => 21,
  9 => 34,
  10 => 55
}

@lgprall
Copy link

lgprall commented May 29, 2020

This is kind of a simple solution. First thing I came up with; I need to look over some of the other solutions to see what I missed.

[NB] Guess I missed the point about having a separate module for the cache...

defmodule Fib do

  def find(0), do: 0
  def find(1), do: 1
  def find(2), do: 1

  def find(count)  do

    {:ok, pid } = Agent.start_link(fn -> %{ 0 => 0, 1 => 1} end)
    for _n <- 1..div(count, 2), do: update(pid)
    Agent.get(pid, fn map -> map end)
    |> pick(count)

  end

  def pick(map,count) when rem(count,2) == 0, do: map[0]

  def pick(map,_), do: map[1]

  def update(pid) do
    Agent.update(pid, fn map -> %{map | 0 => (map[0] + map[1])} end)
    Agent.update(pid, fn map -> %{map | 1 => (map[0] + map[1])} end)
  end
end

iex(7)> Fib.find 100
354224848179261915075
iex(8)> Fib.find 1000
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
iex(9)> Fib.find 10000
336447648764317832666216120051075433103021484606800639065647699746800814421666623681555955136337340255820... . . .
642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
iex(110)>

@tejpochiraju
Copy link

tejpochiraju commented Nov 16, 2020

My first solution used an externally exposed PID. After stealing the run(body) portion of @pragdave's solution that hides the PID, here's where I arrived:

fibonacci.ex:

defmodule Fibonacci do
  def fib(pid, n) do
    state = Agent.get(pid, fn state -> state end)
    cond do
      state[n] -> state[n]
      true ->
        result = fib(pid, n-1) + fib(pid, n-2)
        Agent.update(pid, fn state -> Map.put(state, n, result) end)
        result
    end
  end

  def cached_fib(n) do
    FibCache.run(fn pid -> fib(pid, n) end)
  end

end

cache.ex:

defmodule FibCache do
  def run(body) do
    {:ok, pid} = Agent.start_link(fn -> %{0 => 0, 1 => 1} end)
    result = body.(pid)
    Agent.stop(pid)
    result
  end
end

I find this a lot more readable, albeit with the use of cond.

@wuziq
Copy link

wuziq commented Mar 16, 2021

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

@jeffdevr
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment