[過去ﾛｸﾞ] 関数型プログラミング言語Haskell Part7 (1001ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
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
省16
887(1): 886 2007/09/21(金)13:00 AAS
AA省
888(3): 2007/09/21(金)13:12 AAS
>>886
total allocは確保したメモリの総量だから、空間効率を計るのには使えない。
+RTS -sstderrをつけてmaximum residencyを見ればO(n)になってるのが分かると思う。
891(1): 886 2007/09/21(金)14:04 AAS
>>888
>>890
なるほど。
HaskellのGCって、いらなくなった瞬間に動くものだったんだな。
もっとメモリが足りなくなってから動くものだと思ってた。
（そういう扱いをする部分（世代？）もあると思うけど）
というかそれ以前に、885で
>逆順にソートされたリストが渡される最悪のケースでO(n^2)になる。
って書いてあるのになにも分かってなかった。
あと885は
省6
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]
と買いても間違いではない？
省4
904: 886 2007/09/21(金)23:41 AAS
>>895
-prof付きでコンパイルしてから+RTS -p付きで実行するとプロファイルがとれて、
Fri Sep 21 23:19 2007 Time and Allocation Profiling Report (Final)
main.exe +RTS -p -RTS
total time = 0.05 secs (1 ticks @ 50 ms)
total alloc = 9,079,028 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
main Main 100.0 0.3
qsort Main 0.0 99.1
というようなログが出力される。
省6
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.171s*