Пространственная утечка в динамическом 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 МБ памяти. Насколько мне известно, флаги отсутствуют. –

Или, возможно, я неправильно понимаю вашу проблему. Разумеется, память, очевидно, линейна с 'n', так как вы читаете строки строк n из stdin перед выполнением каких-либо операций. Это все или вы наблюдаете, как 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

EDIT: Другие возможные сбережения включают используя Unboxed массив и не заставляя весь ваш список strLen^2 через last во время построения массива. Рассмотрим array ((0,0),(xBnd,yBnd)) xs.

источник

2016-10-07 21:20:10

Использование границ вместо 'last' сделало трюк! –

Мое ощущение, что проблема в том, что ваш min' недостаточно строг. Поскольку он не форсирует свои аргументы, он просто наращивает громкость для каждого элемента массива. Это вызывает больше памяти, который будет использоваться, раз GC для увеличения и т.д.

Я хотел бы попробовать:

{-# LANGUAGE BangPatterns #-} 

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

источник

2016-10-07 20:58:06 ErikR

Пространственная утечка в динамическом Haskell

ответ

Смежные вопросы