[過去ﾛｸﾞ] 関数型プログラミング言語Haskell Part33 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
703(4): 2021/02/04(木)22:24 ID:w5MK0dgi(1) AAS
>>702
ありがとうございます
参考にさせていただきます
そうですね
もう一つ可読性が欲しい感じがします
元々の問題意識としては私は可読性の高いコードが要求されることが多いのです
例えばFibonacci数列であれば
f n = ( f $ n -1 ) + ( f $ n - 2 )
に可読性においてまさるものはないのですが、もちろんこれでは遅くて使い物になりません
なので実用性も多少はなりとも求めるならある程度は可読性を犠牲にせざるを得ないのですが、どういう方法がいいのだろうというのがテーマなのです
でたまたまFibonacciの場合に
f = 0 : 1 : ( zipWith ( + ) f $ tail f )
というのを見つけてコレ中々いいなと、dpで計算してるのに“メモ”をするための不要な手続きを書く必要がなく、Haskellの“call by need”の機能をうまく利用してdp計算させてるところにちょっと唸ったもので
でどれくらいコレでいけるのかなと二重数列をやってみたらうまくいかなくて、どうしたもんかなと
まぁコレはしょうがないのかもしれませんけど
704: 2021/02/05(金)00:47 ID:hZ1aOePg(1) AAS
>>703
方向性違うかなと思いつつ書いたんですがやっぱり違いましたね。失礼しました。
今更どうでもいいですがちょっと間違えたので訂正だけさせてください。
comb7_1 = (repeat 1 :) $ (map (scanl (+) 1 . tail) $ comb7_1)
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 関数について、
適当な小さな値に適用させたものを
自分でノートに展開してみるといいです。
709(1): 2021/02/06(土)09:10 ID:8eeMDweD(1) AAS
>>707
解説ありがとうございます
やはりメモ化するしかないんだと思います
問題はそれがプログラマが明示的に自分でやらないといけないのか、コンパイラが自分でやってくれるのかの差なんだと思います
Haskellは純粋なcall by nameではなく、call by needのシステムの中にメモ化を備えていてプログラマがメモ化するように書いてなくても勝手にメモ化できるものをメモ化してくれるのがすごいとこだと思うんですけど、例えば>>703の2番目の例で最初見た時「なんでこの定義式でメモ化が効くんだ？」とさっぱりわからなかったのが、実はHaskellのcall by needのシステムをうまく利用してるらしいとわかったのが最初なんです
で二重の漸化式だとうまくいかないなと
もちろん二重の全炊きでも上手くsuffixの取り方を変えたりすると同様の方法でメモ化できるんですけど、それでは結局「Haskellの機能を利用して明示的にメモ化を指定することなく高速化した」事にはなりません
まぁコレはしょうがないんでしょうね
どんな計算も常にメモ化して常に同じ評価式を2度扱う事を防いでたらそんなの逆に使い物になりませんからね
712: 2021/02/06(土)21:12 ID:HlAr7yEc(1) AAS
>>709
今回の話の本質ではないので、へーそうなんだ、
程度に聞いてくれればいいのですが、
>>703 の2番目の例とは、
f = 0 : 1 : zipWith (+) f (tail f)
のことでしょうか。
もしそうなら、これはメモ化ではないですよ。
(このテクニックをなんと呼ぶのかは知りませんが)
メモ化というのは簡単にいえば、
関数の同じ引数に対する2度目(以降)の適用に備えて、
その引数に対する1度目の関数の値をその引数とペアにして
どこかにメモしておくことです。
ポイントは、2度目以降に備えることではなく、
引数と関数値のペアをメモしておくことです。
それを踏まえて、>>703 の2番目の例において、
では何が関数で、引数と関数値のペアはどこにメモされているか、
考えてみてください。
ただ、言葉の意味は時代と共に変化していくものなので、
今はこれも広義にメモ化と言うことになっているのでしたら、すいません。
私の方が勉強不足です。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.031s