Lisp风格的问题：memoization（小心：包含项目euler＃14的解决方案）

Question

我只是想学习一些Lisp，所以我正在经历项目euler问题。我发现问题没有。 14个有趣的（如果你打算解决这个问题，现在就停止阅读，因为我在底部粘贴了我的解决方案）。我的算法非常慢，但使用memoization（我从Paul Graham的“Lisp”书中复制了该函数）后，速度更快（大约4到8秒）。

我的问题是关于这一串警告，我得到了： 我做错了什么？我能改善我的风格吗？

> ;; 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 

这是代码：

(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))) 

非常感谢，赦免可能的错误，我只是用Lisp的开始。 Br

更新： 我想分享我写的最终代码。使用自定义外部哈希表进行记忆并改进最终循环。

(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

这是setq一个未知名称的不良风格。假定你的意思是创建一个新的全局特殊变量，然后设置它，但是应该首先引入这些绑定来明确这个变量。您可以使用defvar（或defparameter或defconstant）替代以及在词法块中使用let,do，multiple-value-bind或类似构造，在顶层执行此操作。