memoization

Une définition du Jargon Français.
Aller à : Navigation, rechercher

Dr enus.png nom féminin.  [cache]  [algorithmie]. Fait de frontaliser une fonction au moyen d'une logique servant de cache.

C'est particulièrement utile dans le cas d'une fonction récursive et pure.

Certains langages de programmation assurent cela automatiquement au prix d'une simple déclaration.

Voir aussi tabulation (sens 2)

Exemple

En Perl:

# variable tableau qui contiendra le cache
# de la fonction "factorial"
my @cache_fact;
 
sub factorielle {  # déclaration de la fonction
 my $n = shift;    # argument passé à la fonction
 
# si le cache contient la valeur retournée
# par cette fonction pour cet argument, alors
# on retourne immédiatement cette valeur 
 return $cache_fact[$n] if defined $cache_fact[$n];
 
 my $result;
# calcul du résultat, par récursivité
 if ($n == 0) { $resultat = 1 }
  else { $resultat = $n * factorielle($n-1) }
 
# on place le résultat dans le cache
 $cache_fact[$n] = $resultat;
 
 return $resultat;
 }