Lisp风格问题: memoization (caution: contains the solution for project euler #14)

Question

我只是想学习一些 Lisp，所以我正在解决项目欧拉问题。我发现问题没有。 14 个有趣的问题(所以如果你打算解决这个问题，请停止阅读，因为我把我的解决方案粘贴在了底部)。使用我的算法它是如此缓慢，但在使用记忆化之后(我从 Paul Graham 的“on 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。

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

(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 一个未知的名字是不好的风格。假定您的意思是创建一个新的全局特殊变量，然后设置它，但这应该通过首先引入这些绑定(bind)来明确说明。您可以在顶层使用 defvar(或 defparameter 或 defconstant)代替，并在词法 block 中使用 let、do、multiple-value-bind 或类似结构。