Haskell Space Leak

Question

Все.

Пытаясь решить некоторые вопросы о программировании: https://www.hackerrank.com/challenges/missing-numbers, я столкнулся с утечкой места.

Основная функция difference, который реализует множественную разницу. Я обнаружил, что List ':' и Triples (,,) хранятся в кучах с профилированием опции -hT. Тем не менее, только большие списки differenceэто два аргумента, и это сокращается как difference продолжает хвостовую рекурсию Но память, используемая списками, продолжает увеличиваться при запуске программы.

Тройки - это структура эфемерного массива, используемая для учета количества каждого элемента мультимножества. Но память, потребляемая тройками, также продолжает увеличиваться, и я не могу понять, почему.

Хотя я просматривал похожие вопросы о "утечке пространства" в stackru, я не мог понять эту идею. Конечно, у меня есть много, чтобы учиться.

Я ценю любые комментарии. Спасибо.

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

[РЕДАКТИРОВАТЬ] Я получил значение и Массив благодаря совету Карла. Я прикрепляю диаграмму кучи.

[Оригинальное профилирование кучи] [] 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(1) поиск бесполезен, когда обновления O(n).

Говоря о, значения хранятся в Array не вынуждены в то время как difference проходит по первому входу. Они представляют собой ссылки, содержащие указатели на неоцененный поиск в предыдущей версии массива. Вы можете убедиться, что значение вычисляется одновременно с обновлением массива различными способами. когда difference зацикливается на своем втором входе, он делает это случайно, фактически сравнивая значение с 0.

В третьих, difference даже не заставляет оценивать создаваемые новые массивы при обходе первого аргумента. Ничто не требует оценки старого массива во время этой части цикла.

Обе эти последние проблемы должны быть решены, чтобы устранить утечку пространства. Первая проблема не приводит к утечке пространства, просто намного больше накладных расходов, чем необходимо.