Techniques de mémoïsation

Les exercices de cette section traitent, pour beaucoup, de la mémoïsation.

Ils sont présentés volontairement avec le code très simple de structure suivante.

Code très simple

🐍 Script Python

# support de mémoïsation (liste ou dictionnaire)
mon_objet = ...

def ma_question(n):
    # Fonction à effet de bord /!\
    # qui modifie mon_objet si besoin
    return mon_objet[n]

# Utilisation
ma_question(10)

Mais les fonctions à effets de bords peuvent être source de difficultés d'analyse et considérées comme une mauvaise pratique. On construira donc ensuite une version plus rigoureuse et élégante.

Pour des raisons pédagogiques, on gardera cette présentation simple pour les exercices.

Pour passer en production, il y a plusieurs possibilités.

Sans effet de bord

🐍 Script Python

# support de mémoïsation (liste ou dictionnaire)
mon_objet = ...

def ma_question(n, mon_objet):
    # Fonction à effet de bord /!\
    # qui modifie mon_objet si besoin
    return mon_objet[n]

# Utilisation
ma_question(10, mon_objet)

L'utilisation est plus lourde. On voudrais rendre mon_objet plus transparent.

Avec paramètre par défaut

🐍 Script Python

# support de mémoïsation (liste ou dictionnaire)
mon_objet = ...

def ma_question(n, mon_objet=mon_objet):
    # Fonction à effet de bord /!\
    # qui modifie mon_objet si besoin
    return mon_objet[n]

# Utilisation
ma_question(10)

L'utilisation est de nouveau légère. De plus, il y a un petit gain de performance ; la portée de la variable mon_objet devient locale dans ma_question.

Utiliser un paramètre par défaut mutable est une mauvaise pratique.

Cette solution ne résout pas le problème de fond : il y a effet de bord ! En revanche, elle l'exhibe un peu !

Un peu de POO

Technique hors programme en NSI.

🐍 Script Python

class MaQuestion:
    def __init__(self):
        # support de mémoïsation (liste ou dictionnaire)
        self.mon_objet = ...

    def __call__(self, n):
        # on modifie self.mon_objet si besoin
        return self.mon_objet[n]

ma_question = MaQuestion()


# Utilisation
ma_question(10)

Explication

ma_question(10) fait appel à la méthode __call__ de la classe MaQuestion, celle-ci utilise self.mon_objet de l'instance ma_question.

Ici, plus d'effet de bord, et l'utilisation reste légère.

On peut gérer finement les règles de mémoïsation (on fait le ménage quand on veut, on ne sauvegarde que ce qu'on veut, ...)

C'est juste à peine peu plus lourd à écrire.

Solution intégrée

Pour une fonction récursive qui appelle souvent les mêmes résultats intermédiaires :

🐍 Script Python

import functools

@functools.cache
def ma_question(n):
    # Cette fonction récursive devient efficace
    return ...

# Utilisation
ma_question(10)

C'est très simple à mettre en œuvre.

Le cache est automatiquement utilisé pour répondre à un appel, si l'entrée a déjà été vu.

On n'a aucun contrôle sur la gestion de la mémoïsation.