#:g1: memoizeの紹介

Posted 2014-02-12 15:00:00 GMT

(LISP Library 365参加エントリ)

 LISP Library 365 の44日目です。

memoizeとはなにか

 memoizeはTim Bradshaw氏作のメモ化関数のライブラリです。

パッケージ情報

パッケージ名memoize
Quicklisp
ドキュメントLisp hacks
CLiKihttp://cliki.net/memoize
Quickdocshttp://quickdocs.org/memoize

インストール方法

(ql:quickload :memoize)

試してみる

 どんな関数があるかは、Quickdocsで確認できます。

 defunと同じ使い勝手のdef-memoized-functionを主としてユーティリティが揃えられています。
CLikiの紹介によれば、fare-memoizationを使え、とありますが、メンテナンスされてないからでしょうか。
なお、ドキュメントによれば、スレッドセーフではないとのこと。

def-memoized-function

 メモ化関数を定義

(org.tfeb.hax.memoize:def-memoized-function fib (n)
  (if (< n 2)
      n
      (+ (fib (1- n))
         (fib (- n 2)))))

(fib 100) ;=> 354224848179261915075

memoized-labels
(defun fib (n)
  (org.tfeb.hax.memoize:memoized-labels ((fib (n)
                                           (if (< n 2)
                                               n
                                               (+ (fib (1- n))
                                                  (fib (- n 2))))))
    (fib n)))

(fib 100) ;=> 354224848179261915075

(setf (fdefinition 'fib) (org.tfeb.hax.memoize:memoized-labels ((fib (n) (if (< n 2) n (+ (fib (1- n)) (fib (- n 2)))))) #'fib))

(fib 100) ;=> 354224848179261915075

 その名の通りメモ化関数のローカル関数版
その他、

まとめ

 今回は、memoizeを紹介してみました。
Quicklispには他にも3つ4つのメモ化ユーティリティがあるようですが、謎の人気ですね。

comments powered by Disqus