Mémorisation - Memoization

Ne doit pas être confondu avec Mémorisation .
« Tabling » redirige ici. Pour la procédure parlementaire, voir Tableau (procédure parlementaire) .

Dans le calcul du , memoization ou mémoïsation est une optimisation technique utilisée principalement pour accélérer les programmes informatiques en stockant les résultats de coûteux appels de fonction et de retourner le résultat mis en cache lorsque les mêmes entrées se produisent à nouveau. La mémorisation a également été utilisée dans d'autres contextes (et à des fins autres que les gains de vitesse), comme dans une simple analyse de descente mutuellement récursive . Bien que liée à la mise en cache , la mémorisation fait référence à un cas particulier de cette optimisation, en la distinguant des formes de mise en cache telles que la mise en mémoire tampon ou le remplacement de page . Dans le cadre de certainslangages de programmation logiques , la mémorisation est également connue sous le nom de tabulation .

Étymologie

Le terme « memoization » a été inventé par Donald Michie en 1968 et est dérivé du mot latin « memorandum » (« à retenir »), généralement tronqué en « memo » en anglais américain, et porte donc le sens de « tourner [le les résultats d'une fonction en quelque chose dont on se souvient". Alors que la « mémorisation » peut être confondue avec la « mémorisation » (parce qu'ils sont étymologiques apparentés ), la « mémorisation » a un sens spécialisé en informatique.

Aperçu

Une fonction mémorisée "se souvient" des résultats correspondant à un ensemble d'entrées spécifiques. Les appels suivants avec des entrées mémorisées renvoient le résultat mémorisé plutôt que de le recalculer, éliminant ainsi le coût principal d'un appel avec des paramètres donnés de tous, sauf le premier appel effectué à la fonction avec ces paramètres. L'ensemble des associations mémorisées peut être un ensemble de taille fixe contrôlé par un algorithme de remplacement ou un ensemble fixe, selon la nature de la fonction et son utilisation. Une fonction ne peut être mémorisée que si elle est référentiellement transparente ; c'est-à-dire uniquement si l'appel de la fonction a exactement le même effet que le remplacement de cet appel de fonction par sa valeur de retour. (Cependant, il existe des exceptions de cas particuliers à cette restriction.) Bien qu'il s'agisse de tables de recherche , étant donné que la mémorisation utilise souvent de telles tables dans son implémentation, la mémorisation remplit son cache de résultats de manière transparente à la volée, selon les besoins, plutôt qu'à l'avance.

