Mémorandum sur la mémorisation de séries récursives

Mémorisation

Un mémorandum de Memoization (cache, mémo) utilisant série Fibonacci comme exemple. Comparons l'implémentation avec Mathematica (langage Wolfram), python et julia. La prochaine fois, j'aimerais penser à la mémorisation en utilisant le polypole Hermite comme exemple.

Je pensais que c'était de la mémorisation, mais r n'est pas nécessaire et semble s'appeler mémorisation.

Série Fibonacci

Tout le monde aime le grade Fibonacci

\begin{align}
&F_0 = 0,\\ 
&F_1 = 1,\\
&F_n = F_{n-1} + F_{n-2} \quad (n>1)
\end{align}

Évaluons simplement le terme d'environ $ n = 40 $ avec la série de Fibonacci. Implémentons une mémorisation (cache).

python

Serait-ce comme suit s'il était écrit simplement en 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))

Sur l'ordinateur portable à portée de main

$ 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]

Ce sera plus rapide si vous mettez en cache le résultat du calcul à l'aide du dictionnaire

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

Puisque le résultat du calcul de $ \ {F_n } $ est sauvegardé, l'utilisation de la mémoire augmente un peu. Le cache équivalent peut être implémenté à faible coût dans la bibliothèque standard 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 (langue Wolfram)

Est-ce que la mise en œuvre naïve est comme ça?

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]

Dans le langage wolfram, $: = $ est une évaluation retardée (définition) et $ = $ est une évaluation immédiate. En combinaison 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]]

Ensuite, le résultat du calcul peut être mis en cache

$ /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]

Il y a peut-être beaucoup de frais généraux dans le langage wolfram, et il y a une grande différence entre le temps pour l'évaluation des fonctions et le temps pour la mesure réelle. En outre, l'utilisation de la mémoire semble avoir tendance à être plus importante que celle de python.

julia

Serait-ce comme suit s'il était écrit simplement?

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]

Même une mise en œuvre simple est très rapide. Si vous mettez en cache en utilisant un dictionnaire comme 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]

Même plus vite. Ce n'est pas une bibliothèque standard, mais si vous utilisez Julia Memoize avec installation et précompilation

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]

Et le temps nécessaire à l'évaluation des fonctions devient encore plus rapide. D'un autre côté, il semble que le temps d'exécution du programme sera un peu plus long, probablement parce qu'il faut du temps pour charger et compiler le paquet.