3

我只是想学习一些 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))))
4

1 回答 1

1

这是setq一个不知名的名字的坏风格。假设您的意思是创建一个新的全局特殊变量，然后设置它，但这应该通过首先引入这些绑定来明确。defvar您可以通过使用(or defparameteror )在顶层执行此操作，defconstant并在词汇块中使用let,或类似结构来执行此操作。domultiple-value-bind

于 2010-08-18T20:18:35.617 回答