Comprendre la mémoïsation en 5 minutes

En dehors du titre, le générique masculin est utilisé sans aucune discrimination et uniquement dans le but d'alléger le texte.

Comprendre la mémoïsation en 5 minutes

La mémoïsation est un terme de programmation étrange et qui semble compliqué. En vrai, c’est super simple et très utile. Une fois de plus, ça tombe de temps en temps en entretien. Allez, en cinq minutes je te raconte tout ce qu’il y a savoir.



C’est quoi la mémoïsation ?

La mémoïsation est une méthode d’optimisation de code utilisée très largement quand les performances comptent vraiment. Le mot ressemble à mémorisation et ça tombe bien parce que c’est exactement le fonctionnement de cette méthode.

Tu peux déjà te mettre cette image mentale de mémorisation, car c’est en mémorisant un bout de logique que la mémoïsation optimise la performance de ton code.

Concrètement, la mémoïsation va prendre le résultat d’une fonction coûteuse et va s’en souvenir. La prochaine fois que cette fonction coûteuse va être appelée, cette méthode va répondre immédiatement par le résultat en mémoire. Et quand cette même fonction est appelée 30K secondes, ça fait vraiment la diff.

Et là, je sais ce que tu te dis. J’essaye d’embrouiller tout le monde avec des mots compliqués alors que je parle juste de cache ?



mémoïsation


Oui et non. Oui, la mémoïsation est bien une forme de caching. C’est un type bien particulier de caching qui fonctionne d’une manière et surtout dans un contexte bien différent. Le caching traditionnel va cacher une page entière ou un appel à une base de données. Mais non, car la mémoïsation s’occupe d’autre chose.

La mémoïsation va se concentrer sur le caching d’une fonction en particulier. Elle va se concentrer sur l’optimisation du temps de process de la logique de ton algorithme. Pour mieux comprendre mon discours de geek, il faut qu’on regarde comment ça fonctionne.



Comment ça marche ?

La logique pour toute mémoisation est la même. Les étapes sont les suivantes :

  • 1 : Avant la fonction, on va créer un endroit où on va stocker le résultat de la fonction

En général, il s’agit d’un hashmap. En Javascript tu as le Map et en Python on va simplement utiliser un dictionnaire.

  • 2 : Dans la fonction, on va vérifier si le résultat n’est pas déjà en mémoire

Cette vérification, ou lookup, va être peu coûteuse puisqu’on utilise un hashmap pour stocker les résultats. En effet, un lookup de O(1) est négligeable pour notre algorithme.

  • 3 : Si le résultat est en mémoire, on le retourne et on évite le process de la fonction
  • 4 : Sinon, on fait le process et on met le résultat en mémoire avant de le retourner

Et du coup t’as compris, le process ne se fait qu’une fois par fonction. Je te laisse imaginer le gain de temps sur une fonction coûteuse appelée 50K fois par seconde. Et tout ça avec une méthode easy, utilisable presque partout et super efficace !



efficace


La mémoïsation c’est aussi et surtout un compromis. Pour aller plus vite, on va stocker beaucoup d’objets dans la mémoire (dans le hashmap). On sacrifie de la place mémoire pour gagner du temps d’exécution.

Quand je t’ai parlé de la big-o notation, on a discuté seulement de la complexité en temps. La complexité en espace c’est juste l’espace mémoire qu’un algorithme va prendre pour être exécuté. On va sacrifier pour gagner de la complexité en temps.

Je commence à te connaitre, je sais que t’es pas convaincu tant que tu as pas vu du code.



Fais voir le code

Là. c’est le moment où je suis censé te montrer l’exemple Fibonacci avec de la memoïsation de récursion. On va pas faire ça pour deux raisons. D’abord je me garde l’exemple de Fibonacci pour l’article sur la récursion qui arrive. Ensuite parce qu’aujourd’hui on va rester sur du code très simple à comprendre.



Javascript (NodeJS 12.14.0)

class Memoization {
    constructor () {
        this.myHashMap = new Map()
    }

    async expensiveFunction(parameter) {
        if(this.myHashMap.has(parameter)) {
            console.log('Instant response !')
            return this.myHashMap.get(parameter)
        }
    
        console.log('First time, long process...')
        await new Promise(resolve => setTimeout(resolve, 1000))
        
        const result = `${parameter}-memoized`
    
        this.myHashMap.set(parameter, result)
    
        return result
    }

    async doStuff(){
        await this.expensiveFunction('superToto') // First time, long process...
        await this.expensiveFunction('superToto') // Instant response !
        await this.expensiveFunction('superToto') // Instant response !
        await this.expensiveFunction('superTata') // First time, long process...
        await this.expensiveFunction('superTata') // Instant response !
        await this.expensiveFunction('superToto') // Instant response !
    }
}
new Memoization().doStuff()

Test et joue avec le code en live ici ! –> https://repl.it/@jesuisundev/memoization-node



Python (3.6.9)

import time

