3

私はLispを学ぼうとしているだけなので、プロジェクトオイラーの問題を経験しています。問題はありませんでした。14興味深い（この問題を解決することを計画している場合は、解決策を下部に貼り付けたので、今すぐ読むのをやめてください）。私のアルゴリズムでは非常に低速でしたが、メモ化を使用した後（Paul Grahamの「onLisp」の本から関数をコピーしました）、はるかに高速でした（約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))))
4

1 に答える 1

1

setq知らない名前には悪いスタイルです。新しいグローバル特殊変数を作成してから設定することを想定していますが、最初にこれらのバインディングを導入することにより、これを明示的にする必要があります。これをトップレベルで行うには、代わりにdefvar（またはdefparameterまたは）を使用し、字句ブロックでは、、、または同様の構成を使用します。defconstantletdomultiple-value-bind

于 2010-08-18T20:18:35.617 に答える