A memorandum of Memoization (cache, memoization) using Fibonacci series as an example. Let's compare the implementation with Mathematica (Wolfram language), python, and julia. Next time, I would like to consider Memoization using the Hermite polynomial as an example.
I thought it was Memorization, but r is unnecessary and it seems to be called Memoization.
Everyone loves Fibonacci series
\begin{align}
&F_0 = 0,\\
&F_1 = 1,\\
&F_n = F_{n-1} + F_{n-2} \quad (n>1)
\end{align}
Let's simply evaluate the term of about $ n = 40 $ in the Fibonacci series. Let's implement some Memoization (cache).
python
Would it be as follows if written simply in python?
fib.py
import time
def fib(n):
if n < 2:
return n
else:
return fib(n-1) + fib(n-2)
a = time.time()
n=40
res = fib(n)
print(time.time() -a, "[sec]", "f(%d)=%d" % (n, res))
On my laptop
$ fmt="\nreal:%e[sec]\nuser:%U[sec]\nsys:%S[sec]\nMemory:%M[KB]"
$ /usr/bin/time -f ${fmt} python fib.py
53.77412390708923 [sec] f(40)=102334155
real:53.83[sec]
user:52.57[sec]
sys:0.04[sec]
Memory:6480[KB]
It will be faster if you cache the calculation result using dictionary
fib.py
import time
fib_d={0:0, 1:1}
def fib(n):
if n in fib_d:
return fib_d[n]
else:
res = fib(n-1) + fib(n-2)
fib_d[n] = res
return res
a = time.time()
n=40
res = fib(n)
print(time.time() -a, "[sec]", "f(%d)=%d" % (n, res))
$ /usr/bin/time -f ${fmt} python fib.py
2.09808349609375e-05 [sec] f(40)=102334155
real:0.05[sec]
user:0.03[sec]
sys:0.03[sec]
Memory:6488[KB]
$ /usr/bin/time -f ${fmt} python fib.py
Since the calculation result of $ \ {F_n } $ is saved, the memory usage increases a little. The equivalent cache can be implemented at low cost in the standard library functools lru_cache.
fib.py
from functools import lru_cache
import time
@lru_cache(maxsize=1000)
def fib(n):
if n < 2:
return n
else:
return fib(n-1) + fib(n-2)
a = time.time()
n=40
res = fib(n)
print(time.time() -a, "[sec]", "f(%d)=%d" % (n, res))
$ /usr/bin/time -f ${fmt} python fib.py
2.0742416381835938e-05 [sec] f(40)=102334155
real:0.10[sec]
user:0.01[sec]
sys:0.03[sec]
Memory:6500[KB]
Is the naive implementation like this?
fib.wl
F[n_]:=F[n-2] + F[n-1]
F[0] = 0
F[1] = 1
Print[Timing@F[40]]
$ /usr/bin/time -f ${fmt} wolframscript -script fib.wl
{336.265625, 102334155}
real:346.60[sec]
user:336.37[sec]
sys:1.28[sec]
Memory:114468[KB]
In Wolfram Language, $: = $ is lazy evaluation (definition) and $ = $ is immediate evaluation. In combination https://reference.wolfram.com/language/tutorial/FunctionsThatRememberValuesTheyHaveFound.html
fib.wl
F[n_]:=F[n]=F[n-2] + F[n-1]
F[0] = 0
F[1] = 1
Print[Timing@F[40]]
Then the calculation result can be cached
$ /usr/bin/time -f ${fmt} wolframscript -script fib.wl
{0., 102334155}
real:1.20[sec]
user:0.56[sec]
sys:0.71[sec]
Memory:114564[KB]
In the wolfram language, there is a considerable overhead, and there is a large difference between the time for function evaluation and the time for actual measurement. Also, the memory usage seems to tend to be larger than that of python.
julia
Would it be as follows if written simply?
fib.jl
function fib(n)
if n<2
return n
else
return fib(n-1) + fib(n-2)
end
end
b = @time fib(40)
@show b
$ /usr/bin/time -f ${fmt} julia fib.jl
0.783497 seconds (2.56 k allocations: 235.453 KiB)
b = 102334155
real:1.19[sec]
user:1.25[sec]
sys:0.32[sec]
Memory:125392[KB]
Even a simple implementation is very fast. If you cache using a dictionary like python
fib.jl
known = Dict(0=>0, 1=>1)
function fibonacci(n)
if n ∈ keys(known)
return known[n]
end
res = fibonacci(n-1) + fibonacci(n-2)
known[n] = res
res
end
b = @time fibonacci(40)
@show b
$ /usr/bin/time -f ${fmt} julia fib.jl
0.047068 seconds (7.81 k allocations: 508.287 KiB)
b = 102334155
real:0.81[sec]
user:0.43[sec]
sys:0.65[sec]
Memory:127560[KB]
Even faster. It's not a standard library, but if you use Julia Memoize with install and precompile
fib.jl
using Memoize
@memoize function fib(n)
if n<2
return n
else
return fib(n-1) + fib(n-2)
end
end
b = @time fibonacci(40)
@show b
$ /usr/bin/time -f ${fmt} julia fib.jl
0.022669 seconds (33.39 k allocations: 1.714 MiB)
b = 102334155
real:2.81[sec]
user:2.70[sec]
sys:0.53[sec]
Memory:188900[KB]
And the time required for function evaluation becomes even faster. On the other hand, it seems that the execution time of the program will be a little longer, probably because it takes time to load and compile the package.
Recommended Posts