Gauche でメモ化 @ val it: α → α = fun

>Gauche のマニュアルを眺めていたらハッシュテーブルがあったので、昨日のメモ化のやつをちょっと Gauche で書いてみました。 > >(define (ptm l x)
(define h (make-hash-table 'equal?))
(define (calc-val l x)
(let ((key (cons l x)))
(if (hash-table-exists? h key)
(hash-table-get h key)
(loop l x))))
(define (loop l x)
(cond ((or (= l 0) (= x 0) (= x l)) 1)
(else (let* ((v1 (calc-val (- l 1) x))
(v2 (calc-val (- l 1) (- x 1))))
(hash-table-put! h (cons l x) (+ v1 v2))
(+ v1 v2)))))
(loop l x)) > >まあやっぱりこっちの方が遅いですね。うーん、けっきょく再帰しちゃうので、スタックの操作のあたりが効いてくるんですかね。 Scheme で書くと、 Haskell とちがってその段までの三角形の全要素を計算してしまうわけだから、ロスは大きいんじゃないかと思うんですが、案外そうでもないのか。ただ、時間差は昨日のほどは強くありませんでした。倍くらいしか変わりません。 >

val it: α → α = fun

Gauche でメモ化

Archives

disclaimer