Hi Guys, I'm new to Haskell and I was wondering if you can help me: One of the first program's I tend to write when I'm looking at a new language is a program to generate a list of perfect numbers: --My First Perfect Number Generator factors :: Integer -> [Integer] factors x = [z | z <- [1..x-1], x `mod` z == 0] is_perfect :: Integer -> Bool is_perfect x = if sum(factors x) == x then True else False do_perfect :: [Integer] -> [Integer] do_perfect x = [z |z <- x, is_perfect z ] Then to run it:
do_perfect [1..9000]
I'm using GHC to run it. My problem / question is this: It's running quite a lot slower than equivalent programs in erlang and python. I suspect it's down to the way I've written it. Any thoughts (or comments in general) Many thanks Matt ______________________________________________________________________ This email may contain privileged or confidential information, which should only be used for the purpose for which it was sent by Xyratex. No further rights or licenses are granted to use such information. If you are not the intended recipient of this message, please notify the sender by return and delete it. You may not use, copy, disclose or rely on the information contained in it. Internet email is susceptible to data corruption, interception and unauthorised amendment for which Xyratex does not accept liability. While we have taken reasonable precautions to ensure that this email is free of viruses, Xyratex does not accept liability for the presence of any computer viruses in this email, nor for any losses caused as a result of viruses. Xyratex Technology Limited (03134912), Registered in England & Wales, Registered Office, Langstone Road, Havant, Hampshire, PO9 1SA. The Xyratex group of companies also includes, Xyratex Ltd, registered in Bermuda, Xyratex International Inc, registered in California, Xyratex (Malaysia) Sdn Bhd registered in Malaysia, Xyratex Technology (Wuxi) Co Ltd registered in The People's Republic of China and Xyratex Japan Limited registered in Japan. ______________________________________________________________________
First step would probably be using Ints instead of Integers. On Thu, Oct 2, 2008 at 6:45 AM, Matthew Williams < Matthew_Williams@xyratex.com> wrote:
Hi Guys,
I'm new to Haskell and I was wondering if you can help me:
One of the first program's I tend to write when I'm looking at a new language is a program to generate a list of perfect numbers:
--My First Perfect Number Generator factors :: Integer -> [Integer] factors x = [z | z <- [1..x-1], x `mod` z == 0]
is_perfect :: Integer -> Bool is_perfect x = if sum(factors x) == x then True else False
do_perfect :: [Integer] -> [Integer] do_perfect x = [z |z <- x, is_perfect z ]
Then to run it:
do_perfect [1..9000]
I'm using GHC to run it. My problem / question is this: It's running quite a lot slower than equivalent programs in erlang and python. I suspect it's down to the way I've written it. Any thoughts (or comments in general)
Many thanks
Matt
______________________________________________________________________ This email may contain privileged or confidential information, which should only be used for the purpose for which it was sent by Xyratex. No further rights or licenses are granted to use such information. If you are not the intended recipient of this message, please notify the sender by return and delete it. You may not use, copy, disclose or rely on the information contained in it.
Internet email is susceptible to data corruption, interception and unauthorised amendment for which Xyratex does not accept liability. While we have taken reasonable precautions to ensure that this email is free of viruses, Xyratex does not accept liability for the presence of any computer viruses in this email, nor for any losses caused as a result of viruses.
Xyratex Technology Limited (03134912), Registered in England & Wales, Registered Office, Langstone Road, Havant, Hampshire, PO9 1SA.
The Xyratex group of companies also includes, Xyratex Ltd, registered in Bermuda, Xyratex International Inc, registered in California, Xyratex (Malaysia) Sdn Bhd registered in Malaysia, Xyratex Technology (Wuxi) Co Ltd registered in The People's Republic of China and Xyratex Japan Limited registered in Japan. ______________________________________________________________________
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
On Wed, Oct 1, 2008 at 22:25, wman <666wman@gmail.com> wrote:
First step would probably be using Ints instead of Integers.
Doesn't seem to make a real difference in GHCi. -- _jsn Prelude> do_perfect [1..2000] :: [Integer] [6,28,496] it :: [Integer] (4.22 secs, 169352736 bytes) Prelude> do_perfect [1..2000] :: [Int] [6,28,496] it :: [Int] (4.23 secs, 153699692 bytes)
factors :: Int -> [Int] factors x = [z | z <- [1..(x `div` 2)], x `mod` z == 0] is_perfect :: Int -> Bool is_perfect x = sum(factors x) == x do_perfect :: [Int] -> [Int] do_perfect x = [z |z <- x, is_perfect z ] main = print $ do_perfect [1..9000] -- compile with ghc -O2, it's more than ten times faster for me -- althought using 1..(x `div 2) instead of 1..x-1 is a bit of cheating ;-)) On Thu, Oct 2, 2008 at 6:45 AM, Matthew Williams < Matthew_Williams@xyratex.com> wrote:
Hi Guys,
I'm new to Haskell and I was wondering if you can help me:
One of the first program's I tend to write when I'm looking at a new language is a program to generate a list of perfect numbers:
--My First Perfect Number Generator factors :: Integer -> [Integer] factors x = [z | z <- [1..x-1], x `mod` z == 0]
is_perfect :: Integer -> Bool is_perfect x = if sum(factors x) == x then True else False
do_perfect :: [Integer] -> [Integer] do_perfect x = [z |z <- x, is_perfect z ]
Then to run it:
do_perfect [1..9000]
I'm using GHC to run it. My problem / question is this: It's running quite a lot slower than equivalent programs in erlang and python. I suspect it's down to the way I've written it. Any thoughts (or comments in general)
Many thanks
Matt
On Thu, 2008-10-02 at 05:45 +0100, Matthew Williams wrote:
Hi Guys,
I'm new to Haskell and I was wondering if you can help me:
One of the first program's I tend to write when I'm looking at a new language is a program to generate a list of perfect numbers:
--My First Perfect Number Generator factors :: Integer -> [Integer] factors x = [z | z <- [1..x-1], x `mod` z == 0]
Hi Matthew, A big optimization for larger numbers is that you only need to go up to the square root of x here and add both z and x/z to the list. (Where x is a perfect square you need to avoid adding the root twice.) It's late and there is probably a better way to do this, but: import List semi_factors :: Int -> [Int] semi_factors x = takeWhile (\n -> n * n <= x) [z | z <- [2..x-1], x `mod` z == 0] factors n = let xs = semi_factors n in nub (1 : (xs ++ (map (n `div`) xs)))
is_perfect :: Integer -> Bool is_perfect x = if sum(factors x) == x then True else False
"if <something> then True else False" should ring alarm bells! Immediately replace with simply "<something>": is_perfect x = sum (factors x) == x you could also use is_perfect x = foldl' (+) 0 (factors x) == x (strict foldl from Data.List)
do_perfect :: [Integer] -> [Integer] do_perfect x = [z |z <- x, is_perfect z ]
Then to run it:
do_perfect [1..9000]
I think more idiomatic would be: do_perfect x = filter is_perfect [2..x] All this speeds it up a bit. But I can't think any more - time to sleep. thanks Ben
I'm using GHC to run it. My problem / question is this: It's running
quite a lot slower than equivalent programs in erlang and python. I suspect it's down to the way I've written it. Any thoughts (or comments in general)
Many thanks
Matt
On 10/2/2008, "Ben Deane"
On Thu, 2008-10-02 at 05:45 +0100, Matthew Williams wrote:
Hi Guys,
I'm new to Haskell and I was wondering if you can help me:
One of the first program's I tend to write when I'm looking at a new language is a program to generate a list of perfect numbers:
--My First Perfect Number Generator factors :: Integer -> [Integer] factors x = [z | z <- [1..x-1], x `mod` z == 0]
Hi Matthew,
A big optimization for larger numbers is that you only need to go up to the square root of x here and add both z and x/z to the list. (Where x is a perfect square you need to avoid adding the root twice.) It's late and there is probably a better way to do this, but:
import List
semi_factors :: Int -> [Int] semi_factors x = takeWhile (\n -> n * n <= x) [z | z <- [2..x-1], x `mod` z == 0]
factors n = let xs = semi_factors n in nub (1 : (xs ++ (map (n `div`) xs)))
is_perfect :: Integer -> Bool is_perfect x = if sum(factors x) == x then True else False
"if <something> then True else False" should ring alarm bells! Immediately replace with simply "<something>":
is_perfect x = sum (factors x) == x
you could also use
is_perfect x = foldl' (+) 0 (factors x) == x
(strict foldl from Data.List)
do_perfect :: [Integer] -> [Integer] do_perfect x = [z |z <- x, is_perfect z ]
Then to run it:
do_perfect [1..9000]
I think more idiomatic would be:
do_perfect x = filter is_perfect [2..x]
All this speeds it up a bit. But I can't think any more - time to sleep.
thanks Ben
I'm using GHC to run it. My problem / question is this: It's running
quite a lot slower than equivalent programs in erlang and python. I suspect it's down to the way I've written it. Any thoughts (or comments in general)
Many thanks
Matt
This isn't really important for this application, because the numbers being factored are relatively small, but there are some inefficiencies in the factors function that Ben presented that are fairly easy to overcome. Here's my version: factors :: (Integral a) => a -> [a] factors n = let p1 = [x | x <- [1 .. floor $ sqrt $ fromIntegral n], n `mod` x == 0] p2 = map (div n) (tail p1) in p1 `concatNoDupe` (reverse p2) where concatNoDupe :: (Eq a) => [a] -> [a] -> [a] concatNoDupe [] ys = ys concatNoDupe [x] (y:ys) = if x == y then (y : ys) else (x : y : ys) concatNoDupe (x:xs) ys = x : (concatNoDupe xs ys) Since my two lists of factors are ordered, I can exploit this to avoid calling nub and instead call 'concatNoDupe' which is more efficient. The other thing I optimized was the creation of the list of potential factors. Ben's solution required the evaluation of a predicate for each element in the list. My solution simply computes the maximum value of the list up front. To demonstrate how these changes affect performance, when I run this on my computer: main = print $ sum $ concat $ map factors [1..80000] Matthew's version: 194 seconds Ben's version: 32 seconds My version: 1 second I don't mean to suggest that my version is optimal. I just want to point out that seemingly small changes to an algorithm can have large consequences. David
On Fri, 2008-10-03 at 09:20 -0800, David Frey wrote:
(a nice improvement to the perfect number code)
Nice followup David. I knew that there had to be a better way than nub. On one of my better days I might have spotted that removing duplicates from sorted lists is O(n) - this is one of the interview questions I used to use! Good spot on the predicate too. Ben
On Thu, Oct 2, 2008 at 12:45 AM, Matthew Williams
I'm using GHC to run it. My problem / question is this: It's running quite a lot slower than equivalent programs in erlang and python. I suspect it's down to the way I've written it. Any thoughts (or comments in general)
Although Ben's algorithm suggestions are wise (just test up to the square root and add the matching divisor), even without those improvements, I get huge speed-up just using Int instead of Integer and compiling with -O2 instead of using ghci. On my machine, just compiling it takes the time down from about 30 seconds to 4.5. Then switching to Int takes it down to 1.2 seconds. I guess maybe the Python interpreter is a bit more deft at this type of problem than the GHC interpreter. In case you're wondering, since you said you're new to Haskell, the Int type uses machine storage (like 'int' in C, with the same bound restrictions), whereas the Integer type is a bit more abstract and can increase without limit. That's why Integer is a bit more costly to calculate with. Another style tip: if your list comprehension is only used to filter out elements (like in your 'do_perfect' function), it's clearer to use the Prelude function 'filter': do_perfect = filter is_perfect Kurt
participants (6)
-
Ben Deane -
David Frey -
Jason Dusek -
Kurt Hutchinson -
Matthew Williams -
wman