MORDOR 문제 haskell로 푸는데 런타임 에러가 계속 나오네요.

  • jwvg0425
    jwvg0425

    아마 메모리 초과로 런타임 에러가 나는 것 같은데 정확한 이유를 잘 모르겠습니다. 여러번 시도했는데 직접 테스트 케이스 이것저것 돌려봤을 때는 딱히 문제가 없는데 제출하니 계속 런타임 에러가 나와서 답답하네요.

    혹시 haskell에서 메모리 사용량을 줄이는 좋은 방법 알고 계신 분 없나요?

    제가 제출한 코드는 다음과 같습니다.

    import Data.List
import Control.Monad

data Tree = Node Int (Int, Int) Tree Tree | Empty deriving Show

val :: Tree -> Int
val (Node v _ _ _) = v
val Empty = (-1)

segment :: Tree -> (Int, Int)
segment (Node _ s _ _) = s
segment Empty = (-1, -1)

left :: Tree -> Tree
left (Node _ _ l _) = l
left Empty = Empty

right :: Tree -> Tree
right (Node _ _ _ r) = r
right Empty = Empty

query :: Tree -> (Int -> Int -> Int) -> Int -> Int -> Int
query Empty _ _ _ = val Empty
query (Node v (l,r) lc rc) merge ls rs
    | l == ls && r == rs = v
    | ls >= (fst $ segment rc) = query rc merge ls rs
    | rs <= (snd $ segment lc) = query lc merge ls rs
    | otherwise = let lval = query lc merge ls (snd $ segment lc)
                      rval = query rc merge (fst $ segment rc) rs
                  in merge lval rval

difficulty :: Tree -> Tree -> (Int, Int) -> Int
difficulty maxTree minTree (l,r) = maxval - minval
    where maxval = query maxTree max l r
          minval = query minTree min l r

makeTree :: [Int] -> (Int -> Int -> Int) -> Int -> Int -> Tree
makeTree [] _ l r = Empty
makeTree [a] _ l r = Node a (l,r) Empty Empty
makeTree xs cmp l r = Node (cmp (val leftTree) (val rightTree)) (l, r) leftTree rightTree
    where len = (length xs + 1) `div` 2
          (xl, xr) = splitAt len xs
          leftTree = makeTree xl cmp l (l+len-1)
          rightTree = makeTree xr cmp (l+len) r

fromList :: [Int] -> (Int -> Int -> Int) -> Tree
fromList xs cmp = makeTree xs cmp 0 (length xs - 1)

solve :: [Int] -> [(Int, Int)] -> [Int]
solve heights queries = let maxTree = fromList heights max
                            minTree = fromList heights min
                        in map (difficulty maxTree minTree) queries

getInt :: IO Int
getInt = liftM read getLine

getInts :: IO [Int]
getInts = liftM (map read . words) getLine

toPair :: [Int] -> (Int, Int)
toPair [a,b] = (a,b)

solveCase :: Int -> IO ()
solveCase _ = do
    [_, q] <- getInts
    heights <- getInts
    queries <- forM [1..q] (\_ -> liftM toPair getInts)
    let answer = solve heights queries
    forM_ answer (\a -> print a)

main = do
    c <- getInt
    forM_ [1..c] solveCase


    7년 전
