ダイナミックハスケルのスペースリーク

Question

私は数日前にこの質問を投稿しました：Haskell performance using dynamic programmingで、StringsではなくByteStringsを使用することをお勧めしました。 ByteStringsでアルゴリズムを実装した後、プログラムがクラッシュし、メモリ制限を超えます。

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では何もしませんでした。

Answer 1

を使用すると、すべての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：他の可能な節約が含まれ、非ボックス化配列を使用していないあなたは、入出力操作をインターリーブ試みることができますあなたの全体のstrLen^2サイズリストをlast経由で配列構築中に強制します。 array ((0,0),(xBnd,yBnd)) xsを考えてください。

Answer 2

私の気持ちは、あなたのmin'が十分に厳格ではないということです。それは引数を強制するものではないので、各配列要素のサンクを単純に構築します。これは、など、増加し、より多くのメモリを使用する

をGC時間を引き起こし私がしようとするだろう：

{-# LANGUAGE BangPatterns #-} 

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