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 ?

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 !

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 !

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 !

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.