[PYTHON] Memorandum on Memoization of recursive series

Memoization

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.

Fibonacci series

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]

Mathematica (Wolfram Language)

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.