Using maps:merge/2 instead of Map.put/3 for Fib.mem/2:
# 3. using a result cache
defp mem_fill(n, kvs, _fib_i1, _fib_i, i) when n == i do
kvs
end
defp mem_fill(n, kvs, fib_i1, fib_i, i) when i < n do
fib_next = fib_i1 + fib_i
next = i + 1
mem_fill(n, [{next,fib_next}|kvs], fib_i, fib_next, next)
end
defp mem_fill(n,mem) do
[{_, fib_n}|_] = kvs =
with top <- Map.size(mem), # top - 1 = i
{:ok, fib_i1} <- Map.fetch(mem, top - 2), # i - 1
{:ok, fib_i} <- Map.fetch(mem, top - 1) do # i
mem_fill(n, [], fib_i1, fib_i, top-1)
else
_ -> # unexpected lookup failure - start fresh
mem_fill(n, [], 0, 1, 1)
end
more_mem = :maps.from_list(kvs)
new_mem = :maps.merge(mem, more_mem)
{fib_n, new_mem}
end
def mem(n, mem \\ %{0 => 0, 1 => 1}) when n >= 0 and is_integer(n) do
with {:ok, result} <- Map.fetch(mem, n) do
{result, mem}
else
_ -> # not found
mem_fill(n, mem)
end
end
$ mix profile.fprof -e Demo.load_1
Warmup...
Reading trace data...
...................................
End of trace!
Processing data...
Creating output...
Done!
CNT ACC (ms) OWN (ms)
Total 2967928 7451.080 7434.032
:fprof.apply_start_stop/4 0 7451.080 0.007
anonymous fn/0 in :elixir_compiler_1.__FILE__/1 1 7451.070 0.002
Demo.load_1/0 1 7451.068 0.001
Demo.run_load/2 1 7451.067 0.011
List.foldl/3 1 7451.023 0.001
List."-foldl/3-lists^foldl/2-0-"/3 9 7451.022 0.029
anonymous fn/2 in Demo.load_1/0 8 7450.993 0.010
Demo.run_1/2 8 7450.983 0.017
Fib.body/1 2959380 7450.397 7388.353
:garbage_collect 6511 44.996 44.996
:suspend 1704 17.048 0.000
Demo.run_2/2 8 0.569 0.040
Fib.mem/2 9 0.202 0.029
Fib.lco/1 20 0.178 0.033
Fib.mem_fill/2 6 0.163 0.072
Fib.ets/2 8 0.155 0.021
Fib.lco/4 105 0.145 0.145
Fib.ets_fill/2 6 0.125 0.020
Fib.ets_fill/6 35 0.096 0.072
Fib.mem_fill/5 35 0.051 0.051
:maps.find/2 21 0.023 0.023
:ets.insert/2 7 0.021 0.021
:ets.lookup/2 14 0.018 0.018
:ets.delete/1 1 0.014 0.014
Fib.ets_init/1 1 0.012 0.005
:maps.size/1 6 0.010 0.010
:maps.from_list/1 6 0.010 0.010
:maps.merge/2 6 0.007 0.007
Fib.mem/1 1 0.007 0.001
Fib.ets_top/3 7 0.007 0.007
:fprof."-apply_start_stop/4-after$^1/0-0-"/3 1 0.003 0.003
:ets.new/2 1 0.003 0.003
:undefined 0 0.000 0.000
$ mix profile.fprof -e Demo.load_2
Warmup...
Reading trace data...
....................................
End of trace!
Processing data...
Creating output...
Done!
CNT ACC (ms) OWN (ms)
Total 36778 74.796 72.899
:fprof.apply_start_stop/4 0 74.796 0.008
anonymous fn/0 in :elixir_compiler_1.__FILE__/1 1 74.785 0.002
Demo.load_2/0 1 74.783 0.001
Demo.run_load/2 1 74.782 0.009
List.foldl/3 1 73.435 0.001
List."-foldl/3-lists^foldl/2-0-"/3 6 73.434 0.026
anonymous fn/2 in Demo.load_2/0 5 73.408 0.006
Demo.run_2/2 5 73.402 0.028
Fib.lco/1 15 26.574 0.042
Fib.lco/4 16600 26.532 24.625
Fib.mem/2 6 23.493 0.023
Fib.mem_fill/2 5 23.463 0.062
Fib.ets/2 5 23.314 0.015
Fib.ets_fill/2 5 23.290 0.014
Fib.ets_fill/6 10004 23.264 15.164
Fib.mem_fill/5 10004 21.344 15.504
:garbage_collect 27 8.112 8.112
:ets.insert/2 6 5.860 5.860
:suspend 29 1.897 0.000
:maps.from_list/1 5 1.690 1.690
:ets.delete/1 1 1.320 1.294
:maps.merge/2 5 0.350 0.350
:ets.lookup/2 10 0.021 0.021
:maps.find/2 16 0.019 0.019
Fib.ets_init/1 1 0.010 0.004
Fib.mem/1 1 0.008 0.001
Fib.ets_top/3 6 0.007 0.007
:maps.size/1 5 0.005 0.005
:fprof."-apply_start_stop/4-after$^1/0-0-"/3 1 0.003 0.003
:ets.new/2 1 0.003 0.003
:undefined 0 0.000 0.000
