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

  • User Avatar
    jwvg0425

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

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

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


    ~~~ 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
    let answer = solve heights queries
    forM_ answer (\a -> print a)

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


    9년 전
4개의 댓글이 있습니다.
  • User Avatar
    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의 인스턴스로 만들어야 합니다.


    9년 전 link
  • User Avatar
    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 = 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
    ```


    9년 전 link
  • User Avatar
    jwvg0425

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


    9년 전 link
  • User Avatar
    riceluxs1t

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


    9년 전 link

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