1

数日前にこの質問を投稿しました:動的プログラミングを使用した Haskell のパフォーマンスで、文字列の代わりに 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 文字です。editDistance各ソリューションが印刷された後、Haskell が使用されているすべてのメモリを解放することを期待します。そうではありませんか？そうでない場合、どうすればこれを強制できますか?

私が見る唯一の他の実際の計算は for ですcostが、それを強制してseqも何もしませんでした。

4

2 に答える 2

2

結果を計算して出力を出力する前にnすべての入力を読み取ると、確かにメモリが増加します。n入力操作と出力操作をインターリーブしてみることができます。

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

または、代わりに遅延 IO を使用します (テストされていないため、おそらく gratuitous が必要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。

于 2016-10-07T21:20:10.750 に答える
0

私の感じでは、問題はあなたmin'が十分に厳格ではないということです. 引数を強制しないため、配列要素ごとにサンクを構築するだけです。これにより、より多くのメモリが使用され、GC 時間が増加します。

私は試してみます：

{-# LANGUAGE BangPatterns #-}

...
min' !a !b !c = min a (min b c)
于 2016-10-07T20:58:06.200 に答える