all.
在尝试解决一些编程测验时：https://www.hackerrank.com/challenges/missing-numbers https://www.hackerrank.com/challenges/missing-numbers，我遇到了空间泄漏。
主要功能是difference，实现了多集差分。
我发现 List ':' 和 Triples (,) 保留在堆上
使用 -hT 选项分析。然而，只有大名单difference的
两个参数，它缩小为difference继续尾递归。
但是列表消耗的内存随着程序的运行而不断增加。
Triples 是临时数组结构，用于记录多重集每个元素的数量。但消耗的内存也增加了三倍 不断增加，我找不到原因。
虽然我在 stackoverflow 上浏览过类似的“空间泄漏”问题， 我无法理解这个想法。当然我还有很多东西要学习。
我很感激任何评论。谢谢。
p.s) 可执行文件是用 -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
[编辑] 感谢卡尔的建议，我对值和数组进行了排序。 我附上堆图。
[original heap profiling]
[
]1 https://i.stack.imgur.com/iCjU2.png
[排序后的值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 and 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
我发现这段代码存在三个主要问题。
首先（不是内存使用的原因，但绝对是性能普遍不佳的原因）Array is horrible对于这个用例。当更新时间为 O(n) 时，O(1) 查找是无用的。
说到这里，值存储在Array没有被强迫difference正在循环其第一个输入。它们是包含指向先前版本的数组中未计算的查找的指针的 thunk。您可以通过多种方式确保在更新数组的同时计算该值。什么时候difference循环遍历第二个输入，事实上，它是通过将值与 0 进行比较来意外地执行此操作的。
Third, difference甚至不强制在遍历其第一个参数时评估正在创建的新数组。在循环的该部分期间不需要对旧数组进行求值。
后两个问题都需要解决才能解决空间泄漏问题。第一个问题不会导致空间泄漏，只是导致开销比所需的高得多。