Haskell太空泄漏

本文介绍了Haskell太空泄漏的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

全部.

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

While trying to solve some programming quiz:https://www.hackerrank.com/challenges/missing-numbers, I came across with space leak.

主要功能是difference，它实现了多组差异.我发现列表':'和三元组(,,)保留在堆中-hT选项分析.但是，只有大列表是difference的两个参数，并且随着difference继续尾递归而缩小.但是列表所消耗的内存随着程序的运行而不断增加.

Main function is difference, which implements multi-set difference.I've found out that List ':' and Triples (,,) kept on heapswith -hT option profiling. However, only big lists are difference'stwo arguments, and it shrinks as difference keeps on tail recursion.But the memory consumed by lists keeps increasing as program runs.

Triples是临时数组结构，用于簿记多集的每个元素的计数.但是三倍消耗的内存也持续增长，我找不到原因.

Triples is ephemeral array structure, used for bookkeeping the count of multiset's each element. But the memory consumed by triples alsokeeps increasing, and I cannot find out why.

尽管我在stackoverflow中浏览了类似的空间泄漏"问题，我不明白这个主意.当然，我有很多东西要学习.

Though I've browsed similar 'space leak' questions in stackoverflow,I couldn't grasp the idea. Surely I have much to study.

我感谢您的任何评论.谢谢.

I appreciate any comments. Thank you.

p.s)可执行文件是使用-O2开关编译的.

p.s) executable is compiled with -O2 switch.

$ ./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的建议，我确定了价值和Array.我附上了堆图.

I seq'ed value and Array thanks to Carl's advice.I attach heap diagram.

[原始堆分析][] 1

[original heap profiling][]1

[在对值v进行排序之后]

[after seq'ing value 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进行序列化之后]

[after seq'ing value 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

Haskell太空泄漏

问题描述

推荐答案