1. 1. En un mot

Prendre des notes à l'aide du décorateur @lru_cache était plus rapide que de prendre des notes par programmation.

2. Somme des nombres de Fibonacci

La somme de la séquence de Fibonacci est calculée de manière récursive par les trois méthodes suivantes, et le nombre de fois que la fonction récursive est appelée et le temps de traitement sont enregistrés. (L'environnement est Google Colaboratory.) (1) Récurrence ordinaire (2) La mémorisation se reproduit (3) Cache LRU @lru_cache

3. 3. Récursif ordinaire

Tout d'abord, trouvons la somme de la séquence de nombres de Fibonacci avec une fonction récursive ordinaire et mesurons-la.

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

Le résultat de l'exécution est le suivant. Eh bien, cela prend du temps.

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

4. Récurrence mémorisée

Ensuite, trouvons et mesurons la somme de la séquence de nombres de Fibonacci en utilisant la récurrence commémorative.

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

Le résultat de l'exécution est le suivant. Naturellement, ce sera plus rapide.

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

Ce qui est inquiétant, c'est le nombre de fois où il est appelé. Puisqu'il s'agit d'une séquence de nombres de Fibonacci, c'est la somme des deux nombres précédents, ou dans le cas de la somme de la séquence de Fibonacci jusqu'à 35, elle est appelée 69 fois, ce qui est environ deux fois plus.

5. Cache LRU @lru_cache

Enfin, essayons de créer un mémo en utilisant le cache LRU @lru_cache. LRU signifie moins récemment utilisé. Cela signifie que je l'ai utilisé le plus récemment.

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

Dans ce cas, il sera appelé 36 fois de 0 à 35. Appelé moins souvent que récursif dans le programme précédent.

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

6. Résumé

En raison de la structure du programme, dans cet exemple, le cache LRU @lru_cache est plus rapide que la récurrence de mémorandum dans le programme. Il peut être bon de bien écrire le programme, mais il s'avère que le cache LRU est maigre.