たまには、common lisp

2007/12/04

フィボナッチと聞くとダヴィンチコードしか思い出さないです。数学には、コンプレックスというか、嫌いというか苦手という印象しかなくて、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マクロは、自由に値を返せるので、自分で副作用のあるコードを書かなくて済むのが嬉しい。(脳内メモリが少ないので)

この記事の投稿者最新記事

しめじ(smeghead)

lisp

2件のコメント

pgf2 2007/12/09

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

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

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

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

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>> loop compound-form* => result*<br>> 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 さんの今後のエントリも楽しみにしています。

コメントする

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