CommonLispでフィボナッチ数列を書く

GWの前半は「プログラミングコンテストチャレンジブック」に捧げたのでその時の知見をブログにまとめていこうと思う。

「フィボナッチ数列」とは，「前の２つの数を加えると次の数になる」という数列.

コードは以下:

(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関数を可変長引数に対応させるのには骨が折れたが、以下のツイートのおかげで実装することが出来た。