881 名前: デフォルトの名無しさん Mail: sage 投稿日: 2007/09/20(木) 22:42:51
http://web.yl.is.s.u-tokyo.ac.jp/~ganat/memo/aboutHaskell.htmlにある
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]
というクイックソートですが、これのメモリ消費量は、リストの長さをnとしたとき、O(n^2)になるような気がするのですが、どうでしょうか。
またCやJavaで配列を使うと、配列そのものを書き換えることで、メモリ消費量は増えませんが、Haskellでも同じようなことができますか。
883 名前: デフォルトの名無しさん Mail: sage 投稿日: 2007/09/20(木) 23:06:56
>>881
O(n)だと思う。参照されなくなったリストはGCによって回収されるので。
Haskellのリストは書き換えられない。破壊的に更新したいなら専用のデータ構造が要る、例えば
http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Array-IO.html
884 名前: デフォルトの名無しさん Mail: sage 投稿日: 2007/09/21(金) 09:51:28
>>883
O(n)にはならないように思うのですが。
整列が完了したら、参照されなくなったリストはGCされますが、整列中の間は参照されているわけですからGCされませんよね？
再帰呼び出しごとに新しいリストが作られ、それらは呼び出しから戻らないとGCされませんが、呼び出しから戻る前に別の再帰呼び出しが発生するわけだから、やはりメモリ消費量はO(n)ではないと思います。
また再帰呼び出しの深さは最大n-1になるので、やはりO(n^2)ではないでしょうか。実際には、呼び出しの深さは平均でlog(n)でしょうから、 O(n*log(n))が正解かもしれませんが。
詳しい人、お願いします。
885 名前: デフォルトの名無しさん Mail: sage 投稿日: 2007/09/21(金) 12:10:42
>>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]888 名前: デフォルトの名無しさん Mail: sage 投稿日: 2007/09/21(金) 13:12:52
>>886
total allocは確保したメモリの総量だから、空間効率を計るのには使えない。
+RTS -sstderrをつけてmaximum residencyを見ればO(n)になってるのが分かると思う。
897 名前: デフォルトの名無しさん Mail: sage 投稿日: 2007/09/21(金) 21:07:44
>>895
それで合ってる。seqを中置で使うのは良く見かける気がする。
seqを使っているのは再帰に入る前にelts_lt_xとelts_greq_xを完全に評価するため。
未評価のelts_greq_xのサンクはxsを参照しているけど、
完全に評価してしまえばただのリストなので、xsへの参照がなくなって、
GCがxsを回収できるようになる。
seq A Bの値はBと同じだけど、この式を評価する時はまずAを評価して、
その結果を捨て、改めてBを評価する。
length elts_lt_x `seq` 本体
を評価するときは、まずelts_lt_xの長さを求めることになるが、
リストの長さを求めるにはリスト全体を評価する必要がある。
結局、本体が評価される前にelts_lt_xが完全に評価される。
lengthが必要な理由には、seqの仕様が関わってくる。
seq A Bが評価されるとき、Aは弱冠頭正規形(weak head normal form, WHNF)まで簡約される。
WHNFというのは、最も外側のデータ構築子が確定した形。
例えば1+2や[1,2]++[3,4]はWHNFじゃないけど、3や1:([2]++[3,4])はWHNF。
だから、lengthを使わずに
elts_lt_x `seq` 本体
のように定義すると、例えば
elts_lt_x = [y | y <- [1, 2, 3, 4], y < 5]
のとき、これを
elts_lt_x = 1 : [y | y <- [2, 3, 4], y < 5]
と簡約したら、この段階でWHNFに達したことになり、評価が終わってしまう。
これだと、xs(ここでは[2, 3, 4])への参照が残っていて、GCがxsを回収できない。
901 名前: デフォルトの名無しさん Mail: sage 投稿日: 2007/09/21(金) 22:02:09
>>897
力作ありがとうございます。
seqは完全に遅延評価を回避できるわけではないんですね。なんというか、オブジェクト指向言語でよく出てくるshallow copyとdeep copyの違いみたいな感じでしょうか（つまりseqはshallow copyに似ている）。
しかし完全に評価するためにlengthを使うのって、bad know howですよね。
このためにlengthを使うのは、lengthの本来の用途ではないのだから、完全に評価するための専用の関数が標準で用意されるべきたと思いました。たとえその実体がlengthであったとしても。
902 名前: デフォルトの名無しさん Mail: sage 投稿日: 2007/09/21(金) 22:16:34
Control.Parallel.Strategies.force :: (NFData a) => a -> a
を使うのかな。
これはこれで目的外使用な気もするが。
904 名前: 886 Mail: 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。
