[Haskell-cafe] Slow IO or bad code?
Hi
I am practicing writing code in haskell, by solving problems at this
site. http://spoj.pl.
The problem http://spoj.pl/problems/FASHION , is pretty simple.
1. Given two lists A,B , of N numbers, sort them and take sum of products.
i.e. Sum ai * bi
I wrote a code, but seems to give Time limit exceeded!
Beginning of CODE
loop t function
| t == 1 = do function
| otherwise = do { function; loop (t - 1) function }
prod [] [] = 0
prod (a:as) (b:bs) = a*b + prod as bs
to_int :: [String] - [Integer]
to_int [] = []
to_int (x:xs) = (read x) : to_int xs
doit = do
n - getLine
a - getLine
b - getLine
let la = to_int (words a);
lb = to_int (words b); in
print (prod la lb)
main = do
t - getLine
loop (read t) doit
END OF CODE
I would love to see if there is any improvement that can be done, to
the code ...
Thanks!
Vimal
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Slow IO or bad code?
j.vimal: Hi I am practicing writing code in haskell, by solving problems at this site. http://spoj.pl. The problem http://spoj.pl/problems/FASHION , is pretty simple. 1. Given two lists A,B , of N numbers, sort them and take sum of products. i.e. Sum ai * bi I wrote a code, but seems to give Time limit exceeded! We have a page for these SPOJ problems: http://haskell.org/haskellwiki/SPOJ#Techniques_for_dealing_with_problems_efficiently With bytestring IO, you can aim to be around the speed of OCaml or C++, according to the existing bytestring entries. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Slow IO or bad code?
* Vimal wrote:
Beginning of CODE
loop t function
| t == 1 = do function
| otherwise = do { function; loop (t - 1) function }
prod [] [] = 0
prod (a:as) (b:bs) = a*b + prod as bs
prod = sum . zipWith (*)
to_int :: [String] - [Integer]
to_int [] = []
to_int (x:xs) = (read x) : to_int xs
This is the slow part. Prelude.read ist really slow.
Futhermore use the recusion pattern again:
to_int = map read
doit = do
n - getLine
a - getLine
b - getLine
let la = to_int (words a);
lb = to_int (words b); in
print (prod la lb)
What is n used for?
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Slow IO or bad code?
@Donald: Thanks for the link. prod = sum . zipWith (*) This is the slow part. Prelude.read ist really slow. Futhermore use the recusion pattern again: to_int = map read What is n used for? @Lutz: Those are some nice tricks... Thanks! Now, the 'n' is for getting the number of numbers in the list. Which I don't need, since I had a way around it. I just had to skip that line... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Slow IO or bad code?
I wrote a code, but seems to give Time limit exceeded! ?? Your code writes 15 to stdout which is correct (with the example given on the page).. You have to explain what you mean by seems to give Time limit exceeded loop t function Does already exist. sequence $ replicate 10 function is a much shorter way :-) oor perhaps mapM_ [ function | i - [1..10] ] ) prod, to_int: You can both implement using higher order functions prod = sum . zipWith (*) to_int = map read Marc ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Slow IO or bad code?
On 8/9/07, Marc Weber [EMAIL PROTECTED] wrote: I wrote a code, but seems to give Time limit exceeded! ?? Your code writes 15 to stdout which is correct (with the example given on the page).. You have to explain what you mean by seems to give Time limit exceeded I think Vimal is referring to a message from SPOJ rather than the compiler. I.e. the program runs too slowly so it is rejected by the judging software. -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Slow IO or bad code?
Note that this code isn't more successful, clearly I have misunderstood one requirement : import qualified Data.ByteString.Char8 as B import Data.List (unfoldr) main = B.interact $ hot hot = B.unlines . map (B.pack . show) . processList . tail . unfoldr readInt1 readInt1 cs = do (n, cs') - B.readInt cs return (n, B.tail cs') processList [] = [] processList (x:xs) = (sum $ zipWith (*) men women) : processList rest where (men,r1) = splitAt x xs (women,rest) = splitAt x r1 -- Jedaï ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Slow IO or bad code?
On 8/9/07, Chaddaï Fouché [EMAIL PROTECTED] wrote: I get Wrong answer with the following code for the same problem... Is there something strange in this code : This problem description is not worded very well. You have to figure out the matching that maximizes the sum of hotnesses; you don't necessarily just do a sum . zipWith (*). -Brent ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Slow IO or bad code?
On 8/9/07, Brent Yorgey [EMAIL PROTECTED] wrote: On 8/9/07, Chaddaï Fouché [EMAIL PROTECTED] wrote: I get Wrong answer with the following code for the same problem... Is there something strange in this code : This problem description is not worded very well. You have to figure out the matching that maximizes the sum of hotnesses; you don't necessarily just do a sum . zipWith (*). Exactly. The description says: Company XYZ has done the work for you, and now do xxx. This confused me a lot :-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
