Our Fibonacci code is really inefficient. To calculate fib(5), we calculate this:
| | fib(5) |
| | = fib(4) + fib(3) |
| | = fib(3) + fib(2) + fib(2) + fib(1) |
| | = fib(2) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) |
| | = fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) |
Look at all that duplication. If only we could cache the intermediate values.
As you know, Elixir modules are basically buckets of functions—they cannot hold state. But processes can hold state. And Elixir comes with a library module called Agent that makes it easy to wrap a process containing state in a nice module interface. Don’t worry about the details of the code that follows—we cover agents and tasks. For now, just see how processes are among the tools we use to add persistence to Elixir code. (This code comes from a mailing-list post by José Valim, written in response to some ugly code I wrote.)
| | defmodule FibAgent do |
| | def start_link do |
| | Agent.start_link(fn -> %{ 0 => 0, 1 => 1 } end) |
| | end |
| | |
| | def fib(pid, n) when n >= 0 do |
| | Agent.get_and_update(pid, &do_fib(&1, n)) |
| | end |
| | |
| | defp do_fib(cache, n) do |
| | case cache[n] do |
| | nil -> |
| | { n_1, cache } = do_fib(cache, n-1) |
| | result = n_1 + cache[n-2] |
| | { result, Map.put(cache, n, result) } |
| | |
| | cached_value -> |
| | { cached_value , cache } |
| | end |
| | end |
| | |
| | end |
| | |
| | {:ok, agent} = FibAgent.start_link() |
| | IO.puts FibAgent.fib(agent, 2000) |
Let’s run it:
| | $ elixir fib_agent.exs |
| | 42246963333923048787067256023414827825798528402506810980102801373143085843701 |
| | 30707224123599639141511088446087538909603607640194711643596029271983312598737 |
| | 32625355580260699158591522949245390499872225679531698287448247299226390183371 |
| | 67780606070116154978867198798583114688708762645973690867228840236544222952433 |
| | 47964480139515349562972087652656069529806499841977448720155612802665404554171 |
| | 717881930324025204312082516817125 |
If we’d tried to calculate fib(2000) using the noncached version, the sun would grow to engulf the Earth while we were waiting for it to finish.