Hello everyone, I am a newbie to Haskell coming from a Java/Scala/Ruby background. As first few exercises, I was trying to translate my Scala solutions for some Project Euler [1] problems to Haskell. The function that solves problem 4 turns out to be quite slow (6s in Haskell as opposed to 400ms in Scala) and I cannot understand why. Here's the function: euler4 = solve 100 999 where solve min max = maximum palindromes where palindromes = [n | a <- range, b <- range, let n = a * b, isPalindrome n] range = [max, max - 1 .. min] isPalindrome n = (n :: Int) == (read $ reverse $ show n) Using +RTS -sstderr I see that the allocation rate is 12M/s, which seems rather high to me. My guess would be that this is somehow related to lazy evaluation but all in all, I've got no real clue and would be thankful for any advice. Thank you Andreas [1] http://www.projecteuler.net
On Thursday 29 July 2010 00:29:56, Andreas Flierl wrote:
Hello everyone,
I am a newbie to Haskell coming from a Java/Scala/Ruby background. As first few exercises, I was trying to translate my Scala solutions for some Project Euler [1] problems to Haskell. The function that solves problem 4 turns out to be quite slow (6s in Haskell as opposed to 400ms in Scala) and I cannot understand why. Here's the function:
euler4 = solve 100 999 where solve min max = maximum palindromes where palindromes = [n | a <- range, b <- range, let n = a * b, isPalindrome n] range = [max, max - 1 .. min] isPalindrome n = (n :: Int) == (read $ reverse $ show n)
Try isPalindrome n = let s = show n in s == reverse s `read' is slow, though I didn't expect it to be that slow, to be honest. The above change brought time down from ~5.1 secs to 0.22 secs here. You can make it still faster if you make an arithmetic palindrome check instead of converting to String (0.1 secs). With algorithmic improvements more can be gained.
Using +RTS -sstderr I see that the allocation rate is 12M/s, which seems rather high to me. My guess would be that this is somehow related to lazy evaluation but all in all, I've got no real clue and would be thankful for any advice.
The problem (part of it at least) is that the Read instances for number types has been written more with elegance in mind than efficiency, apparently. Thus when you want to read an Int, first a generic number, possibly including a fractional part and an exponent or represented in base 8 or 16 is tried to be read. That number is read as an Integer or a Rational (depending on the presence of a fractional part and an exponent [and its value]). If the read produced an Integer, that is then converted to the appropriate number type [Int in this case]. That gives very elegant, but not very fast code.
Thank you Andreas
Cheers, Daniel
<Shameful plug>http://scrollingtext.org/project-euler-problem-4 to get the numeric check I had to do change the number to a list (to reverse it). module Main where import Data.List --Stole numberToList code from: --http://www.rhinocerus.net/forum/lang-functional/95473-converting-number-list... numberToList = reverse . unfoldr (\x -> if x == 0 then Nothing else let (a,b) = x `quotRem` 10 in Just (b,a)) is_palimdrome number = num_list == reverse num_list where num_list = numberToList number main :: IO () main = print . maximum $ [ x * y | x <- nums, y <- nums, is_palimdrome (x * y)] where nums = [1000,999..100] on my quadcore box w/ 3G of Ram the compiled code runs in .6 ms. I'm posting this to share my answer, but also to get any feed back on how I could make this code better. Bryce On 07/28/2010 04:33 PM, Daniel Fischer wrote:
On Thursday 29 July 2010 00:29:56, Andreas Flierl wrote:
Hello everyone,
I am a newbie to Haskell coming from a Java/Scala/Ruby background. As first few exercises, I was trying to translate my Scala solutions for some Project Euler [1] problems to Haskell. The function that solves problem 4 turns out to be quite slow (6s in Haskell as opposed to 400ms in Scala) and I cannot understand why. Here's the function:
euler4 = solve 100 999 where solve min max = maximum palindromes where palindromes = [n | a<- range, b<- range, let n = a * b, isPalindrome n] range = [max, max - 1 .. min] isPalindrome n = (n :: Int) == (read $ reverse $ show n)
Try
isPalindrome n = let s = show n in s == reverse s
`read' is slow, though I didn't expect it to be that slow, to be honest. The above change brought time down from ~5.1 secs to 0.22 secs here.
You can make it still faster if you make an arithmetic palindrome check instead of converting to String (0.1 secs).
With algorithmic improvements more can be gained.
Using +RTS -sstderr I see that the allocation rate is 12M/s, which seems rather high to me. My guess would be that this is somehow related to lazy evaluation but all in all, I've got no real clue and would be thankful for any advice.
The problem (part of it at least) is that the Read instances for number types has been written more with elegance in mind than efficiency, apparently. Thus when you want to read an Int, first a generic number, possibly including a fractional part and an exponent or represented in base 8 or 16 is tried to be read. That number is read as an Integer or a Rational (depending on the presence of a fractional part and an exponent [and its value]). If the read produced an Integer, that is then converted to the appropriate number type [Int in this case].
That gives very elegant, but not very fast code.
Thank you Andreas
Cheers, Daniel
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
<Shameful plug>http://scrollingtext.org/project-euler-problem-4
On Thursday 29 July 2010 02:02:04, Bryce Verdier wrote: plug> You wrote there: "If anyone knows of a way to run haskell interpretively, and without using ghci, please let me know." a) what's wrong with ghci? b) hugs [that is an interpreter only, no attached compiler]
to get the numeric check I had to do change the number to a list (to reverse it).
module Main where
import Data.List
--Stole numberToList code from: --http://www.rhinocerus.net/forum/lang-functional/95473-converting-numbe r-list-haskell.html numberToList = reverse . unfoldr (\x -> if x == 0 then Nothing else let (a,b) = x `quotRem` 10 in Just (b,a))
Here you're only interested in whether it's a palindrome, so the `reverse' is an unnecessary waste of time. Removing it doesn't gain much time, though.
is_palimdrome number = num_list == reverse num_list where num_list = numberToList number
main :: IO () main = print . maximum $ [ x * y | x <- nums, y <- nums, is_palimdrome (x * y)] where nums = [1000,999..100]
on my quadcore box w/ 3G of Ram the compiled code runs in .6 ms.
I hope that is a typo, it takes approximately 0.6 seconds here.
I'm posting this to share my answer, but also to get any feed back on how I could make this code better.
Without type signatures, the types default to Integer. Everything comfortably fits in an Int, so specifying the type as Int gives a small speedup (it's small because GHC special-cases small Integers and uses Int-arithmetic throughout here, but it must do some checks to see whether a large Integer is necessary, which can be avoided by using Int). Here at least, using let s = show n in s == reverse s is the much faster palindrome test. You can halve the running time by using the property x * y == y * x of multiplication. You can chop a further 10% off by eliminating multiples of 10 (which never give palindromes). You can make it much faster by considering only pairs which have a larger product than the largest palindrome found so far (that means you can't use such a simple list-comprehension, so if better code means shorter code, that won't be better). You can further speed it up by using a little math to find necessary conditions for x * y to be a (six-digit) palindrome. Alternatively, you can bring the runtime down by reversing your approach, instead of checking whether the product is a palindrome, check whether a palindrome can be written as a product of two three-digit numbers.
Thanks Daniel for the explanation, that was really helpful, and thanks Bryce for sharing your solution. I know that the algorithm itself can be improved vastly (especially interesting for bigger palindromes..) but here, I was only worried about the loss of speed after the more or less direct port from Scala to Haskell. But since the Haskell solution now runs 4 times faster than my previous Scala version, I'm happy. :) Thanks again Andreas
On Thu, Jul 29, 2010 at 2:02 AM, Bryce Verdier
main :: IO () main = print . maximum $ [ x * y | x <- nums, y <- nums, is_palimdrome (x * y)] where nums main :: IO ()
This version of main is faster for me. main :: IO () main = print . maximum $ [ x * y | x <- [100..1000], y <- [100..x], is_palimdrome (x * y)] David.
participants (4)
-
Andreas Flierl -
Bryce Verdier -
Daniel Fischer -
David Virebayre