Question de style Lisp: memoization (attention: contient la solution pour le projet euler # 14)

Question

J'essaie juste d'apprendre un peu de Lisp, donc je suis en train de vivre des problèmes avec le projet euler. J'ai trouvé le problème non. 14 intéressant (donc si vous envisagez de résoudre ce problème arrêtez de lire maintenant, parce que j'ai collé ma solution en bas). Avec mon algorithme, c'était tellement lent, mais après avoir utilisé la mémo (j'ai copié la fonction du livre "sur Lisp" de Paul Graham) c'était beaucoup plus rapide (environ 4 à 8 secondes).

Ma question concerne les avertissements que j'ai reçus: Est-ce que je fais quelque chose de mal? Puis-je améliorer mon style?

> ;; Loading file 
> /euler-lisp/euler-14.lisp 
> ... WARNING in COLLATZ-SERIE : 
> COLLATZ-SERIE-M is neither declared 
> nor bound, it will be treated as if it 
> were declared SPECIAL. WARNING in 
> COLLATZ-SERIE : COLLATZ-SERIE-M is 
> neither declared nor bound, it will be 
> treated as if it were declared 
> SPECIAL. WARNING in COMPILED-FORM-314 
> : COLLATZ-SERIE-M is neither declared 
> nor bound, it will be treated as if it 
> were declared SPECIAL. (525 837799) 
> Real time: 18.821894 sec. Run time: 
> 18.029127 sec. Space: 219883968 Bytes GC: 35, GC time: 4.080254 sec. Las 
> siguientes variables especiales no han 
> sido definidas: COLLATZ-SERIE-M 0 
> errores, 0 advertencias ;; Loaded file 

Voici le code:

(defun collatz (n) 
     (if (evenp n) (/ n 2) (+ (* 3 n) 1))) 

    (defun memoize (fn) 
     (let ((cache (make-hash-table :test #'equal))) 
     #'(lambda (&rest args) 
      (multiple-value-bind (val win) (gethash args cache) 
       (if win 
        val 
       (setf (gethash args cache) 
         (apply fn args))))))) 

    (defun collatz-serie (n) 
     (cond ((= n 1) (list 1)) 
     ((evenp n) (cons n (funcall collatz-serie-m (/ n 2)))) 
     (t (cons n (funcall collatz-serie-m (+ (* 3 n) 1)))))) 

    (defun collatz-serie-len (n) 
     (length (collatz-serie n))) 

    (setq collatz-serie-m (memoize #'collatz-serie)) 

    (defun gen-series-pairs (n) 
     (loop for i from 1 to n collect 
      (list (collatz-serie-len i) i))) 

    (defun euler-14 (&key (n 1000000)) 
     (car (sort (gen-series-pairs n) #'(lambda (x y) (> (car x) (car y)))))) 

    (time (print (euler-14))) 

Merci beaucoup, et remettrez les erreurs probables, je commence juste avec Lisp. Br

MISE À JOUR: je veux partager le code final que je l'ai écrit. en utilisant une table de hachage externe personnalisée pour la mémoisation et en améliorant la boucle finale.

(defvar *cache* (make-hash-table :test #'equal)) 

(defun collatz (n) 
     (if (evenp n) (/ n 2) (+ (* 3 n) 1))) 

(defun collatz-serie (n) 
    (cond ((= n 1) (list 1)) 
    ((evenp n) (cons n (collatz-serie (/ n 2)))) 
    (t (cons n (collatz-serie (+ (* 3 n) 1)))))) 

(defun collatz-serie-new (n) 
    (labels ((helper (n len) 
      (multiple-value-bind (val stored?) (gethash n *cache*) 
       (if stored? 
        val 
       (setf (gethash n *cache*) (cond ((= n 1) len) 
               ((evenp n) (+ len (helper (/ n 2) len))) 
               (t (+ len (helper (+ (* 3 n) 1) len))))))))) 
    (helper n 1))) 

;; learning how to loop 
(defun euler-14 (&key (n 1000000)) 
    (loop with max = 0 and pos = 0 
     for i from n downto 1 
     when (> (collatz-serie-new i) max) 
     do (setf max (collatz-serie-new i)) and do (setf pos i) 
     finally (return (list max pos)))) 

Answer 1

Il est mauvais style à setq un nom inconnu. Il est supposé que vous voulez créer une nouvelle variable spéciale globale, puis la définir, mais cela doit être rendu explicite en introduisant ces liaisons en premier. Vous faites cela au niveau supérieur en utilisant defvar (ou defparameter ou defconstant) à la place, et dans les blocs lexicaux en utilisant let, do, multiple-value-bind ou des constructions similaires.