class Memoization():
    def __init__(self):
        self.my_hash_map = {}

    def expensive_function (self, parameter):
        if parameter in self.my_hash_map:
            print('Instant response !')
            return self.my_hash_map[parameter]

        print('First time, long process...')
        time.sleep(1)

        result = '%s-memoized' % (parameter)

        self.my_hash_map[parameter] = result

        return result

    def do_stuff(self):
        self.expensive_function('superToto') # First time, long process...
        self.expensive_function('superToto') # Instant response !
        self.expensive_function('superToto') # Instant response !
        self.expensive_function('superTata') # First time, long process...
        self.expensive_function('superTata') # Instant response !
        self.expensive_function('superToto') # Instant response !

Memoization().do_stuff()

Test et joue avec le code en live ici ! –> https://repl.it/@jesuisundev/memoization-python



Comme le concept, l’implémentation est très simple !

Tout d’abord, on initialise notre hashmap ou table de hachage. C’est là qu’on va stocker le résultat des longs process donc c’est très important.

Ensuite, on créer une fonction dite coûteuse, qui est donc censée prendre du temps. La première chose qu’on fait dans cette fonction c’est de vérifier si le résultat n’a pas déjà été stocké dans notre hashmap dans le passé.

On fait notre fameux O(1) lookup et si on trouve un résultat en utilisant le paramètre de la fonction, on retourne immédiatement ! Sinon, on est forcé de faire le long process. Ici le long process est simulé avec une fonction qui va faire “dormir” le process pendant une seconde. Ensuite on stocke une variable dans le hashmap pour un futur passage.

Et voilà, il suffit d’adapter cette logique avec toutes les fonctions coûteuses de ton application et tu vas tout accélérer. Ton application va oublier ce que c’était de bosser après ça !



mémoïsation


Et tout ça c’est bien beau, mais on ne peut pas utiliser cette méthode n’importe où.



Quand utiliser la mémoïsation ?

  • Seulement dans les fonctions coûteuses qui demandent des calculs lourds

On parle pas d’appels HTTP async qui peuvent être cachés avec un système de cache plus global comme Redis. On parle de traitement qui demande énormément côté CPU. Un bon exemple d’utilisation ça serait pour éviter le traitement inutile de fonctions récursives qui augmente de façon exponentielle dans le temps.

Avec cette façon de faire, tu peux par exemple INCROYABLEMENT accélérer le traitement de la célèbre fonction Fibonacci. Je te conseille très fortement cette vidéo qui te montre clairement cet exemple-là en particulier.

  • Seulement dans les fonctions pures

Je pourrais faire un article dédié sur le sujet des fonctions pures, mais on va se contenter du concept clef. Une fonction pure c’est simplement une fonction qui, avec un paramètre donné, te répondra toujours le même résultat. Par exemple:

const pureFunction = number => number + number

console.log(pureFunction(2))
//4

Cette fonction est pure car si je passe 2, elle me répondra toujours 4. Il n’y a pas d’effet de bord ou de process aléatoire. Pour une entrée donnée, une sortie garantie.

C’est important que la fonction soit pure car le principe de la mémoïsation c’est qu’on stocke le résultat. Donc si le résultat peut changer dans le temps et qu’on fige au premier passage, ça va tout péter dans ton app !



mémoïsation


Il faut aussi savoir que dans la vraie vie, la memoïsation tu la fais rarement toi-même. Tu as des fonctions ou des librairies toutes faites pour toi. C’est TRÈS simple à mettre en place, c’est optimisé et super pratique à utiliser.

Par exemple pour refaire l’exemple plus haut en Python il suffit d’utiliser la fonction built-in et de la passer en décorateur de la fonction coûteuse !



import time
from functools import lru_cache

class Memoization():
    @lru_cache(maxsize = 1000)
    def expensive_function (self, parameter):
        print('First time, long process...')
        time.sleep(1)

        result = '%s-memoized' % (parameter)

        return result

    def do_stuff(self):
        self.expensive_function('superToto') # First time, long process...
        self.expensive_function('superToto')
        self.expensive_function('superToto')
        self.expensive_function('superTata') # First time, long process...
        self.expensive_function('superTata')
        self.expensive_function('superToto')

Memoization().do_stuff()

Test et joue avec le code en live ici ! –> https://repl.it/@jesuisundev/memoization-python-import



En Javascript tu peux faire sensiblement la même chose avec une libraire comme Lodash qui va s’occuper de tout pour toi. Plus d’excuses de ne pas l’utiliser !



Épilogue

Le sujet de la mémoïsation ouvre le sujet des algorithmes de cache qui eux-mêmes ouvrent le sujet de la programmation dynamique. T’as compris qu’on va rentrer dans ces sujets excitants dans le futur ! En attendant, tu peux impressionner un peu plus ton futur recruteur avec ta maîtrise de la mémoïsation.

Qui me parle ?

jesuisundev
Je suis un dev. En ce moment je suis Backend Développeur / DevOps à Montréal. Le dev est l'une de mes passions et j'écris comme je parle. Je continue à te parler quotidiennement sur mon Twitter. Tu peux m'insulter à cet e-mail ou le faire directement dans les commentaires juste en dessous. Y'a même une newsletter !

