Est-ce considéré comme une mémoisation?

En optimisant du code récemment, nous avons fini par effectuer ce que je pense être un "type" de mémoiation mais je ne suis pas sûr que nous devrions l'appeler ainsi. Le pseudo-code ci-dessous n'est pas l'algorithme réel (puisque nous avons peu besoin de factoriels dans notre application, et l'affichage de ce code est une infraction de tir) mais cela devrait être suffisant pour expliquer ma question. Ce fut l'original:Est-ce considéré comme une mémoisation?

def factorial (n): 
    if n == 1 return 1 
    return n * factorial (n-1)

assez simple, mais nous avons ajouté des points fixes de sorte qu'un grand nombre de calculs pourraient être évités pour un plus grand nombre, quelque chose comme:

def factorial (n): 
    if n == 1 return 1 
    if n == 10 return 3628800 
    if n == 20 return 2432902008176640000 
    if n == 30 return 265252859812191058636308480000000 
    if n == 40 return 815915283247897734345611269596115894272000000000 
    # And so on. 

    return n * factorial (n-1)

Ceci, bien sûr, signifiait que 12! a été calculé comme 12 * 11 * 3628800 plutôt que le moins efficace 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1.

Mais je me demande si nous devrions inviterons cette mémoïsation puisque cela semble être définie comme souvenir résultats passés de calculs et de les utiliser. C'est plus sur les calculs codés en dur (ne pas se souvenir) et en utilisant cette information. Y a-t-il un nom propre à ce processus ou pouvons-nous affirmer que la memoisation ne s'applique pas seulement aux calculs effectués à l'exécution, mais aussi à ceux de la compilation et même à ceux effectués dans ma tête avant même de commencer écrire le code?

Source

2011-03-22 paxdiablo

Oui. C'est une sorte de mémo. Que devez-vous savoir de plus? –

_C'est ce que j'ai besoin de savoir. Cela ne colle pas avec l'article de Wikipédia qui stipule spécifiquement: 'Une fonction mémoisée 'se souvient' des résultats correspondant à un ensemble d'entrées spécifiques. Les appels subséquents avec des entrées mémorisées renvoient le résultat mémorisé plutôt que de le recalculer, ... '. Je pensais qu'il pourrait y avoir un terme différent pour le cas où il ne se souvient pas, mais à la place il a codé en dur. – paxdiablo

Bon, j'ai deux réponses à ce jour, oui et non. Cela signifie que des références aux sources d'autorité vont probablement être nécessaires. Je vais laisser la question pendant quelques heures et voir ce qui entre. – paxdiablo

Je l'appelle pré-calcul plutôt que memoization. Vous ne vous souvenez pas vraiment des calculs que vous avez effectués dans le processus de calcul d'une réponse finale pour un intrant donné, mais vous précalculez un nombre fixe de réponses pour des intrants spécifiques. Memoization comme je le comprends est vraiment plus proche de "mise en cache" d'un ensemble de résultats que vous les calculez pour une réutilisation ultérieure. Si vous deviez stocker chaque valeur calculée de sorte que vous n'ayez pas besoin de la recalculer plus tard, ce serait la mémo.Votre solution diffère en ce que vous ne stockez jamais de résultats "calculés" de votre programme, seulement les points fixes qui ont été pré-calculés. Avec la mémoisation, si vous réexécutez la fonction avec une entrée différente de l'une des valeurs précalculées, il ne sera pas nécessaire de recalculer le résultat, mais simplement de le réutiliser.

Source

2011-03-22 03:09:31 tvanfosson

Que vous codiez ou non les résultats, il s'agit toujours de mémo, car vous avez déjà calculé les résultats que vous prévoyez de calculer à nouveau. Maintenant, cela peut venir sous la forme d'exécution, ou de temps de compilation .. mais de toute façon, c'est mémoization.

Source

2011-03-22 03:04:34

La mémorisation est effectuée au moment de l'exécution. Vous optimisez au moment de la compilation. Donc, ça ne l'est pas.

Voir par exemple ... Wikipedia

Ou ...

Memoization Le terme memoization a été inventé par Donald Michie (1968) pour désigner le processus par lequel une fonction est fait à automatiquement rappeler les résultats des calculs précédents. L'idée est devenue plus populaire ces dernières années avec la montée des langages fonctionnels; Field et Harrison (1988) y consacrent un chapitre entier. L'idée de base est simplement de conserver une table de paires d'entrées/résultats précédemment calculées.

Peter Norvig Université de Californie (le gras est le mien)

Link

Source

2011-03-22 03:06:09

Quand est-ce mystérieux "temps d'exécution"? Puis-je mettre en cache les résultats des précédentes exécutions dans un stockage persistant? Si oui, puis-je mettre en cache les résultats des exécutions précédentes dans le code exécutable lui-même? Si oui, puis-je mettre en cache les résultats d'exécutions précédentes dans le code source? Je ne vois pas pourquoi il y a une ligne aléatoire excluant "mettre en cache les résultats précédents dans le code source". –

@ S.Lott Comme toujours, les mots ne sont que des mots, et une définition est toujours répréhensible. Je pense que le concept utilisé par l'OP diverge de la définition habituelle de mémoisation parce que 1) Il est forcé de modifier la fonction pour stocker de nouveaux/autres résultats et 2) Dans le sens habituel "une fonction est faite pour mémoriser automatiquement les résultats des calculs précédents "sans intervention humaine (d'où le _automatically_). Personne ne mourra s'il n'y a pas d'accord sur une telle chose. –

@belisarius: Donc, le moyen de passer le test de mémoization serait d'avoir la fonction réécrire son propre code source? –

Est-ce considéré comme une mémoisation?

Répondre

Questions connexes