Haskell 空间泄漏

Question

全部。

在尝试解决一些编程测验时: https://www.hackerrank.com/challenges/missing-numbers，我遇到了空间泄漏。

主要功能是difference，实现多集差分。我发现 List ':' 和 Triples (,,) 堆放在一起使用 -hT 选项分析。然而，只有大列表才是不同的两个参数，它随着 difference 继续尾递归而缩小。但是列表消耗的内存随着程序的运行不断增加。

Triples 是临时数组结构，用于记录 multiset 的每个元素的计数。但是三元组消耗的内存也不断增加，我找不到原因。

尽管我在 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

[编辑]多亏了 Carl 的建议，我对 value 和 Array 进行了排序。我附上堆图。

[原始堆分析][ ] 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

Answer 1

我发现这段代码存在三个主要问题。

首先(不是内存使用的原因，但绝对是性能普遍较差的原因)Array 对于这个用例来说是可怕的。当更新为 O(n) 时，O(1) 查找是无用的。

说到，当 difference 循环其第一个输入时，存储在 Array 中的值不是强制的。它们是包含指向先前版本数组中未评估查找的指针的 thunk。您可以通过多种方式确保在更新数组的同时评估值。当 difference 遍历其第二个输入时，它实际上是意外地通过将值与 0 进行比较来做到这一点。

第三，difference 在遍历其第一个参数时甚至不强制计算正在创建的新数组。在循环的那一部分不需要对旧数组进行求值。

后两个问题都需要解决以修复空间泄漏。第一个问题不会导致空间泄漏，只是开销比需要的高得多。