1. 1. In einem Wort

Das Erstellen von Notizen mit dem Dekorator @lru_cache war schneller als das programmgesteuerte Erstellen von Notizen.

2. Summe der Fibonacci-Zahlen

Die Summe der Fibonacci-Sequenz wird nach den folgenden drei Methoden rekursiv berechnet, und die Häufigkeit, mit der die rekursive Funktion aufgerufen und die Verarbeitungszeit aufgezeichnet wird. (Die Umgebung ist Google Colaboratory.) (1) Ordentliche Wiederholung (2) Wiederholung der Erinnerung (3) LRU-Cache @lru_cache

3. 3. Gewöhnlich rekursiv

Lassen Sie uns zunächst die Summe der Fibonacci-Zahlenfolge mit einer gewöhnlichen rekursiven Funktion ermitteln und messen.

%%time
fib_cnt=0
def fib(n):
    global fib_cnt
    fib_cnt+=1
    if n<=1:
        return n
    return fib(n-1)+fib(n-2)
fib1=fib(35)
print('fib1=',fib1)
print('fib1_cnt=',fib_cnt)

Das Ausführungsergebnis ist wie folgt. Nun, es braucht Zeit.

fib1= 9227465
fib1_cnt= 29860703
CPU times: user 4.93 s, sys: 5 ms, total: 4.94 s
Wall time: 4.94 s

4. Gespeicherte Wiederholung

Als nächstes suchen und messen wir die Summe der Fibonacci-Zahlenfolge mithilfe der Wiederholung von Gedenkstätten.

%%time
fib2_cnt=0
def fib2(n):
    memo=[0]*(n+1)
    def fib3(n):
        global fib2_cnt
        fib2_cnt+=1
        if n<=1:
            return n
        if memo[n]!=0:
            return memo[n]
        memo[n]=fib3(n-1)+fib3(n-2)
        return memo[n]
    return fib3(n)
fib2=fib2(35)
print('fib2=',fib2)
print('fib2_cnt=',fib2_cnt)

Das Ausführungsergebnis ist wie folgt. Natürlich wird es schneller sein.

fib2= 9227465
fib2_cnt= 69
CPU times: user 0 ns, sys: 1.69 ms, total: 1.69 ms
Wall time: 2.74 ms

Was besorgniserregend ist, ist die Häufigkeit, mit der es aufgerufen wird. Da es sich um eine Fibonacci-Zahlenfolge handelt, handelt es sich um die Summe der beiden vorhergehenden Zahlen, oder bei der Summe der Fibonacci-Folgen bis zu 35 wird sie 69-mal aufgerufen, was etwa doppelt so viel ist.

5. LRU-Cache @lru_cache

Lassen Sie uns abschließend versuchen, ein Memo mit dem LRU-Cache @lru_cache zu erstellen. LRU steht für Least Recent Used. Es bedeutet, dass ich es zuletzt verwendet habe.

%%time
from functools import lru_cache
fib4_cnt=0
@lru_cache(maxsize=None)
def fib4(n):
    global fib4_cnt
    fib4_cnt+=1
    if n<=1:
        return n
    return fib4(n-1)+fib4(n-2)
fib4=fib4(35)
print('fib4=',fib4)
print('fib4_cnt=',fib4_cnt)

In diesem Fall wird es 36 Mal von 0 bis 35 aufgerufen. Wird im vorherigen Programm seltener als rekursiv aufgerufen.

fib4= 9227465
fib4_cnt= 36
CPU times: user 1.74 ms, sys: 4 µs, total: 1.75 ms
Wall time: 1.61 ms

6. Zusammenfassung

Aufgrund der Struktur des Programms ist in diesem Beispiel der LRU-Cache @lru_cache schneller als die Wiederholung des Memorandums im Programm. Es mag gut sein, das Programm gut zu schreiben, aber es stellt sich heraus, dass der LRU-Cache schlank ist.