[過去ﾛｸﾞ] 関数型プログラミング言語Haskell Part7 (1001ﾚｽ)

関数型プログラミング言語Haskell Part7 http://echo.5ch.net/test/read.cgi/tech/1174211797/

上下前次1-新
通常表示 512ﾊﾞｲﾄ分割 ﾚｽ栞
抽出解除 ﾚｽ栞

---

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

---

ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡

---

886: デフォルトの名無しさん [sage] 2007/09/21(金) 12:47:02 プロファイル取って調べてみた。数字は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)になるっぽい http://echo.5ch.net/test/read.cgi/tech/1174211797/886

887: 886 [sage] 2007/09/21(金) 13:00:44 ちなみにコードはこんな感じ import System.Random main = print . qsort =<< lst 800 lst n = fmap (take n . randomRs (1, 1000000)) newStdGen lst2 n = return [1 .. n] qsort [] = [] qsort (x:xs) = 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] qsort2 [] = [] qsort2 (x:xs) = length elts_lt_x `seq` length elts_greq_x `seq` qsort2 elts_lt_x ++ [x] ++ qsort2 elts_greq_x where elts_lt_x = [y | y <- xs, y < x] elts_greq_x = [y | y <- xs, y >= x] main関数のqsortとlstと800の部分を変化させながら計測していった。 http://echo.5ch.net/test/read.cgi/tech/1174211797/887

888: デフォルトの名無しさん [sage] 2007/09/21(金) 13:12:52 >>886 total allocは確保したメモリの総量だから、空間効率を計るのには使えない。 +RTS -sstderrをつけてmaximum residencyを見ればO(n)になってるのが分かると思う。 http://echo.5ch.net/test/read.cgi/tech/1174211797/888

891: 886 [sage] 2007/09/21(金) 14:04:46 >>888 >>890 なるほど。 HaskellのGCって、いらなくなった瞬間に動くものだったんだな。 もっとメモリが足りなくなってから動くものだと思ってた。 （そういう扱いをする部分（世代？）もあると思うけど） というかそれ以前に、885で >逆順にソートされたリストが渡される最悪のケースでO(n^2)になる。 って書いてあるのになにも分かってなかった。 あと885は qsort [] = [] qsort (x:xs) = let !elts_lt_x = [y | y <- xs, y < x] in let !elts_greq_x = [y | y <- xs, y >= x] in qsort elts_lt_x ++ [x] ++ qsort elts_greq_x と書くといいかなと思ったり。 http://echo.5ch.net/test/read.cgi/tech/1174211797/891

895: デフォルトの名無しさん [sage] 2007/09/21(金) 20:23:16 >>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 は全体のメモリ消費量で単位はバイトでしょうか。 http://echo.5ch.net/test/read.cgi/tech/1174211797/895

904: 886 [sage] 2007/09/21(金) 23:41:03 >>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 というようなログが出力される。 total allocとか%allocはこれのこと。 total allocはアロケートされたメモリの累計で、%allocは各関数ごとの割合。 とまあそういうことなんだけど、ここでの議論は、GCでメモリが再利用されて O(n)になるという話なので、無意味と言うか、的外れと言うか、 >>886-887は無かったことにしてください。 メモリ使用量を正しく知る方法は>>888。 http://echo.5ch.net/test/read.cgi/tech/1174211797/904

---

ﾒﾓ帳

(0/65535文字)

---

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

---

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

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.039s