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或類似構造，在頂層執行此操作。