4개의 댓글이 있습니다.
  • codeonwort
    codeonwort

    String 즉 [Char] 타입을 다루는 getLine과 read는 메모리 사용량과 실행 속도 면에서 퍼포먼스가 매우 구립니다. n이 10만 이상이면 거의 입력 받다가 시간 초과한다고 보시면 됩니다.

    대개 정수나 ASCII 문자만 입력받는 알고리즘 문제의 경우 ByteString 버전 getLine과 read를 사용하면 입력 읽는 것이 엄청 빨라집니다. 저는 이런 형태를 주로 씁니다.

    import Data.Maybe
    import qualified Data.ByteString as BS
    import qualified Data.ByteString.Char8 as BS8

    -- 숫자 하나만 읽는 건 상관 없음
    getInt = read fmap getLine :: IO Int

    -- 긴 배열 읽을 때는 ByteString 사용
    getInts = (map parseInt . BS8.words) fmap BS.getLine :: IO [Int]
    parseInt = fst . fromJust . BS8.readInt

    그리고 하스켈의 장점인 지연 평가가 알고리즘 문제에서는 오히려 독이 되는데요. 트리를 아예 완전히 평가한 다음 쿼리를 날리는 것이 좋습니다.

    Control.DeepSeq 모듈의 force와 Control.Exception 모듈의 evaluate 함수를 이용하면 됩니다. 단 직접 정의하신 트리 타입을 NFData의 인스턴스로 만들어야 합니다.


    7년 전 link
  • codeonwort
    codeonwort

    채점 통과한 코드입니다.

    -- Algospot (https://algospot.com)
-- ID:  MORDOR
-- URL: https://algospot.com/judge/problem/read/MORDOR

import Control.Monad
import Control.DeepSeq
import Control.Exception
import Data.Maybe
import qualified Data.ByteString as BS
import qualified Data.ByteString.Char8 as BS8

getInt = read `fmap` getLine :: IO Int
getInts = (map parseInt . BS8.words) `fmap` BS.getLine :: IO [Int]
parseInt = fst . fromJust . BS8.readInt

main = getInt >>= \n -> replicateM_ n solve

solve = do
    [n,q] <- getInts
    heights <- getInts
    let tree = buildTree heights n
    evaluate (force tree)
    replicateM_ q $ do
        range@[a,b] <- getInts
        let (low,high) = query tree range
        print $ high - low

-- left bound, right bound, minimum and maximum value in the range
type NodeData = (Int, Int, Int, Int)

data SegTree = Empty | Node NodeData SegTree SegTree
instance NFData SegTree where
    rnf (Node a b c) = rnf a `seq` rnf b `seq` rnf c
    rnf Empty = ()
rangeMin (Node (_,_,x,_) _ _) = x
rangeMax (Node (_,_,_,x) _ _) = x

buildTree :: [Int] -> Int -> SegTree
buildTree nums n = f nums (0,n-1) where
    f [x] (l,r) = Node (l,r,x,x) Empty Empty
    f xs (l,r) = Node (l,r,minLR,maxLR) ltree rtree where
        mid = (l + r) `div` 2
        half = mid - l + 1
        ltree = f (take half xs) (l,mid)
        rtree = f (drop half xs) (mid+1,r)
        minLR = min (rangeMin ltree) (rangeMin rtree)
        maxLR = max (rangeMax ltree) (rangeMax rtree)

query :: SegTree -> [Int] -> (Int, Int)
query Empty _ = (20000 + 10, -1)
query (Node (rangeL, rangeR, minValue, maxValue) ltree rtree) range@[l,r]
    | r < rangeL || rangeR < l = (20000 + 10, -1)
    | l <= rangeL && rangeR <= r = (minValue, maxValue)
    | otherwise = (min minL minR, max maxL maxR)
    where
        (minL, maxL) = query ltree range
        (minR, maxR) = query rtree range


    7년 전 link
  • jwvg0425
    jwvg0425

    @codeonwort 감사합니다. 덕분에 수정해서 통과했습니다 ㅜㅜ 거의 비슷하게 코드 바꿨는데 그래도 통과 안 돼서 끙끙대다가 length xs로 구하던 끝 길이를 n 입력 받은거 쓰게 바꾸니까 통과가 되네요. length도 안 쓰는게 좋다는 것까지 추가로 배우고 갑니다.


    7년 전 link
  • riceluxs1t
    riceluxs1t

    최근 펑서녈 프로그래밍에 관심이 많은데 하스켈로 푸는 분들이 계셨군요..


    7년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.