3

整数の文字列の最大合計部分文字列を計算するための次の Haskell プログラムがあります。

{-# LANGUAGE BangPatterns #-} {-# OPTIONS_GHC -O2 #-}
import Data.Functor
import Data.Maybe 
import Data.ByteString.Lazy.Char8 (getContents,lines,readInt,words)
import Prelude hiding (getContents,words,lines)

main = do
    cont <- words <$> getContents
    putStrLn $ show $ snd $ foldl opt (0,0) $ map (fst.fromJust.readInt) cont

opt (!c,!m) x = (max 0 (c+x),max m (c+x))

このプログラムの問題は、ファイル全体をメモリに読み込むことです。BytesString のない対応するプログラムには、この問題はありません。

{-# LANGUAGE BangPatterns #-} {-# OPTIONS_GHC -O2 #-}
import Data.Functor
import Data.Maybe 

main = do
    cont <- words <$> getContents
    putStrLn $ show $ snd $ foldl opt (0,0) $ map read cont
opt (!c,!m) x = (max 0 (c+x),max m (c+x))

少量の一定量のメモリしか使用しませんが、もちろん非常に遅いです (約 25 倍遅くなります)。

この問題は、非常に大きな行を読み取るプログラムでのみ発生します。入力が複数の小さな行にまたがっている場合、ByteString は期待どおりに動作します。

これを回避する方法はありますか？

4

2 に答える 2

6

そこでの遅延タプルの使用は最適ではありません。これは次のように書き直した方がよいでしょう:

main = do
    cont <- words <$> getContents
    putStrLn $ show $ sndT $ foldl opt (T 0 0) $ map (fst.fromJust.readInt) cont

sndT :: T -> Int
sndT (T _ m) = m

opt (T c m) x = T (max 0 (c+x)) (max m (c+x))

data T = T {-# UNPACK #-} !Int  {-# UNPACK #-}!Int

したがって、厳密でボックス化されていないアキュムレータが得られます。ただし、この全体をインクリメンタルな左折りとして記述した方がよいでしょう。そのためreadInt、2 番目のパラメーターで残りの入力を返します。合計は必要ありません。マップ。言葉のパイプライン。

送信したバージョンでスペースがリークしています。大きなファイルで実行し、ファイル サイズに比例したヒープを使用します (640k エントリ)。

$ time ./A +RTS -p -s -K50M < input.txt.2
346882
     326,337,136 bytes allocated in the heap
     302,321,732 bytes copied during GC
      82,617,772 bytes maximum residency (8 sample(s))
       1,466,500 bytes maximum slop
             149 MB total memory in use (0 MB lost due to fragmentation)

  %GC     time      63.8%  (63.9% elapsed)

あなたが言うように、ファイルを保持しています。

ここに画像の説明を入力

では、記憶を保持することとは何でしょう？1 つの手がかりは、foldloptです。遅延タプルを渡します。そして、アキュムレータfoldlで怠惰です。

したがって、評価されていない操作の長いチェーンを構築しているだけです+。はそのアキュムレータを評価しないため、上の強打パターンoptは違いを生みません。foldl最後に最終的に結果を調べたときにのみ、全体が崩壊します。

これは古典的なスペースリークです。そう：

  • foldl' を使用します -- アキュムレータでは厳密です
  • 中間リストを完全に避ける (readInt + unfoldr を使用)。
  • リストをトラバースする必要がある場合は、アキュムレータで厳密なタプルを使用して、パフォーマンスをさらに向上させます。
于 2013-09-02T10:40:09.877 に答える