先日の,AOJのMaximum Profitの件の続き. まず,前回の記事で誤解しているところがあった.メモリ使用量が2.6GBとあったが,これはallocateした延べ量だった.ピークメモリ量は260kB程度だった.2.6GBはProfiling Reportから読んだ数字だが,ピークメモリ量はtimeコマンドで測定できる
% /usr/bin/time -f "%M" {コマンド}
メモリ使用量≒入力サイズということは,遅延評価のために全データがメモリに展開されているだろうと色々試行錯誤の上,ようやくAcceptされたコードが以下.
import Data.List import System.IO f :: (Int,Int) -> Int -> (Int,Int) f (m,a) x = let m' = min m x a' = max a (x-m) in (m',a') exec :: (Int,Int) -> IO (Int,Int) exec (m,a)= do l <- getLine let i = read l :: Int o = (m,a) `seq` i `seq` f (m,a) i eof <- isEOF if eof then return o else exec o main = do n <- getLine (_,o) <- exec (2000000000,-2000000000) print o
mapとかfoldとかHaskellっぽいものは一切使わず,1データ毎に正格評価して処理するというHaskellらしくないもの.全然気に入らないけど,他にどう書いたものか分からない...