La mémorisation est un moyen de réduire le coût du temps d' une fonction en échange du coût de l' espace ; c'est-à-dire que les fonctions mémorisées sont optimisées pour la vitesse en échange d'une utilisation plus importante de l' espace mémoire de l' ordinateur . Le « coût » temps/espace des algorithmes a un nom spécifique en informatique : la complexité de calcul . Toutes les fonctions ont une complexité de calcul en temps (c'est- à - dire qu'elles prennent du temps à s'exécuter) et en espace .

Bien qu'un compromis espace-temps se produise (c'est-à-dire que l'espace utilisé est la vitesse gagnée), cela diffère de certaines autres optimisations qui impliquent un compromis espace-temps , telles que la réduction de la force , en ce que la mémorisation est un temps d' exécution plutôt que de compilation optimisation. De plus, la réduction de la force remplace potentiellement une opération coûteuse telle que la multiplication par une opération moins coûteuse telle que l'addition, et les résultats en matière d'économies peuvent être fortement dépendants de la machine (non portables entre les machines), alors que la mémorisation est une opération croisée plus indépendante de la machine. -stratégie de la plate-forme .

Considérons la fonction de pseudocode suivante pour calculer la factorielle de n : 

function factorial (n is a non-negative integer)
    if n is 0 then
        return 1 [by the convention that 0! = 1]
    else
        return factorial(n – 1) times n [recursively invoke factorial 
                                        with the parameter 1 less than n]
    end if
end function

Pour tout entier n tel que n ≥ 0, le résultat final de la fonction factorialest invariant ; s'il est invoqué en tant que x = factorial(3), le résultat est tel que x se verra toujours attribuer la valeur 6. L'implémentation non mémorisée ci-dessus, étant donné la nature de l' algorithme récursif impliqué, nécessiterait n + 1 invocations de factorialpour arriver à un résultat, et chacun des ces invocations, à leur tour, ont un coût associé dans le temps qu'il faut à la fonction pour renvoyer la valeur calculée. Selon la machine, ce coût peut être la somme de :

  1. Le coût de configuration du cadre de pile d'appels fonctionnel.
  2. Le coût pour comparer n à 0.
  3. Le coût pour soustraire 1 de n .
  4. Le coût de configuration de la trame de pile d'appels récursifs. (Comme ci-dessus.)
  5. Le coût pour multiplier le résultat de l'appel récursif à factorialpar n .
  6. Le coût de stockage du résultat de retour afin qu'il puisse être utilisé par le contexte appelant.

Dans une implémentation non mémorisée, chaque appel de niveau supérieur à factorialinclut le coût cumulé des étapes 2 à 6 proportionnel à la valeur initiale de n .

Une version mémorisée de la factorialfonction suit : 

function factorial (n is a non-negative integer)
    if n is 0 then
        return 1 [by the convention that 0! = 1]
    else if n is in lookup-table then
        return lookup-table-value-for-n
    else
        let x = factorial(n – 1) times n [recursively invoke factorial
                                         with the parameter 1 less than n]
        store x in lookup-table in the nth slot [remember the result of n! for later]
        return x
    end if
end function

Dans cet exemple particulier, si factorialest d'abord invoqué avec 5, puis invoqué plus tard avec n'importe quelle valeur inférieure ou égale à cinq, ces valeurs de retour auront également été mémorisées, puisqu'elles factorialauront été appelées de manière récursive avec les valeurs 5, 4, 3, 2, 1 et 0, et les valeurs de retour pour chacun d'entre eux auront été stockées. S'il est alors appelé avec un nombre supérieur à 5, tel que 7, seuls 2 appels récursifs seront effectués (7 et 6), et la valeur pour 5 ! aura été enregistré à partir de l'appel précédent. De cette manière, la mémorisation permet à une fonction de gagner en efficacité au fur et à mesure qu'elle est appelée, ce qui entraîne une éventuelle accélération globale.

Quelques autres considérations

Programmation fonctionnelle

Article détaillé : Thunk § Programmation fonctionnelle

La mémorisation est largement utilisée dans les compilateurs pour les langages de programmation fonctionnels , qui utilisent souvent une stratégie d'évaluation d' appel par nom . Pour éviter la surcharge lors du calcul des valeurs d'argument, les compilateurs de ces langages utilisent massivement des fonctions auxiliaires appelées thunks pour calculer les valeurs d'argument, et mémorisent ces fonctions pour éviter les calculs répétés.

Mémorisation automatique

Alors que la mémorisation peut être ajoutée aux fonctions en interne et explicitement par un programmeur informatique de la même manière que la version mémorisée ci-dessus factorialest implémentée, les fonctions référentiellement transparentes peuvent également être automatiquement mémorisées en externe . Les techniques employées par Peter Norvig ont une application non seulement dans Common Lisp (le langage dans lequel son article a démontré la mémorisation automatique), mais aussi dans divers autres langages de programmation . Les applications de la mémorisation automatique ont également été formellement explorées dans l'étude de la réécriture de termes et de l'intelligence artificielle .

Dans les langages de programmation où les fonctions sont des objets de première classe (tels que Lua , Python ou Perl ), la mémorisation automatique peut être implémentée en remplaçant (au moment de l'exécution) une fonction par sa valeur calculée une fois qu'une valeur a été calculée pour un ensemble donné de paramètres. La fonction qui effectue ce remplacement d'objet valeur pour fonction peut envelopper génériquement n'importe quelle fonction référentiellement transparente. Considérez le pseudocode suivant (où il est supposé que les fonctions sont des valeurs de première classe) : 

function memoized-call (F is a function object parameter)
    if F has no attached array values then
        allocate an associative array called values;
        attach values to F;
    end if;

    if F.values[arguments] is empty then
        F.values[arguments] = F(arguments);
    end if;

    return F.values[arguments];
end function

Afin d'appeler une version mémorisée automatiquement de l' factorialutilisation de la stratégie ci-dessus, plutôt que d'appeler factorialdirectement, le code invoque . Chacun de ces appels vérifie d'abord si un tableau de supports a été alloué pour stocker les résultats, et sinon, attache ce tableau. Si aucune entrée n'existe à la position (où sont utilisés comme clé du tableau associatif), un véritable appel est effectué avec les arguments fournis. Enfin, l'entrée dans le tableau à la position clé est renvoyée à l'appelant. memoized-call(factorial(n))values[arguments]argumentsfactorial

La stratégie ci-dessus nécessite un wrapping explicite à chaque appel à une fonction qui doit être mémorisée. Dans les langages qui autorisent les fermetures , la mémorisation peut être effectuée implicitement via une fabrique de foncteurs qui renvoie un objet fonction mémorisé enveloppé dans un motif décorateur . En pseudocode, cela peut être exprimé comme suit : 

function construct-memoized-functor (F is a function object parameter)
    allocate a function object called memoized-version;

    let memoized-version(arguments) be
        if self has no attached array values then [self is a reference to this object]
            allocate an associative array called values;
            attach values to self;
        end if;

        if self.values[arguments] is empty then
            self.values[arguments] = F(arguments);
        end if;

        return self.values[arguments];
    end let;

    return memoized-version;
end function

Plutôt que d'appeler factorial, un nouvel objet de fonction memfactest créé comme suit : 

 memfact = construct-memoized-functor(factorial)

L'exemple ci-dessus suppose que la fonction factoriala déjà été définie avant l'appel à construct-memoized-functor. À partir de ce point, est appelé chaque fois que la factorielle de n est souhaitée. Dans des langages comme le Lua, il existe des techniques plus sophistiquées qui permettent de remplacer une fonction par une nouvelle fonction du même nom, ce qui permettrait : memfact(n)

 factorial = construct-memoized-functor(factorial)

Essentiellement, ces techniques impliquent d'attacher l' objet de fonction d'origine au foncteur créé et de transférer les appels à la fonction d'origine mémorisée via un alias lorsqu'un appel à la fonction réelle est requis (pour éviter une récursion sans fin ), comme illustré ci-dessous : 

function construct-memoized-functor (F is a function object parameter)
    allocate a function object called memoized-version;

    let memoized-version(arguments) be
        if self has no attached array values then [self is a reference to this object]
            allocate an associative array called values;
            attach values to self;
            allocate a new function object called alias;
            attach alias to self; [for later ability to invoke F indirectly]
            self.alias = F;
        end if;

        if self.values[arguments] is empty then
            self.values[arguments] = self.alias(arguments); [not a direct call to F]
        end if;

        return self.values[arguments];
    end let;

    return memoized-version;
end function

(Remarque : Certaines des étapes indiquées ci-dessus peuvent être implicitement gérées par le langage d'implémentation et sont fournies à titre d'illustration.)

Analyseurs

Lorsqu'un analyseur descendant essaie d'analyser une entrée ambiguë par rapport à une grammaire sans contexte ambiguë (CFG), il peut avoir besoin d'un nombre exponentiel d'étapes (par rapport à la longueur de l'entrée) pour essayer toutes les alternatives du CFG afin de produire tous les arbres d'analyse possibles. Cela nécessiterait finalement un espace mémoire exponentiel. La mémorisation a été explorée en tant que stratégie d' analyse en 1991 par Peter Norvig, qui a démontré qu'un algorithme similaire à l'utilisation de la programmation dynamique et des ensembles d'états dans l'algorithme d'Earley (1970), et des tables dans l'algorithme CYK de Cocke, Younger et Kasami, pourrait être généré en introduisant la mémorisation automatique dans un simple analyseur de descente récursive de retour en arrière pour résoudre le problème de la complexité temporelle exponentielle. L'idée de base de l'approche de Norvig est que lorsqu'un analyseur est appliqué à l'entrée, le résultat est stocké dans un mémotable pour une réutilisation ultérieure si le même analyseur est réappliqué à la même entrée. Richard Frost a également utilisé la mémorisation pour réduire la complexité temporelle exponentielle des combinateurs d'analyseurs , qui peut être considérée comme une technique d'analyse « Purely Functional Top-Down Backtracking ». Il a montré que les combinateurs d'analyseurs de base mémorisés peuvent être utilisés comme blocs de construction pour construire des analyseurs complexes en tant que spécifications exécutables des CFG. Il a de nouveau été exploré dans le contexte de l'analyse en 1995 par Johnson et Dörre. En 2002, il a été examiné en profondeur par Ford sous la forme appelée packrat parsing .

En 2007, Frost, Hafez et Callaghan décrit un algorithme analyse de haut en bas que les utilisations memoization pour abstenant calculs redondants pour recevoir toute forme de CFG ambiguë dans polynomial temps ( Θ (n 4 ) pour gauchers récursif grammaires et Θ (n 3 ) pour grammaires non récursives à gauche). Leur algorithme d'analyse descendante nécessite également un espace polynomial pour les arbres d'analyse ambigus potentiellement exponentiels par « représentation compacte » et « regroupement d'ambiguïtés locales ». Leur représentation compacte est comparable à la représentation compacte de Tomita de l' analyse syntaxique ascendante . Leur utilisation de la mémorisation ne se limite pas seulement à récupérer les résultats précédemment calculés lorsqu'un analyseur syntaxique est appliqué à une même position d'entrée à plusieurs reprises (ce qui est essentiel pour l'exigence de temps polynomial) ; il est spécialisé pour effectuer les tâches supplémentaires suivantes :

  • Le processus de mémorisation (qui pourrait être considéré comme un " wrapper " autour de n'importe quelle exécution d'analyseur) s'adapte à une analyse récursive directe gauche en constante augmentation en imposant des restrictions de profondeur en ce qui concerne la longueur d'entrée et la position d'entrée actuelle.
  • La procédure de « recherche » de la table de mémo de l'algorithme détermine également la réutilisation d'un résultat enregistré en comparant le contexte de calcul du résultat enregistré avec le contexte actuel de l'analyseur. Cette comparaison contextuelle est la clé pour s'adapter à la récursivité à gauche indirecte (ou cachée) .
  • Lors d'une recherche réussie dans un élément mémorisable, au lieu de renvoyer l'ensemble de résultats complet, le processus ne renvoie que les références du résultat réel et accélère finalement le calcul global.
  • Lors de la mise à jour du mémotable, le processus de mémorisation regroupe les résultats ambigus (potentiellement exponentiels) et assure l'encombrement polynomial.

Frost, Hafiz et Callaghan ont également décrit l'implémentation de l'algorithme dans PADL'08 comme un ensemble de fonctions d'ordre supérieur (appelées combinateurs d'analyseurs ) dans Haskell , qui permet la construction de spécifications directement exécutables de CFG en tant que processeurs de langage. L'importance de la capacité de leur algorithme polynomial à s'adapter à «toute forme de CFG ambigu» avec une analyse descendante est vitale en ce qui concerne l'analyse syntaxique et sémantique lors du traitement du langage naturel . Le site X-SAIGA a plus d'informations sur l'algorithme et les détails de mise en œuvre.

Alors que Norvig augmentait la puissance de l'analyseur grâce à la mémorisation, l'analyseur augmenté était toujours aussi complexe dans le temps que l'algorithme d'Earley, ce qui démontre un cas d'utilisation de la mémorisation pour autre chose que l'optimisation de la vitesse. Johnson et Dörre démontrent une autre application de la mémorisation non liée à la vitesse : l'utilisation de la mémorisation pour retarder la résolution des contraintes linguistiques jusqu'à un point dans une analyse où suffisamment d'informations ont été accumulées pour résoudre ces contraintes. En revanche, dans l'application d'optimisation de la vitesse de la mémorisation, Ford a démontré que la mémorisation pouvait garantir que les grammaires d'expression d'analyse pouvaient analyser en temps linéaire même les langues qui entraînaient un comportement de retour en arrière dans le pire des cas.

Considérez la grammaire suivante : 

S → (A c) | (B d)
A → X (a|b)
B → X b
X → x [X]

(Note de notation : dans l'exemple ci-dessus, la production S → (A c ) | (B d ) s'écrit : " Un S est soit un A suivi d'un c ou un B suivi d'un d ." La production X → x [ X] lit "Un X est un x suivi d'un X facultatif .")

Cette grammaire génère l' une des trois variantes de suivantes chaîne : XAC , XBC ou XBD (où x ici , on entend une ou plusieurs x « s .) Ensuite, examiner comment cette grammaire, utilisé comme une spécification d'analyse syntaxique, l' effet pourrait un analyse descendante, gauche-droite de la chaîne xxxxxbd :

La règle A reconnaîtra xxxxxb (en descendant d'abord dans X pour reconnaître un x , puis de nouveau dans X jusqu'à ce que tous les x soient consommés, puis en reconnaissant le b ), puis reviendra à S , et ne parviendra pas à reconnaître un c . La clause suivante de S descendra alors dans B, qui à son tour redescend dans X et reconnaît les x au moyen de nombreux appels récursifs à X , puis à a b , et revient à S et reconnaît finalement a d .

Le concept clé ici est inhérent à la phrase descend à nouveau dans X . Le processus consistant à regarder vers l'avant, à échouer, à sauvegarder, puis à réessayer l'alternative suivante est connu dans l'analyse sous le nom de retour en arrière, et c'est principalement le retour en arrière qui présente des opportunités de mémorisation dans l'analyse. Considérons une fonction RuleAcceptsSomeInput(Rule, Position, Input), où les paramètres sont les suivants :

  • Rule est le nom de la règle considérée.
  • Position est le décalage actuellement considéré dans l'entrée.
  • Input est l'entrée considérée.

Laissez la valeur de retour de la fonction RuleAcceptsSomeInputêtre la longueur de l'entrée acceptée par Rule, ou 0 si cette règle n'accepte aucune entrée à ce décalage dans la chaîne. Dans un scénario de retour en arrière avec une telle mémorisation, le processus d'analyse est le suivant :

Lorsque la règle A descend dans X au décalage 0, elle mémorise la longueur 5 contre cette position et la règle X . Après avoir échoué à d , B alors, plutôt que de redescendre en X , interroge la position 0 par rapport à la règle X dans le moteur de mémorisation, et est renvoyé une longueur de 5, évitant ainsi d'avoir à redescendre en X , et continue comme s'il était descendu en X autant de fois qu'avant.

Dans l'exemple ci-dessus, une ou plusieurs descentes dans X peuvent se produire, permettant des chaînes telles que xxxxxxxxxxxxxxxxbd . En fait, il peut y avoir n'importe quel nombre de x avant le b . Alors que l'appel à S doit descendre récursivement dans X autant de fois qu'il y a de x , B n'aura jamais à descendre du tout dans X, puisque la valeur de retour de sera 16 (dans ce cas particulier). RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd)

Les analyseurs syntaxiques qui utilisent des prédicats syntaxiques sont également capables de mémoriser les résultats des analyses de prédicats, réduisant ainsi des constructions telles que : 

S → (A)? A
A → /* some rule */

à une descente dans A .

Si un analyseur construit un arbre d'analyse au cours d'une analyse, il doit mémoriser non seulement la longueur de l'entrée qui correspond à un décalage par rapport à une règle donnée, mais doit également stocker le sous-arbre généré par cette règle à ce décalage dans le entrée, car les appels ultérieurs à la règle par l'analyseur ne descendront pas et ne reconstruiront pas réellement cet arbre. Pour la même raison, les algorithmes d'analyseur mémorisé qui génèrent des appels à du code externe (parfois appelé routine d'action sémantique ) lorsqu'une règle correspond doivent utiliser un schéma pour s'assurer que ces règles sont invoquées dans un ordre prévisible.

Étant donné que, pour tout analyseur capable de revenir en arrière ou de prédicat syntaxique, toutes les grammaires n'auront pas besoin d'un retour en arrière ou de vérifications de prédicat, la surcharge de stockage des résultats d'analyse de chaque règle par rapport à chaque décalage dans l'entrée (et le stockage de l'arbre d'analyse si le processus d'analyse le fait implicitement) peut ralentir réellement un analyseur. Cet effet peut être atténué par une sélection explicite des règles que l'analyseur va mémoriser.

Voir également

Les références

Liens externes

Exemples de mémorisation dans divers langages de programmation