val it: α → α = fun

ptm l n = evalState (main l n) empty
where main 0 _ = modify (insert (0, 0) 1) >> return 1
main l 0 = modify (insert (l, 0) 1) >> return 1
main l x
| l == x = modify (insert (l, x) 1) >> return 1
| otherwise = do v1' <- gets $ lookup (l-1, x)
v1 <- maybe (main (l-1) x) return v1'
v2' <- gets $ lookup (l-1, x-1)
v2 <- maybe (main (l-1) (x-1)) return v2'
modify (insert (l, x) (v1+v2))
return (v1+v2) > >というところでしょうか。計算させてみると、前回の三角形作っちゃう版と同じくらい速く動きますが、デカい数値になると如実に差があらわれてしまいます。前回版を繰返しということで pti という名前で定義していますが、比較はこんな感じ。 > >*Main> :set +s
*Main> ptm 1000 500
(長いので略)
(17.18 secs, 622941608 bytes)
*Main> pti 1000 500
(長いので略)
(0.58 secs, 51275988 bytes) > >というわけでメモ化した方がだいぶ遅いです。 Data.Map は log n な速度ですし、 AVL 木なので回転に計算コストがかかっているのかも。それとも State モナドが単に遅い？　というわけで気になったので Data.Array.IO を使って IO 操作でメモ化する方針のもちょっと書いてみましたが、やっぱりむしろ遅くなりました。どこかアルゴリズム間違えている？ > >実のところ pti も Haskell 処理系自身のメモ化による高速化がされたものなので、そちらの方が速いのは当然なのかもしれませんが……。 >