[PYTHON] Memorandum über das Auswendiglernen rekursiver Reihen

Auswendiglernen

Ein Memorandum von Memoization (Cache, Memo) am Beispiel von Fibonacci series. Vergleichen wir die Implementierung mit Mathematica (Wolfram-Sprache), Python und Julia. Das nächste Mal möchte ich über Memoization am Beispiel des Hermite-Polypolys nachdenken.

Ich dachte, es sei Memorization, aber r ist unnötig und scheint Memorization zu heißen.

Fibonacci-Serie

Jeder liebt Fibonacci-Klasse

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

Lassen Sie uns einfach den Term von ungefähr $ n = 40 $ mit der Fibonacci-Reihe bewerten. Lassen Sie uns etwas Memoization (Cache) implementieren.

python

Wäre es wie folgt, wenn es einfach in Python geschrieben wäre?

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))

Auf dem Laptop zur Hand

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

Es ist schneller, wenn Sie das Berechnungsergebnis mit dem Wörterbuch zwischenspeichern

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

Da das Berechnungsergebnis von $ \ {F_n } $ gespeichert wird, steigt die Speichernutzung etwas an. Ein gleichwertiger Cache kann kostengünstig in der Standardbibliothek functools lru_cache implementiert werden.

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-Sprache)

Ist die naive Implementierung so?

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 der Wolfram-Sprache ist $: = $ eine verzögerte Auswertung (Definition) und $ = $ eine sofortige Auswertung. In Kombination 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]]

Dann kann das Berechnungsergebnis zwischengespeichert werden

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

Die Wolfram-Sprache ist mit einem erheblichen Overhead verbunden, und es gibt einen großen Unterschied zwischen der Zeit für die Funktionsbewertung und der Zeit für die tatsächliche Messung. Außerdem scheint die Speichernutzung tendenziell größer zu sein als die von Python.

julia

Wäre es wie folgt, wenn es einfach geschrieben würde?

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]

Selbst eine einfache Implementierung ist sehr schnell. Wenn Sie mit einem Wörterbuch wie Python zwischenspeichern

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]

Noch schneller. Es ist keine Standardbibliothek, aber wenn Sie Julia Memoize für die Installation und Vorkompilierung verwenden

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]

Und die für die Funktionsbewertung benötigte Zeit wird noch schneller. Andererseits scheint die Ausführungszeit des Programms etwas länger zu sein, wahrscheinlich weil das Laden und Kompilieren des Pakets einige Zeit in Anspruch nimmt.