動態Haskell中的空間泄漏

前幾天我發佈了這個問題：Haskell performance using dynamic programming，並建議使用ByteStrings而不是Strings。在使用ByteStrings實現算法後，程序崩潰，超出內存限制。動態Haskell中的空間泄漏

import Control.Monad 
import Data.Array.IArray 
import qualified Data.ByteString as B 

main = do 
    n <- readLn 
    pairs <- replicateM n $ do 
    s1 <- B.getLine 
    s2 <- B.getLine 
    return (s1,s2) 
    mapM_ (print . editDistance) pairs 

editDistance :: (B.ByteString, B.ByteString) -> Int 
editDistance (s1, s2) = dynamic editDistance' (B.length s1, B.length s2) 
    where 
    editDistance' table (i,j) 
     | min i j == 0 = max i j 
     | otherwise = min' (table!((i-1),j) + 1) (table!(i,(j-1)) + 1) (table!((i-1),(j-1)) + cost) 
     where 
     cost = if B.index s1 (i-1) == B.index s2 (j-1) then 0 else 1 
     min' a b = min (min a b) 

dynamic :: (Array (Int,Int) Int -> (Int,Int) -> Int) -> (Int,Int) -> Int 
dynamic compute (xBnd, yBnd) = table!(xBnd,yBnd) 
    where 
    table = newTable $ map (\coord -> (coord, compute table coord)) [(x,y) | x<-[0..xBnd], y<-[0..yBnd]] 
    newTable xs = array ((0,0),fst (last xs)) xs

內存消耗似乎與n成比例。輸入字符串的長度爲1000個字符。我希望Haskell在每個解決方案打印後釋放所有在editDistance中使用的內存。這不是這種情況嗎？如果沒有，我該如何強制這個？

我看到的唯一的其他實際計算是cost，但強制與seq什麼也沒做。

來源

2016-10-07 Free_D

我無法重現您的問題。你使用什麼版本的GHC？你在編譯什麼標誌？ –

@ ThomasM.DuBuisson這是通過HackerRank比賽完成的。環境使用ghc 7.8，只提供512 MB的內存。據我所知，沒有標誌。 –

或者我誤解了你的問題。由於您在執行任何操作之前正在從stdin讀取「n」行字符串，所以肯定內存與'n'顯然是線性關係。是所有還是你正在觀察editDistance在某個維度上佔用太多內存？ –

當然，你的記憶將與n如果你看過所有n輸入計算的結果和印刷前增加輸出。你可以嘗試交錯的輸入和輸出操作：

main = do 
    n <- readLn 
    replicateM_ n $ do 
    s1 <- B.getLine 
    s2 <- B.getLine 
    print (editDistance (s1,s2))

或可選擇地使用懶IO（未經測試，可能需要無償B.）：

main = do 
    n <- readLn 
    cont <- getContents 
    let lns = take n (lines cont) 
     pairs = unfoldr (\case (x:y:rs) -> Just ((x,y),rs) ; _ -> Nothing) lns 
    mapM_ (print . editDistance) pairs

編輯：使用未裝箱的陣列，而不是其他可能的儲蓄包括在陣列構建期間通過last強制您的整個strLen^2大小列表。考慮array ((0,0),(xBnd,yBnd)) xs。

來源

2016-10-07 21:20:10

使用邊界而不是'last'做了訣竅！ –

我的感覺是，問題在於你的min'不夠嚴格。因爲它不強制它的參數，它只是爲每個數組元素構建一個thunk。這將導致使用更多的內存，GC次增加等

我會嘗試：

{-# LANGUAGE BangPatterns #-} 

... 
min' !a !b !c = min a (min b c)

來源

2016-10-07 20:58:06 ErikR

動態Haskell中的空間泄漏

回答

相關問題