[過去ﾛｸﾞ] 関数型プログラミング言語Haskell Part14 (1001ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
317(3): デフォルトの名無しさん [sage] 2011/05/01(日)06:57
>>314
>>316のいうとおり、nの大きさは計算量に関係ないが、しかし、take m (succ n)としたとき前者はO(m^2)、後者はO(m)のオーダーになっているように思う。
前者はいわば
let
x1 = n
x2 = n + 1
x3 = n + 1 + 1
x4 = n + 1 + 1 + 1
・
・
・
in x1 : x2 : x3 : x4 ...
のような計算をしている。しかし、後者は
let
x1 = n
x2 = x1 + 1
x3 = x2 + 1
x4 = x3 + 1
・
・
・
in x1 : x2 : x3 : x4...
のような計算をしている。
前者はx1、x2...に相当するようなものを覚えていないが、後者はnsの中で覚えているので。
簡約と一緒に、コンスセルの間の矢印を書いたほうが良い。
そうすれば、前者だといちいち計算しなおしているものを、後者だと共有していることが分かるはず。
318(1): 316 [sage] 2011/05/01(日)07:44
.>>317
それと同じことが言いたかった
>>316は後者についての話ね
319: 317 [sage] 2011/05/01(日)07:56
>>318
む。オレの読解力が足りなかったみたい。スマン。
326(1): 314 [sage] 2011/05/01(日)14:45
すいません、n には依存しませんね。
私も自分で take m で計算量を調べてました。
まだ納得できないです。
後者の計算で、次のようなステップを考えてました。
take の第1引数の引き算を端折ったり、冗長なステップもありますが、
問題はそこではありません。
[01] take 3 (succ 1)
[02] take 3 ns -- <== ns = 1 : map (+1) ns
[03] take 3 (1 : map (+1) ns)
[04] 1 : take 2 (tail ns)
[05] 1 : take 2 (map (+1) ns)
[06] 1 : take 2 (map (+1) (1 : map (+1) ns))
[07] 1 : take 2 (((+1)1) : map (+1) (tail ns))
[08] 1 : ((+1)1) : take 1 (map (+1) (tail ns))
[09] 1 : ((+1)1) : take 1 (map (+1) (map (+1) ns))
[10] 1 : ((+1)1) : take 1 (map (+1) (map (+1) (1 : map (+1) ns)))
[11] 1 : ((+1)1) : take 1 (map (+1) (((+1)1) : map (+1) ns))
コンスセルの指しているものをグラフを描いて考えてみたのですが、どうしても、
[11] の左側の ((+1)1) と右側の ((+1)1) が別物にしか思えないです。
つまり、たまたま同じ引数に同じ関数を適用しているだけで、
結局のところ２回同じ計算しなければならないと思います。
これらが同じものを指しているのなら、
>>317 の後者のようにリストの各要素は定数時間で計算できるのですが、
別物を指しているように見えるので、リストの各要素は線形時間かかるように見えます。
（全体の計算量というのは結局のところ、簡約ではなくプリミティブな計算の量ですよね）
なぜ左側の ((+1)1) と右側の ((+1)1) が同じものと言えるのか、もう少し考えてみます。
（ちなみに、(+1) は両者で同じ物、1 も両者で同じ物だと思います）
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.035s