Dec 2010
1 / 3
Dec 2010
Jul 2011
sheaf_
Dec '10

Hey,

I've been learning Haskell by trying to solve some of the problems here, but it seems that most of the time I end up getting TLEs.
For instance, I'm reasonably confident that my solution to INTEGMAX is good, except I'm not using any complicated IO code that would optimise it.
Similarly with ARMY, I don't think I can improve on it. I initially was having TLEs, but changing the IO code from normal IO to ByteStrings made it run in time. I wonder how some of the faster Haskell answers to ARMY might deal with the IO?
On WATER, I keep getting NZEC, no idea why. It runs fine on some of the large inputs I've tried. But I don't think the algorithm is too good, so I'm sort of expecting a TLE anyway. Edit: OK, I didn't realise there was an empty line between test cases. Now I get TLE. I guess that's sort of expected.
Also on BUGLIFE, I'm also using a somewhat slower algorithm, but I don't think it's much slower that it should be.

Can anyone give me some tips about how I could handle IO better, or if possible run some of my things and see how long they take on SPOJ, just to see how far off I am?

Here's how my IO works on, for example, WATER:

readInt :: BS.ByteString -> Int
readInt x =
  case BS.readInt x of Just (i,_) -> i
                       Nothing    -> error "Unparsable Int"
--Parser: takes k lines, and puts them into a grid
parseGrid :: [BS.ByteString] -> Grid
parseGrid s = (map (map readInt)).(map BS.words) $ s
--Parser. Input should be (a string of) integers, separated by spaces.
parseInt :: String -> [Int]
parseInt = (map read).words
printAnswer :: Int -> [BS.ByteString] -> IO()
printAnswer 0 _ = return()
printAnswer n (x:xs) = do    
    let (a:b:stuff) = (map readInt).BS.words $ x
    let s = take a xs
        rest = drop a xs
        l = parseGrid s
    print $ answer' (a,b,l)
    printAnswer (n-1) rest
main :: IO()
main = do
    [n] <- (fmap parseInt $ getLine)
    x <- (fmap BS.lines) BS.getContents
    printAnswer n x

Please be gentle, I just started out in Haskell! Sorry to be a hassle.

Thanks.

  • created

    Dec '10

  • last reply

    Jul '11
  • 2

    replies

  • 822

    views

  • 2

    users

  • 2

    links

gorlum0_sof
Dec '10

Hello sheaf_,

Not being haskell expert myself, but still.
IO looks fine. But haskell is.. well not straight. Some list transformations, lazyness (and strictness on demand) can make huge difference even if "general" algorithm is OK.
Try profiling. Also if you're learning haskell now and you're picking some "old" problem, check how much haskell solutions it got first. Or even start with few easy(?) problems, get to feel haskell first.

My ARMY IO part:

main = putStr . unlines . army . tail . BS.lines =<< BS.getContents

Had 0.96s AC before today with lazy BS. Changed just for fun to strict and got 0.68. As an example.
readInt = fst . fromJust . BS.readInt --offtopic, my readInt. imo looks prettier stuck_out_tongue

INTEGMAX's 5.. best solutions all are >=0.3s and they're in C/C++ and 1s time limit. 1:3 - quite tight.
Can't say anything about BUGLIFE.

In general even if after haskell wiki spoj page you may want use some really complicated optimizations, in my (small) experience basic BS' usage is enough (again if time limit is not that bad and your haskell code is fine). And yeah - there you can find some nice code samples. E.g. http://www.haskell.org/haskellwiki/Primes6 page. Or http://www.haskell.org/haskellwiki/Memoization3 page. Project euler solutions also count.. but you'd better check them after you solve not before.)

6 months later
sheaf_
Jul '11

OK, back in the game now.

Thanks for the advice, I've been trying some profiling, and every time it seems that it is indeed IO that causes the problem.

For instance, my solution to Matrix Game I think follows a fast algorithm, but then is considerably slowed down with the IO. The profiler says that 96% of runtime is dedicated to the IO. At the moment, this is almost exclusively down to the bit of code that reads the matrices from the input and makes them into lists of integers. The following seems to account for 90% of run time, please point out any blunders that would be slowing it down considerably: (Matrix is of type [[Int]])

--Processes a matrix block with b rows from input, returning the matrix
procBlock :: Int -> IO(Matrix)
procBlock 0 = return []
procBlock b = do
	line <- BS.getLine
	let vect = map readInt $ BS.words line 
	liftM2 (:) (return vect) (procBlock (b-1))

In particular, the readInt seems to be taking a third of that 90%, it's still defined just as above. All this is using strict bytestrings.

Feel free to bash me unreservedly.