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

• jwvg0425

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

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

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

import Data.List

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

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


4년 전
##### 4개의 댓글이 있습니다.

• 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의 인스턴스로 만들어야 합니다.

4년 전

• codeonwort

채점 통과한 코드입니다.

-- Algospot (https://algospot.com)
-- ID:  MORDOR

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

4년 전

• jwvg0425

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

4년 전

• riceluxs1t

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

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