15 commentaires sur “Comprendre la mémoïsation en 5 minutes”

  1. Tres bon article, mais pourquoi préciser “le générique masculin” en debut de texte ? Un simple “emploi du neutre” aurait éte plus pertinent, sans ceder aux sirenes bien-pensantes de la société actuelle..

    1. Parce que le neutre n’existe pas dans la langue française, j’imagine ? À part il est vrai dans certaines écritures un peu novatrices avec du iel et autres termes. Mais il est parfaitement du droit de l’auteur de refuser d’utiliser ces termes peu familier et de s’en tenir aux genres couramment utilisés. Il aurait bien pu utiliser le féminin d’une façon générique à la place du masculin. Cependant, ce qu’on apprend à l’école, c’est d’utiliser le masculin quand on ne sait pas. Et si certes l’usage n’en a cure et utilise la règle de la majorité (par exemple, comme il y a plus d’infirmières que d’infirmiers, c’est le féminin qui est utilisé par défaut), comme il y a plus de développeurs que de développeuses, l’usage du masculin générique est plus approprié.

      Mais au fait, pourquoi ce commentaire sur un truc qui n’a rien à voir avec l’article ? Que ce soit en mode SJW (“Faut utiliser le neutre pour pas exclure les non-binaires”) ou mal-pensant (“Faut surtout pas inclure les femmes, je veux pas qu’une développeuse me donne des leçons”), ça fait juste un peu gros troll (que j’ai sûrement tort de nourrir).

  2. Cautère sur une jambe de bois, non ? Si ta fonction CPU-intensive est appelée 30k/seconde avec les mêmes arguments, ne vaut-il pas mieux passer 5 minutes à te poser la question : “Mais pourquoi ?” et corriger cette horreur plutôt que d’implémenter un tel mécanisme ?

    1. Ici c’est un exemple très (trop ?) simple, mais dans la réalité tu ne vas pas toujours appeler la fonction avec les mêmes arguments (et quand ce sera le cas tu n’auras aucun moyen de le savoir en amont).
      Il se peut que seulement 50% des appels aient déjà été faits auparavant avec les mêmes arguments par exemple.

      Pour le coup l’exemple plus parlant (et réaliste) de Fibonacci peut répondre à tes interrogations.

    2. Salut,
      L’exemple est peut être trop simple mais imagine que tu travailles sur de larges ensembles de données qui appellent régulièrement les mêmes fonctions coûteuses : tu vas te retrouver à appeler 50k fois la même fonction. Exemple pour une assurance qui recalcule tous ses contrats en fin d’année.
      En tout cas, article très intéressant !

  3. Hello,
    je rejoins Laurent Gibet dans mon questionnement (NB : je code un peu mais suis pas dév 😉 : à quoi bon mettre en place toute cette mécanique si le besoin est de calculer UNE FOIS un résultat coûteux et de le réutiliser n fois ?
    J’aurais naïvement stocké le résultat dans une variable et basta.
    Merci pour tous tes articles : j’apprends beaucoup de choses avec toi 😉

    1. C’est exactement ce qui est fait ici, on stocke le résultat dans une variable.
      L’avantage c’est que c’est la fonction en elle même qui gère ce stockage et ce rendu. A chaque fois que tu as besoin du résultat, tu n’a pas besoin de te demander “est-ce que mon résultat est dans la variable ou est-ce que je dois appeler la fonction ?”, tu appelles systématiquement la fonction et elle gère toute seule (avec l’avantage de stocker TOUS les résultats qu’on lui a déjà demandé et pas un seul comme tu pourrais le faire avec une variable).
      C’est plus générique et plus transparent. Le code appelant la fonction est simplifié, et si tu utilise les librairies existantes, même ta fonction de base n’est pas vraiment plus complexe.

  4. Connaissais pas le décorateur python… Je suppose qu’il fonctionne quels que soient le nbre et le type des arguments ?
    Car sinon c’est tout de suite plus chiant une solution de memoisation générique en multi paramètres…

  5. Merci pour cet exemple simple de mémoïsation, au moins on comprends facilement.
    Décidément cette série de comprendre un concept en 5 min est super, merci à toi.

  6. “.. En effet, un lookup de O(1) est négligeable pour notre algorithme.”
    petit détail :O(1) dit que l’opération est constante par rapport a la taille des données… Mais cela ne donne aucune information sur la durée de l’opération elle meme. On peut avoir une fonction O(1) qui prend 2hde calcul….

  7. Alors c’est un joli concept avec un bien joli mot. Mais en fait, c’est pas nouveau en vrai. Je me souviens que j’utilisais la même technique en 2007 quand j’ai démarré le développement.
    Le seul truc nouveau, c’est le mot qu’on y colle. A l’époque, on appelait ça juste du cache.

    1. Qui a dit que c’était nouveau ?
      Comme dit dans l’article, c’est une sorte de cache. Mais c’est pas tout a faire correct de l’appeler comme ça.

T'en penses quoi ?

Your email address will not be published. Required fields are marked *