Comment mémoriser une fonction récursive dans Lisp?

quelque chose comme ceci:

(setf collatz-steps (memoize lambda (n)
  (if (= 1 n) 0
    (if (evenp n) 
        (1+ (collatz-steps (/ n 2)))
        (1+ (collatz-steps (1+ (* 3 n))))))))

IOW: votre fonction originale (non-memoized) est anonyme, et vous ne donnez qu'un nom au résultat de la memoizing.

Voici une fonction de memoize qui rebinde la fonction de symbole:

(defun memoize-function (function-name)
  (setf (symbol-function function-name)
    (let ((cache (make-hash-table :test #'equal)))
         #'(lambda (&rest args)
             (multiple-value-bind 
                 (result exists)
                (gethash args cache)
               (if exists
                   result
                   (setf (gethash args cache)
                         (apply fn args)))))))

vous feriez alors quelque chose comme ceci:

(defun collatz-steps (n)
  (if (= 1 n) 0
      (if (evenp n) 
          (1+ (collatz-steps (/ n 2)))
          (1+ (collatz-steps (1+ (* 3 n)))))))

(memoize-function 'collatz-steps)

je vous laisse faire une fonction de démémoize.

Note que peu de choses:

(defun foo (bar)
   ... (foo 3) ...)

ci-Dessus est une fonction qui a un appel à elle-même.

dans Common Lisp, le compilateur de fichiers peut supposer que FOO ne change pas. Il ne sera pas appelé FOO mis à jour plus tard. Si vous changez la liaison de fonction de FOO, alors L'appel de la fonction originale ira toujours à l'ancienne fonction.

ainsi la mémorisation d'une fonction auto-récursive ne fonctionnera pas dans le cas général. Surtout pas si vous utilisez un bon compilateur.

Vous pouvez travailler autour de lui pour passer toujours par le symbole par exemple: (funcall ' foo 3)

(DEFVAR ...) est un formulaire de niveau supérieur. Ne l'utilisez pas à l'intérieur des fonctions. Si vous avez déclaré une variable, définissez-la avec SETQ ou SETF plus tard.

pour votre problème, j'utiliserais juste une table de hachage pour stocker les résultats intermédiaires.

cette fonction est exactement celle que Peter Norvig donne comme exemple d'une fonction qui semble être un bon candidat pour la memoization, mais qui ne l'est pas.

Voir la figure 3 (la fonction "Grêle") de son papier d'origine sur memoization ("à l'Aide Automatique Memoization comme un Logiciel Outil d'Ingénierie dans le Monde Réel système d'intelligence artificielle").

donc je devine, même si vous obtenez la mécanique de la memoization de travail, il ne sera pas vraiment accélérer dans ce cas.

changer la fonction" original " est nécessaire, car, comme vous le dites, il n'y a pas d'autre moyen pour que le ou les appels récursifs soient mis à jour pour appeler la version memoizée.

Heureusement, la façon lisp travaux est de trouver la fonction par le nom chaque fois qu'il faut l'appeler. Cela signifie qu'il suffit de remplacer la liaison de la fonction par la version memoized de la fonction, de sorte que les appels récursifs memoization.

le code de huaiyuan montre l'étape clé:

(setf (fdefinition 'collatz-steps) (memoize #'collatz-steps))

ce truc fonctionne aussi en Perl. Dans une langue comme C, cependant, une version memoized d'une fonction doit être codée séparément.

certaines implémentations du lisp fournissent un système appelé "advice", qui fournit une structure standardisée pour remplacer les fonctions par des versions améliorées d'elles-mêmes. En plus des mises à jour fonctionnelles Comme la memoization, cela peut être extrêmement utile dans le débogage par insertion des impressions de débogage (ou arrêt complet et obtention d'une invite continue) sans modification du code d'origine.

(define (memoize op)
  (letrec ((get (lambda (key) (list #f)))
           (set (lambda (key item)
                  (let ((old-get get))
                    (set! get (lambda (new-key)
                                (if (equal? key new-key) (cons #t item)
                                    (old-get new-key))))))))
    (lambda args
      (let ((ans (get args)))
        (if (car ans) (cdr ans)
            (let ((new-ans (apply op args)))
              (set args new-ans)
              new-ans))))))

Ce doit être utilisé comme suit:

(define fib (memoize (lambda (x)
                       (if (< x 2) x
                           (+ (fib (- x 1)) (fib (- x 2)))))))

je suis sûr que cela peut être porté à votre saveur préférée de Lisp portée lexicalement avec facilité.

je ferais probablement quelque chose comme:

(let ((memo (make-hash-table :test #'equal)))
  (defun collatz-steps (n)
    (or (gethash n memo)
    (setf (gethash n memo)
          (cond ((= n 1) 0)
            ((oddp n) (1+ (collatz-steps (+ 1 n n n))))
            (t (1+ (collatz-steps (/ n 2)))))))))

ce n'est pas agréable et fonctionnel, mais, alors, ce n'est pas beaucoup de tracas et ça fonctionne. L'inconvénient, c'est que vous n'avez pas de version non personnalisée à tester et le nettoyage du cache est à la limite de "très difficile".