[Haskell-cafe]Prime Generator time limit exceeded

Jason Dagit dagit at codersbase.com
Thu Nov 2 13:44:51 EST 2006


On 11/2/06, Spencer Janssen <sjanssen at cse.unl.edu> wrote:
> On Nov 2, 2006, at 8:48 AM, alaiyeshi wrote:
> > Also, I guess my code still waste too much time "parsing" input (I
> > compiled my code with -prof flag on)...
> > Maybe ByteString may save me (or a smarter brain), What is your
> > opinion about doing faster IO, would you please tell me?
>
> ByteString will likely make this problem go faster, but sadly SPOJ
> doesn't have the FPS library or GHC 6.6.  My submission doesn't use
> any fancy IO tricks and manages to complete in 2.28 seconds.
>
> There is one major problem with your IO code.  get_contents will read
> every line of input before doing any other processing or output.
> This could potentially eat up a ton of memory, and thereby make your
> program slow.  A better approach is to interleave reading input and
> printing output.  Here is the input code from my submission:
>
> \begin{code}
> main = do
>      cases <- readLn
>      replicateM_ cases $ do
>          s <- getLine
>          let [m, n]     = map read $ words s
>         {- fill in the blank! -}
> \end{code}

Wouldn't this be the same as:
\begin{code}
main = do
  cases <- readLn -- probably don't need this anymore
  c <- getContents -- this should be lazy
  let ls = lines c  -- lazy too
  flip mapM_ ls $ \s -> do
    let [m, n] = map read $ words s
    {- fill in the blank! -}
\end{code}

Initially I was thinking this version might be preferable, but now I
see it's actually more lines  (although could be condensed).

Jason


More information about the Haskell-Cafe mailing list