[過去ﾛｸﾞ] 関数型プログラミング言語Haskell Part7 (1001ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
885(3): 2007/09/21(金)12:10 AAS
>>884
確かにそうだ。最悪O(n^2)になるな。
でも、中間リストを作ることが直接の原因ではない。
実際、正確評価ならelts_lt_xとelts_greq_xを作り終えた時点で引数のxsはGCできる。
遅延評価だとこれが上手くいかなくて、逆順にソートされたリストが渡される最悪のケースでO(n^2)になる。
時間的には同じ最悪のケースでも、入力が正順にソートされていた場合はO(n)なんだが。
汚い方法だけど、seqを使って評価順を入れ替えることでO(n)になる。
qsort [] = []
qsort (x:xs) = length elts_lt_x `seq` length elts_greq_x `seq`
qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
where
elts_lt_x = [y | y <- xs, y < x]
elts_greq_x = [y | y <- xs, y >= x]
886(5): 2007/09/21(金)12:47 AAS
プロファイル取って調べてみた。数字はtotal allocにqsortの%allocをかけたもの。左の数字は要素数。
>>881とランダム要素のリスト
800 : 380003.544
1600: 873076.32
2400: 1296538.048
3200: 1816425.728
4000: 2399276.16
>>885とランダム要素のリスト
800 : 400965.324
1600: 1040519.448
2400: 1389810.24
3200: 1846377.12
4000: 2776879.088
>>881と整列リスト（[1..n]）
800 : 8985561.144
1600: 35887143.13
2400: 80695069.14
3200: 143405095.9
4000: 224106868.3
>>885と整列リスト（[1..n]）
800 : 8995036.344
1600: 35906208.73
2400: 80723725.14
3200: 143443342.3
4000: 224154724.3
最悪ケースだとO(n^2)になるっぽい
892: 2007/09/21(金)18:05 AAS
>>891
>HaskellのGCって、いらなくなった瞬間に動くものだったんだな。
デフォルトだと確保エリアの大きさは256kらしいから、第0世代のGCは頻繁に起こるんだろう。
>と書くといいかなと思ったり。
それだとリストの先頭しかeagerに評価されないから、
[99, 100, 97, 98, 95, 96, ..., 4, 1]
みたいなリストが入力だとO(n^2)になる。
リストを最後まで評価させるために>>885ではlengthを使ってる。
895(2): 2007/09/21(金)20:23 AAS
>>885
このコードが理解できない初心者のために、教えてください。
seqは遅延評価をしないための関数のようですが、lengthは何のためにあるのでしょうか。
あとseqは２項演算子として使うのが普通なのですか。
qsort [] = []
qsort (x:xs) = seq (length elts_lt_x) (seq (length elts_greq_x) (qsort elts_lt_x ++ [x] ++ qsort elts_greq_x))
where
elts_lt_x = [y | y <- xs, y < x]
elts_greq_x = [y | y <- xs, y >= x]
と買いても間違いではない？
>>886
>数字はtotal allocにqsortの%allocをかけたもの
total alloc と %alloc が何か分からないので、それらをかけて何が求まるのか分かりません。
total alloc は全体のメモリ消費量で単位はバイトでしょうか。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.038s