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-04

KMRCLを眺める(160) MEMOIZE

| 07:55 | KMRCLを眺める(160) MEMOIZE - わだばLisperになる を含むブックマーク はてなブックマーク - KMRCLを眺める(160) MEMOIZE - わだばLisperになる

今回は、KMRCLのfunctions.lispからMEMOIZEです。

前回のMEMO-PROCを利用して既存の関数をメモ化版にするものです。

定義は、

(defun memoize (fn-name)
  (setf (fdefinition fn-name) (memo-proc (fdefinition fn-name))))

動作は、

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

;; トレース
(TRACE FIB)

(FIB 5)
0: (FIB 5)
  1: (FIB 4)
    2: (FIB 3)
      3: (FIB 2)
        4: (FIB 1)
        4: FIB returned 1
        4: (FIB 0)
        4: FIB returned 0
      3: FIB returned 1
      3: (FIB 1)
      3: FIB returned 1
    2: FIB returned 2
    2: (FIB 2)
      3: (FIB 1)
      3: FIB returned 1
      3: (FIB 0)
      3: FIB returned 0
    2: FIB returned 1
  1: FIB returned 3
  1: (FIB 3)
    2: (FIB 2)
      3: (FIB 1)
      3: FIB returned 1
      3: (FIB 0)
      3: FIB returned 0
    2: FIB returned 1
    2: (FIB 1)
    2: FIB returned 1
  1: FIB returned 2
0: FIB returned 5
;⇒ 5

;; メモ化発動
(KL:MEMOIZE 'FIB)

(FIB 5)
0: (FIB 5)
  1: (FIB 4)
    2: (FIB 3)
      3: (FIB 2)
        4: (FIB 1)
        4: FIB returned 1
        4: (FIB 0)
        4: FIB returned 0
      3: FIB returned 1
      3: (FIB 1)
      3: FIB returned 1
    2: FIB returned 2
    2: (FIB 2)
    2: FIB returned 1
  1: FIB returned 3
  1: (FIB 3)
  1: FIB returned 2
0: FIB returned 5
;⇒ 5

といったところで、FIBをメモ化すると関数の呼び出しが減るのが分かると思います。

ゲスト



トラックバック - http://cadr.g.hatena.ne.jp/g000001/20100604