[過去ﾛｸﾞ] 関数型プログラミング言語Haskell Part33 (1002ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

707(4): 2021/02/05(金)19:44 ID:DBOaHn9B(1/2) AAS
>>703
その遅くて使い物にならない計算を、
可読性をあまり犠牲にしないで爆速にする方法に、
メモ化(memoization)というテクニックがあります。
(その代わり、当然メモリを使います)

メモ化関数 memoize が用意されていれば、
n 番目のフィボナッチ数を求める関数 fib は
次のように書けます。

-- メモ化
fib :: Int -> Integer
fib = fix (memoize . fib')

-- フィボナッチ計算の本体
fib' :: (Int -> Integer) -> Int -> Integer
fib' f 0 = 0
fib' f 1 = 1
fib' f n = f (n-1) + f (n-2)

メモ化関数を提供するパッケージは色々あります。
また、メモ化の仕組みの基礎や本質を学びたいのなら、
次のごく短いブログ記事がおすすめです。
外部ﾘﾝｸ[html]:kseo.github.io
この記事の最後の fibMemo 関数について、
適当な小さな値に適用させたものを
自分でノートに展開してみるといいです。

---

708: 2021/02/05(金)20:00 ID:DBOaHn9B(2/2) AAS
>>707
すいません。
肝腎の memoize 関数の定義を書き忘れました。

memoize :: (Int -> a) -> (Int -> a)
memoize f = (map f [0 ..] !!)

先に紹介した記事にこれを導く過程や、
より速くより一般化する方法を学びたい人へ向けた
URL紹介が載っています。

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 3.445s*