Speed ​​up partitioning in Haskell

Question

I am trying to solve the Euler 78 problem, which basically asks for the first number, where the function > p (n) is divided by 1,000,000.

I use the recursive Euler function based on pentagonal numbers (calculated here in pents along with the corresponding sign). Here is my code:

 ps = 1 : map p [1..] where pn = sum $ map getP $ takeWhile ((<= n).fst) pents where getP (pent,sign) = sign * (ps !! (n-pent)) pents = zip (map (\n -> (3*n-1)*n `div` 2) $ [1..] >>= (\x -> [x,-x])) (cycle [1,1,-1,-1]) 

While ps seems to give the correct results, it is too slow. Is there a way to speed up the calculation or do I need a completely different approach?

Answer 1

xs !! n xs !! n has linear complexity. You should try to use a logarithmic data structure or data with constant access.

Edit: here is a quick implementation that I came across by copying augustss-like :

 psOpt x = psArr x where psCall 0 = 1 psCall n = sum $ map getP $ takeWhile ((<= n).fst) pents where getP (pent,sign) = sign * (psArr (n-pent)) psArr n = if n > ncache then psCall n else psCache ! n psCache = listArray (0,ncache) $ map psCall [0..ncache] 

In ghci, I don't see impressive acceleration over your version of the list. Bad luck!

Edit: Indeed, with -O2 , as Chris Kuklevich suggested, this solution is eight times faster than yours for n=5000 . In combination with Hammar's understanding of the sum of the sums modulo 10 ^ 6, I get a solution that is fast enough (you can find the correct answer to our device in 10 seconds):

 import Data.List (find) import Data.Array ps = 1 : map p [1..] where pn = sum $ map getP $ takeWhile ((<= n).fst) pents where getP (pent,sign) = sign * (ps !! (n-pent)) summod li = foldl (\ab -> (a + b) `mod` 10^6) 0 li ps' = 1 : map p [1..] where pn = summod $ map getP $ takeWhile ((<= n).fst) pents where getP (pent,sign) = sign * (ps !! (n-pent)) ncache = 1000000 psCall 0 = 1 psCall n = summod $ map getP $ takeWhile ((<= n).fst) pents where getP (pent,sign) = sign * (psArr (n-pent)) psArr n = if n > ncache then psCall n else psCache ! n psCache = listArray (0,ncache) $ map psCall [0..ncache] pents = zip (map (\n -> ((3*n-1)*n `div` 2) `mod` 10^6) $ [1..] >>= (\x -> [x,-x])) (cycle [1,1,-1,-1]) 

(I broke the abstraction of psCache, so you should use psArr instead of psOpt , which ensures that another call to psArr will reuse the same memoized array. This is useful when you write find ((== 0) . ...) .. I thought it’s better not to publish the complete solution.)

Thanks to everyone for the additional tips.

Answer 2

So, one remark is that since you are only interested in map (`mod` 10^6) ps , you can avoid the need to do calculations on huge numbers.

Answer 3

I did not do this Euler problem, but usually with Euler problems there is a smart trick to speed up the calculation.

When I see this:

 sum $ map getP $ takeWhile ((<=n).fst) pents 

I can't help but think that there should be a smarter way than invoking sum . map getP sum . map getP every time you compute a ps element.

Now, when I look at this ... would it not be faster to do the sum first, and then multiply, and not do the multiplication (inside getP ) for each element, and then the sum?

I would usually look more deeply and provide working code; but this is Euler’s problem (I would not want to spoil it!), so I’ll just stay here with these little thoughts.

Answer 4

Inspired by your question, I used your approach to solve Euler 78 with Haskell. So I can give you some performance tips.

Your pet list cache should be good as it is.

Select some maxN to bind the search (pn).

The plan is to use (Array Int64 Integer) to store the result (pn) with a lower bound of 0 and an upper bound of maxN. This requires an array definition in terms of "p" and "p" in terms of an array, they are mutually recursively defined:

Override (pn) to (pArray n) to search for recursive calls to "p" in array A.

Use the new pArray with Data.Array.IArray.listArray to create an array A.

Definitely compiled with 'ghc -O2'. This is done in 13 seconds.