全て。
https://www.hackerrank.com/challenges/missing-numbersのプログラミングクイズを解こうとしている ときに、スペースリークに遭遇しました。
主な機能はdifference、マルチセット差分を実装する です。リスト ':' とトリプル (,,) が -hT オプションのプロファイリングでヒープに保持されることがわかりました。ただし、大きなリストだけがの 2 つの引数であり、末尾再帰を続けるdifferenceと縮小します。differenceしかし、リストによって消費されるメモリは、プログラムが実行されるにつれて増加し続けます。
Triples は一時的な配列構造であり、マルチセットの各要素の数を記録するために使用されます。しかし、トリプルによって消費されるメモリも増加し続けており、その理由がわかりません。
同様の「スペースリーク」の質問をstackoverflowで閲覧しましたが、その考えを理解できませんでした. 確かに私には勉強することがたくさんあります。
コメントをお待ちしております。ありがとうございました。
ps) 実行可能ファイルは -O2 スイッチでコンパイルされます。
$ ./difference -hT < input04.txt
Stack space overflow: current size 8388608 bytes.
$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.6.3
.
import Data.List
import Data.Array
-- array (non-zero-count, start-offset, array_data)
array_size=101
myindex :: Int -> Int -> Int
myindex key offset
| key >= offset = key - offset
| otherwise = key - offset + array_size
mylookup x (_,offset,arr) = arr ! idx
where idx = myindex x offset
addOrReplace :: Int -> Int -> (Int, Int, Array Int (Int,Int)) -> (Int, Int, Array Int (Int,Int))
addOrReplace key value (count,offset,arr) = (count', offset, arr // [(idx,(key,value))])
where idx = myindex key offset
(_,prev_value) = arr ! idx
count' = case (prev_value, value) of
(0,0) -> count
(0,_) -> count + 1
(_,0) -> count - 1
otherwise -> count
difference :: (Int,Int,Array Int (Int,Int)) -> [Int] -> [Int] -> [Int]
difference (count,offset,arr) [] []
| count == 0 = []
| otherwise = [ k | x <- [0..array_size-1], let (k,v) = (arr ! x), v /= 0]
difference m (x:xs) y = difference new_m xs y
where (_,v) = mylookup x m
new_m = addOrReplace x (v + 1) m
difference m [] (y:ys) = difference new_m [] ys
where (_,v) = mylookup y m
new_m = if v == 0
then m
else addOrReplace y (v - 1) m
main = do
n <- readLn :: IO Int
pp <- getLine
m <- readLn :: IO Int
qq <- getLine
let p = map (read :: String->Int) . words $ pp
q = map (read :: String->Int) . words $ qq
startArray = (0,head q, array (0,100) [(i,(0,0)) | i <- [0..100]] )
putStrLn . unwords . map show . sort $ difference startArray q p
[編集] Carl のアドバイスのおかげで、値と配列を seq しました。ヒープ図を添付します。
[元のヒープ プロファイリング] [ 
] 1
[値をシーケンシングした後v]
difference m (x:xs) y = difference new_m xs y
where (_,v) = mylookup x m
new_m = v `seq` addOrReplace x (v + 1) m
[値vとをシーケンシングした後Array]
difference m (x:xs) y = new_m `seq` difference new_m xs y
where (_,v) = mylookup x m
new_m = v `seq` addOrReplace x (v + 1) m
