Gauche:メモ化

Gauche:Memoizeに移行しました。

yamasushi(2013/04/10 00:21:29 UTC)メモ化のための小物をまとめてみます。
yamasushi(2013/04/13 11:34:10 UTC) Gauche:マニュアルにアクセスで使用しています。
yamasushi(2013/04/16 10:46:28 UTC)Gauche:マニュアルにアクセスで使っていたのですが、instance-poolでやったほうが簡単でした。(→Gauche:infoファイルにアクセス)
yamasushi(2013/05/01 00:52:10 UTC)Gauche:メモ化から移行しました。

; info-file <string> ---> info <info-file>
; infoをたびたび開くのを抑止してメモ化
(define info-node-open-file
  (make-memoized (make-hash-table 'string=?) ($ open-info-file $ find-info-file $) ) )

; info node-name ---> [node info-index] or #f
(define-method %info-node-get-index% ( (info <info-file>) node-name )
  (and-let* [ [_ (string? node-name) ]
              [_ info  ]
              [node (info-get-node info node-name)] ]
    (let1 info-index (make-tree-map string=? string<?)
      (for-each
        (match-lambda
          [ (keyword . nodename)
          
          ....
          
        (info-parse-menu node) )
      (list node info-index)
      ) ) )
; メモ化
(define info-node-get-index
  (make-memoized
    (make-hash-table 'string=?)
    %info-node-get-index%
    (^(info node-name) (string-append (ref info 'path) node-name )) ) )

メモ化についての資料

• cut-sea:log

  memoize

  こんなんもありかなぁ。 (define foo ... で定義しておいて、あとからメモ化したいなぁって関数だけ memoize-define に差し替えるとか。cut-sea:2004/12/02 03:49:57 PST

  (define-syntax memoize-define
    (syntax-rules ()
      ((_ (fn . arg) body ...)
       (memoize-define fn (lambda arg body ...)))
      ((_ fn lambda-body)
       (define fn (let ((cache (make-hash-table 'equal?))
                        (rawfn lambda-body))
                    (lambda args
                      (if (hash-table-exists? cache args)
                          (hash-table-get cache args)
                          (let ((val (apply rawfn args)))
                            (hash-table-put! cache args val)
                            val))))))))
  

• Scheme:OnLisp
  • 5.3 関数の値のメモワイズ

    (define (memoize fn)
      (let ((cache (make-hash-table 'equal?)))
        (lambda args
          (if (hash-table-exists? cache args)
              (hash-table-get cache args)
              (let ((val (apply fn args)))
                (hash-table-put! cache args val)
                val)))))
    

• GaucheDevelML:29769162 memoize from karme

  is there a "standard" memoize?

  • GaucheDevelML:29772717 Re: memoize from Shiro Kawai(Shiro)

    No, we don't have standard memoize.
    

    Simple memoization is easy to write up. The problem is that some applications aren't ok with the simple one: One obvious problem is that the simple one retains reference to all the arguments ever passed to the procedure, causing memory problem; also, the one you found doesn't support multiple return values, etc.
    

    So, I think it's easier to write up one every time I need some memoization, whenever the simple one satisfies it.
    

  • GaucheDevelML:29772755 Re: memoize from Alex Shinn(foof)

    As Shiro says there are many issues with memoization that make a general purpose definition difficult, but it is useful enough that the R7RS large language will provide a general memoization library.

• SynthCode:memoize.scm? @ Alex Shinn(foof)'s synthcode.com

  Automatically memoize procedures, including utilities for saving to files.

• WikipediaJa:メモ化
• WikipediaEn:Memoization
• Memoizing functions
  http://www.tfeb.org/lisp/hax.html#MEMOIZE
  

関連

• GaucheRefj:object-hash
  

  Generic Function: object-hash obj
  この総称関数に対するメソッドを定義することにより、ユーザ定義された 型のオブジェクトはハッシュ値を持つことができ、equal?型のハッシュ テーブルで利用することができるようになります。
  

  メソッドは正確な非負整数を返さなければなりません。また、hash と 同じ制約に従わなければなりません。
  

  メソッドが obj の要素のハッシュ値を必要とする場合には、 それらに対しては、object-hash ではなく、hash を 呼ばなければなりません。プリミティブなオブジェクトのハッシュ計算は hash が行うからです。
  

• GaucheRefj:等価
  

  Function: equal? obj1 obj2
  [R5RS+] obj1とobj2がリストやベクタなどの複合型である場合、 equal?は再帰的に対応する要素同士をequal?で比較してゆきます。
  そうでなければ、equal?はeqv?と同じようにふるまいます。

  もしobj1とobj2が論理値、数値、文字、ペア、文字列、 ベクタのいずれでもなく、かつ両者のクラスが等しい場合、equal?は ジェネリックファンクションobject-equal?を呼びます。 object-equal?にメソッドを定義することにより、 ユーザ定義のデータ型に対するequal?の振るまいを拡張することができます。

  Generic Function: object-equal? obj1 obj2
  equal?が未知のオブジェクトに対して呼ばれた場合、 このジェネリックファンクションが呼ばれます。自分で定義したクラスに対して このメソッドを定義することにより、equal?で等価判定が行えるようになります。
  

  メソッドは、obj1とobj2が等価ならば#tを、 そうでなければ#fを返さねばなりません。 オブジェクトの各要素に対して再帰的に等価判定を行いたい場合は、 object-equal?を直接呼ぶのではなく、equal?を各要素に対して 呼ぶようにして下さい。

その他

• Scheme:MOP:InstancePool
  

• keyが一つのときのメモ化

  ; ハッシュテーブルでメモ化
  (define-method memoize ((ht <hash-table>) proc key)
    (and (applicable? proc <top>)
      (if-let1 v (hash-table-get ht key #f)
        (begin
          ;(print "メモ化 " key)
          v)
        (rlet1 r (proc key)
          ;(print "!!call !! " key)
          (hash-table-put! ht key r)
          ) ) ) )
  

  (define-method make-memoized ((init-ht <hash-table>) proc)
    (and (applicable? proc <top>)
      (let1 ht init-ht
        (^k (memoize ht proc k) ) ) ))
  

• keyが複数のときのメモ化

  ; ハッシュテーブルでメモ化
  ; keyが複数 , (key-proc primary-key . rest) で実際のキーを作る
  ; TODO proc,key-procの複数のapplicabilityチェック
  ;      (可変のapplicable?は可能？)
  (define-method memoize ((ht <hash-table>) proc key-proc primary-key . rest )
    (let1 key (apply key-proc primary-key rest)
      (if-let1 v (hash-table-get ht key #f)
        (begin
          ;(print "メモ化 " key)
          v)
        (rlet1 r (apply proc primary-key rest)
          ;(print "!!call !! " key)
          (hash-table-put! ht key r)
          ) ) ) )
  

  ; TODO proc,key-procの複数のapplicabilityチェック
  ;      (可変のapplicable?は可能？)
  (define-method make-memoized ((init-ht <hash-table>) proc key-proc)
    (let1 ht init-ht
      (^ arg (apply memoize ht proc key-proc arg) ) ) )
  

yamasushi(2013/04/14 08:27:35 UTC) 改良してみました。

• keyが一つ

  ; dictionaryでメモ化
  (define-method single-memoize ((ht <dictionary>) proc k)
    (if-let1 v (dict-get ht k #f)
      (begin
        ;(print "メモ化 " k)
        v)
      (rlet1 r (proc k)
        ;(print "!!call !! " k)
        (dict-put! ht k r)
        ) ) )
  (define-method make-single-memoized ((ht <dictionary>) proc)
    (^x (single-memoize ht proc x) ) )
  
  

• key複数でも可だが、要素に適切な等価判定が設定されていること

  (define-method simple-memoize ((ht <dictionary>) proc . k)
    (if-let1 v (dict-get ht k #f)
      (begin
        ;(print "メモ化 " k)
        v)
      (rlet1 r (apply proc k)
        ;(print "!!call !! " k)
        (dict-put! ht k r)
        ) ) )
  
  (define-method make-simple-memoized ((ht <dictionary>) proc)
    (^ arg (apply simple-memoize ht proc arg) ) )
  
  

• hash-tableで実装する。

  (define-method make-single-memoized ( (type <symbol>) proc)
    (make-single-memoized (make-hash-table type) proc) )
  
  (define-method make-simple-memoized (proc)
    (make-simple-memoized (make-hash-table 'equal?) proc) )
  

使用例

• 等価判定とhashを用意しておきます。

  ; 等価判定を付加する。
  (define-method object-equal? ( (obj1 <info-file> ) (obj2 <info-file>) )
    (string=? (~ obj1 'path) (~ obj2 'path) ) )
  
  (define-method object-equal? ( (obj1 <info-node> ) (obj2 <info-node>) )
    (and
      (equal? (~ obj1 'file) (~ obj2 'file))
      (equal? (~ obj1 'name) (~ obj2 'name)) ) )
  
  ; hashを定義する
  (define-method object-hash ((a <info-file>))
    (hash (~ a 'path) ) )
  
  (define-method object-hash ((a <info-node>))
    (hash (list (~ a 'file 'path) (~ a 'name) ) ) )
  

• キー一つのときの例(文字列をキーにしています。)

  (define info-node-open-file
    (make-single-memoized 'string=? ($ open-info-file $ find-info-file $) ) )
  

• キーが複数の例。

  (define-method %info-node-get-index% ( (info <info-file>) node-name )
    (and-let* [ [_ (string? node-name) ]
                [_ info  ]
                [node (info-get-node info node-name)] ]
      (let1 info-index (make-tree-map string=? string<?)
        (for-each
          (match-lambda
            [ (keyword . nodename)
               .....
          (info-parse-menu node) )
        (list node info-index)
        ) ) )
  ; メモ化
  (define info-node-get-index (make-simple-memoized %info-node-get-index%) )
  

• Shiro(2013/04/11 17:08:46 UTC): メモ化手続きは、手続きの性質によって どうメモ化すべきかが変わるので、 汎用的なモジュールにするのは難しい、というのが私の印象です。 せいぜい、アプリケーションごとにそれで使うメモ化をまとめておく、くらいでしょうか。 どうせ汎用化できないなら、その都度書いてしまっても大した手間じゃないですし。

• yamasushi(2013/04/11 22:01:11 UTC): 性能をシビアに考えないでいいけれど、重い処理は繰り返したくないようなカジュアルな用途のために、汎用化できたらいいかなと考えました。

• Shiro(2013/04/12 01:16:55 UTC): カジュアルな用途というのが使い捨てスクリプト程度ならいいですけど、 それだと複数引数でいちいちkey-procを渡さないとならないのが一手間ありますね。
  あと、普通はmemoizeは内部でメモ用のテーブルを作っちゃって外には見せないと思いますが、 ここで外から渡すようにしてるのはテーブルのリセットとかを後で可能にするため? (これも「カジュアルな用途」を考えるならそこまで柔軟にせずに普通のmemoizeにしといた方が 手軽かなと思います。)
  もひとつ、make-memoizedのlet1 ht init-htは要らないですよね? Gaucheのコンパイラの 最適化で消えると思いますが、あってもコードがわかりやすくなるわけでもないですし…

• yamasushi(2013/04/12 23:13:29 UTC) let ht init-htはいらないのでしたか。なるほど。(いまひとつschemeを理解していないのでありました。)
  テーブルを渡しているのは、key仕様('string=?とかのことです)をあとから変更できるように・・・とか考えたのでした。そういえば、テーブルのリセットにも使えますね。
  また、hash-table固定でなく、dictionaryとするという考えもちらりと浮かんだりしてます。
  • yamasushi(2013/04/13 01:57:43 UTC)

    ; dictionaryでメモ化
    ; key一つ
    (define-method memoize ((ht <dictionary>) proc key)
      (and (applicable? proc <top>)
        (if-let1 v (dict-get ht key #f)
          (begin
            ;(print "メモ化 " key)
            v)
          (rlet1 r (proc key)
            ;(print "!!call !! " key)
            (dict-put! ht key r)
            ) ) ) )
    ; dictionaryでメモ化
    ; keyが複数 , (key-proc primary-key . rest) で実際のキーを作る
    (define-method memoize ((ht <dictionary>) proc key-proc primary-key . rest )
      (let1 key (apply key-proc primary-key rest)
        (if-let1 v (dict-get ht key #f)
          (begin
            ;(print "メモ化 " key)
            v)
          (rlet1 r (apply proc primary-key rest)
            ;(print "!!call !! " key)
            (dict-put! ht key r)
            ) ) ) )
    
    (define-method make-memoized ((ht <dictionary>) proc)
      (^k (memoize ht proc k) ) )
    
    (define-method make-memoized ((ht <dictionary>) proc key-proc)
      (^ arg (apply memoize ht proc key-proc arg) ) )
    
    

• yamasushi(2013/04/13 12:28:04 UTC)手続きの引数の同一性判定関数がわかっているタイプをひとくくりにできれば(<memoizable>的なクラス)、key-procの指定は全自動でできるのかしらとか考えました。
  うまくまとまらないのですが、手続きをつくるときに同一性判定関数もセットで定義するみたいな感じです。

• Shiro(2013/04/13 14:01:32 UTC): 私の感覚では、メモ化が「使える」のは限定的な場面なので、 頑張って汎用化してもアンバランスだなあという感じです。引数をどう比較するかという 問題もありますが (例えば、equal?で比較したいリストとeq?で比較しないとならないリストを 引数に取る関数、のkey-procはどう書きますか?)、それ以外にもそもそも同じ引数で呼ばれることが 滅多に無ければメモ化の意味がないですし、同じ引数で呼ばれることが非常に多いけれどもその 理由がコールグラフの同じ場所にあるせいなのでむしろdelay/forceでやる方が良いって場合もあります。
  まあその上で、使える場面を限定したお手軽メモ化ユーティリティを作ることには意味があると思います。

• yamasushi(2013/04/13 22:11:15 UTC) メモ化の側面として、これはdictionaryに値を入れるための方法の一つとして見ることができなあと思いました。つまり手続きを与えて、それの挙動をdictionaryに記録している・・・ように見えます。(これにどういう意味があるのかはわかりません。)
  eq?とequql?が混在した場合の件、これはdictionaryを包括するようなデータ構造が必要になるということでしょうか。多次元連想配列的な。
  「お手軽さ」が決め手という指摘は、たしかにそのとおりです。関数を与えればそれがメモ化される、というくらい気軽でなければ・・・と思いました。
  

• Shiro(2013/04/13 22:54:17 UTC): 純粋な関数は写像なので、引数から結果を計算しようが、 あらかじめ全ての引数とそれに対応する結果を辞書に入れといて単にルックアップしようが、 外部から見た機能は同じです。メモ化はこの「辞書」をlazyに構築していると考えられますね。

• yamasushi(2013/04/14 08:37:44 UTC)インターフェースを少し変えて見ました。

Tags: メモワイズ, メモ化, memoize