Il y a un bon moment déjà, j’avais écrit un billet sur la mémoïsation. Si vous ne savez pas ce que c’est, je vous encourage à lire le billet. L’idée général est de stocker les résultats d’appels de fonction pour ne pas refaire plusieurs fois les mêmes calculs, ce qui se produit dans de nombreux cas de fonctions récursives.

Dans ce billet, je montrais un moyen simple d’implémenter un tel cache, à l’aide d’un décorateur. J’ignorais à ce moment que la fonctionnalité… était déjà présente dans la librairie standard de Python.

Le principe reste le même, et la doc indique que les résultats sont cachés dans un dictionnaire ayant les arguments de la fonction pour clé. Il faut donc que les arguments soient hachables, une restriction que nous avions déjà avec le décorateur maison.

Un bonus, outre les optimisations probablement présentes, c’est qu’on peut indiquer à lru_cache le nombre de résultats à cacher. En indiquant qu’il faut cacher N appels, les N appels les plus récents seulement seront conservés.

Si vous relisez l’article sur la mémoïsation, vous n’aurez pas de mal à comprendre l’exemple qui suit, exactement le même que celui que j’ai déjà donné mais avec le décorateur de la bibliothèque standard :

from functools import lru_cache

@lru_cache(128) # On ne cache que les 128 derniers appels
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

@lru_cache()   # Notez les parenthèses vides
def A(m,n):
    if m == 0:
        return n + 1
    if n == 0:
        return A(m - 1, 1)
    return A(m - 1, A(m, n - 1))

>>> fibonacci(6)
8

>>> A(2,2)
7

Rappelons le gain en vitesse :

      # Version sans la ligne lru_cache
In[1] %timeit -n 1 -r 1 fibonacci(40)
1 loop, best of 1: 47.6 s per loop

      # Version avec la ligne lru_cache
In[1] %timeit -n 1 -r 1 fibonacci(40)
1 loop, best of 1: 30 µs per loop

30 mico secondes dans un cas contre 47 secondes dans l’autre. Naturellement, vu l’arbre des appels de la fonction, cet écart se creuse encore plus, très vite.