Hatena::Groupcadr

わだばLisperになる このページをアンテナに追加 RSSフィード

2004 | 12 |
2005 | 01 | 02 | 07 | 10 | 11 |
2006 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 11 |

2010-06-02

KMRCLを眺める(159) MEMO-PROC

| 07:56 | KMRCLを眺める(159) MEMO-PROC - わだばLisperになる を含むブックマーク はてなブックマーク - KMRCLを眺める(159) MEMO-PROC - わだばLisperになる

ifstar.lispの次のファイルということで、今回は、KMRCLのfunctions.lispからMEMO-PROCです。

MEMO-PROCはをメモワイズ関数化する関数です。

定義は、

(defun memo-proc (fn)
  "Memoize results of call to fn, returns a closure with hash-table"
  (let ((cache (make-hash-table :test #'equal)))
    #'(lambda (&rest args)
        (multiple-value-bind (val foundp) (gethash args cache)
          (if foundp
              val
            (setf (gethash args cache) (apply fn args)))))))

となっています。

引数とその結果が登録されたハッシュ表を引き、結果が既に登録されていれば、その値を返し、なければ計算というしくみで、割と定番かと思います。

動作は、

(DEFUN FIB (N)
  (IF (< N 2)
      N
      (+ (FIB (1- N))
         (FIB (- N 2)))))

(SETF (FDEFINITION 'FIB) ;既にあるFIBを置き換え
      (KL:MEMO-PROC #'FIB))

(FIB 100)
;⇒ 354224848179261915075

といったところ。