たまには、common lisp

フィボナッチと聞くとダヴィンチコードしか思い出さないです。数学には、コンプレックスというか、嫌いというか苦手という印象しかなくて、SICPも買ってはみたものの、序章で挫折している状況です。

http://d.hatena.ne.jp/pgf2/20071204/1196737473 (こちらでは、pgf2さんでよいんでしょうか?)

pgf2さんのところで、フィボナッチ数列の関数が書かれていたので、メモ化してみました。

(let ((answer-table (make-hash-table)))
(setf (gethash 1 answer-table) 1
(gethash 2 answer-table) 1)
(defun fib (n)
(or (plusp n) (error :invalid-arg))
(or (gethash n answer-table)
(setf (gethash n answer-table)
(+ (fib (1- n)) (fib (- n 2)))))))
(print (loop for i from 1 to 10 collect (fib i)))
;(do ((i 1 (1+ i))) ; xyzzy
;  ((> i 10))
;  (format t "~d~%" (fib i)))

lispを始めたころは、拡張loopマクロ嫌いだったんですが、今は大好きです。拡張loopマクロは、自由に値を返せるので、自分で副作用のあるコードを書かなくて済むのが嬉しい。(脳内メモリが少ないので)

2件のコメント

  • トラバありがとうございますー。

    ダヴィンチコードにフィボナッチが出てくるんですね。
    頁が多すぎてスルーしてたんですが、フィボナッチが絡んでるなら読んでみようと思います。
    (本はそんなに評価が悪くなかった気がするので…)

    フィボナッチ数列は再帰使うとやはり遅くなりますね…。
    関数内で同じ関数を2度呼び出しているので、アルゴリズム上仕方ないと言えばそれまでですが。

    まだ、拡張loopマクロとかわからないレベルですが、読んでくださってありがとうございます。
    数学とアルゴリズム関係はpgf2とか使ってますが、お好きな方でお願いします(笑)

  • pgf2さん、コメントありがとうございます。
    ダヴィンチコードは、DVDで見ただけです。。フィボナッチ数列がちょこっと出てくるだけなのです。数学的なつっこんだ話までは出てこなかったと思います。

    拡張loopマクロというか、Common Lispの仕様(HyperSpec)では、「Theextended’’ loop form:」というのがあって非常に便利なんですが、xyzzyでは、「Thesimple’’ loop form」しか使えなかったと思います。
    http://www.lisp.org/HyperSpec/Body/mac_loop.html
    > Syntax:
    > The simple’’ loop form:<br>&gt; loop compound-form* =&gt; result*<br>&gt; Theextended’’ loop form:
    > loop [name-clause] {variable-clause}* {main-clause}* => result*
    ↓は、非常に詳しい解説があります。
    http://smpl.seesaa.net/article/29800843.html
    「The “extended’’ loop form」のために、別の処理系をインストールするというのもありかもしれませんね。

    私にとって、lispは良い玩具でした。道具と呼べる程使いこなせていない(汗)という意味でも、そうなのですが。数学という観点からのlispというpgf2 さんの今後のエントリも楽しみにしています。

コメントする

メールアドレスが公開されることはありません。 が付いている欄は必須項目です


The reCAPTCHA verification period has expired. Please reload the page.

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください