Background
In my never ending quest to learn Elixir I am now doing another Codewars exercise. The description is as follows:
Given a number, say prod (for product), we search two Fibonacci numbers F(n) and F(n+1) verifying
F(n) * F(n+1) = prod.
The real challenge
This is one of my favorites, taking me back to the University days. As any seasoned developer knows, Fibonnaci exercises are mainly used for two things:
- Introducing recursivity
- Forcing you to think about code optimization
In this specific case, it is the second. The code is supposed to pass tests with the following parameters:
ProdFib.product_fib(2563195080744681828)
Naive implementation
The first, and most naive, way to solve this exercise is to simply do it without a cache:
Spoiler
defmodule ProdFib do
def product_fib(n) do
product_fib(0, 1, n)
end
defp product_fib(f1, f2, prod) do
fib_1 = fibonacci(f1)
fib_2 = fibonacci(f2)
cond do
fib_1 * fib_2 == prod -> [fib_1, fib_2, true]
fib_1 * fib_2 > prod -> [fib_1, fib_2, false]
true -> product_fib(f1+1, f2+1, prod)
end
end
defp fibonacci(0), do: 0
defp fibonacci(1), do: 1
defp fibonacci(n) do
fibonacci(n-1) + fibonacci(n-2)
end
end
Now this code works. But you will eventually start to have timeouts because you are repeating a lot of computations you donāt need.
How to improve it?
We add a cache !
The Bad cache
So my first approach was to use module attributes to save a map which would work as a cache:
Spoiler
defmodule ProdFib do
@fib_table %{}
def product_fib(n) do
product_fib(0, 1, n)
end
defp product_fib(f1, f2, prod) do
fib_1 = fibonacci(f1)
fib_2 = fibonacci(f2)
cond do
fib_1 * fib_2 == prod -> [fib_1, fib_2, true]
fib_1 * fib_2 > prod -> [fib_1, fib_2, false]
true -> product_fib(f1+1, f2+1, prod)
end
end
defp fibonacci(0), do: 0
defp fibonacci(1), do: 1
defp fibonacci(n) do
case Map.get(@fib_table, n) do
nil ->
val = fibonacci(n-1) + fibonacci(n-2)
Map.put(@fib_table, n, val)
val
res -> res
end
end
end
This does NOT work. After checking the documentation for module attributes I understand that module attributes are defined at compile time, and thus cannot not mutate at runtime:
https://elixir-lang.org/getting-started/module-attributes.html
However, I still needed a cacheā¦
The Ugly cache
So I have been reading about ETS and I thought that since I need a global cache for this exercise, and since one of ETSās main uses is to cache things, that it would fit perfectly !
Spoiler
defmodule ProdFib do
def product_fib(n) do
try do
:ets.new(:fibo_cache, [:protected, :named_table, :set])
product_fib(0, 1, n)
catch
_, _ -> product_fib(0, 1, n)
end
end
defp product_fib(f1, f2, prod) do
fib_1 = fibonacci(f1)
fib_2 = fibonacci(f2)
cond do
fib_1 * fib_2 == prod -> [fib_1, fib_2, true]
fib_1 * fib_2 > prod -> [fib_1, fib_2, false]
true -> product_fib(f1+1, f2+1, prod)
end
end
defp fibonacci(0), do: 0
defp fibonacci(1), do: 1
defp fibonacci(n) do
case :ets.lookup(:fibo_cache, n) do
[] ->
val = fibonacci(n-1) + fibonacci(n-2)
:ets.insert(:fibo_cache, {n, val})
val
[{_key, val}] -> val
end
end
end
So, this code works. It passes all tests and never times out. But it is really ugly.
Problems with Ugly cache
- I am using a
try/catch
for control flow. We donāt use errors for control flow. - This example is not really testable. I am using a global ETS table as a cache. Globals are evil. Adding to this point, there is a chance that some of you may think ETS to be overkill for this. And to be honest I wouldnāt have any arguments to prove you wrong.
I need a Good cache
So, the solution to the previous problem would be:
- Donāt use errors for control flow. Just donāt.
- Instead of relying in a global table for cache, one could create an empty map, and pass it around as state. The problem with this approach is that I failed miserably with it. Hence, the usage of ETS.
This works and all but ā¦
But I was wondering if my example could be improved?
I am pretty much sure someone here will have ideas on how to solve issue 1 ( remove control flow via errors ) and as far as issue 2 goes perhaps there is a different approach I am not yet familiar with.
Any ideas?