La mémoïsation est une technique d'optimisation en informatique qui consiste à conserver en mémoire les résultats de l'exécution d'une fonction pour les réutiliser si la même entrée se représente. Contrairement à un recalcul coûteux, la valeur préalablement stockée est renvoyée rapidement, ce qui réduit le temps d'exécution au prix d'une utilisation supplémentaire de la mémoire. La mémoïsation s'applique surtout aux fonctions déterministes — c'est‑à‑dire qui renvoient toujours le même résultat pour les mêmes arguments — et s'intègre naturellement aux langages fonctionnels et aux algorithmes récursifs.

Principe et mise en œuvre

Au cœur de la mémoïsation se trouve une table de recherche (tableau associatif, table de hachage, map) qui associe une clé représentant les arguments de la fonction à la valeur calculée. Lorsqu'une fonction est appelée, on cherche d'abord la clé dans la table : si elle existe, la valeur mise en cache est renvoyée ; sinon la fonction est évaluée, le résultat est stocké et renvoyé. La génération de la clé nécessite parfois une normalisation des arguments (sérialisation, hachage, gestion des objets mutables).

Variantes et politiques de gestion

La mémoïsation peut être implémentée de manière simple (stockage illimité) ou associée à des politiques de gestion de cache : taille maximale, stratégie d'éviction (LRU, FIFO), durée de vie (TTL) ou nettoyage périodique. On distingue par ailleurs la mémoïsation « top‑down » (on cache les résultats au fur et à mesure des appels récursifs) de la tabulation « bottom‑up » (calculer et stocker les sous‑résultats dans un ordre non récursif) utilisée en programmation dynamique.

Histoire et terminologie

Le terme « mémoïsation » (memoization) a été popularisé à la fin des années 1960 pour décrire cette idée de « se souvenir » de résultats intermédiaires. La notion elle‑même se confond avec des concepts plus anciens de programmation dynamique et de mise en cache. Dans certains contextes, notamment en programmation logique, on emploie aussi le mot « tabulation » pour désigner des techniques proches ou complémentaires.

Exemples d'usage et importance pratique

Les cas d'application typiques incluent le calcul de suites récursives (ex. Fibonacci), les algorithmes combinatoires, l'évaluation de fonctions coûteuses (pour un même ensemble d'arguments), ou l'optimisation de parsers et d'interpréteurs. En programmation web et dans les systèmes distribués, des formes apparentées de mise en cache améliorent la latence et la charge serveur. La mémoïsation permet souvent de transformer une complexité exponentielle en polynomiale lorsque de nombreux sous‑problèmes se répètent.

Distinctions, limites et bonnes pratiques

La mémoïsation est un cas particulier de mise en cache : elle se concentre sur les résultats d'appels de fonctions. Elle n'est pas adaptée aux fonctions avec effets de bord (I/O, états globaux, date/heure) sans mécanismes de gestion explicite, car le cache rendrait des résultats obsolètes ou incorrects. Les bonnes pratiques incluent :

  • Limiter la taille du cache et choisir une politique d'éviction adaptée (LRU courant).
  • Sérialiser ou normaliser correctement les arguments pour créer des clés stables.
  • Éviter la mémoïsation d'objets mutables ou invalides sans copie ou versionnement.
  • Gérer la concurrence et la sécurité en multi‑threads (verrouillage ou structures concurrentes).
  • Mesurer l'impact mémoire et la réduction réelle du temps de calcul avant déploiement.

En résumé, la mémoïsation est une technique simple et puissante pour accélérer des calculs répétitifs lorsque les fonctions sont déterministes et que la consommation mémoire demeure acceptable. Bien utilisée, elle est un outil essentiel de l'optimisation algorithmique et du développement d'applications performantes.