CommonLispでフィボナッチ数列を書く
- May 29, 2019
- Lisp
GWの前半は「プログラミングコンテストチャレンジブック」に捧げたのでその時の知見をブログにまとめていこうと思う。
「フィボナッチ数列」とは,「前の2つの数を加えると次の数になる」という数列.
コードは以下:
(defun memo (fn)
(let ((table (make-hash-table :test 'equal)))
#'(lambda (&rest rest)
(multiple-value-bind (val found-p) (gethash rest table)
(if found-p
val
(setf (gethash rest table) (apply fn rest)))))))
(defun memoize (fn-name)
(setf (symbol-function fn-name) (memo (symbol-function fn-name))))
(defmacro defun-memo (fn args &body body)
`(memoize (defun ,fn ,args . ,body)))
(defun fib (n)
(if (<= n 1) 1
(+ (fib (- n 1)) (fib (- n 2)))))
(defun-memo fib-memo (n)
(if (<= n 1) 1
(+ (fib-memo (- n 1)) (fib-memo (- n 2)))))
パフォーマンス:
CL-USER> (time (fib 40))
Evaluation took:
2.449 seconds of real time
2.448322 seconds of total run time (2.448322 user, 0.000000 system)
99.96% CPU
4,406,984,086 processor cycles
0 bytes consed
CL-USER> (time (fib-memo 40))
Evaluation took:
0.000 seconds of real time
0.000045 seconds of total run time (0.000045 user, 0.000000 system)
100.00% CPU
73,547 processor cycles
0 bytes consed
メモ化をすることによって高速化できるというのはよくある方法なのだが、 defmacro
で書くとめちゃくちゃスッキリ書くことが出来る.
上記のmemo関数を可変長引数に対応させるのには骨が折れたが、以下のツイートのおかげで実装することが出来た。
いま手元に処理系ないんで未確認ですけど (make-hash-table :test 'equal) にしたら所望の動作になりませんか
— Kiyoshi Mizumaru (@kmizumar) April 27, 2019
取れました!!!
— たけてぃ (@takeokunn) April 27, 2019
なるほど、デフォルトはeqlだったから取れなかったっぽいです
test---a designator for one of the functions eq, eql, equal, or equalp. The default is eql.https://t.co/LAaUWAj3ir