performance - 加速 Haskell 中的分区计算

Question

我正在尝试解决欧拉问题 78，它基本上要求 partition function 所在的第一个数字p(n) 可以被 1000000 整除。

我使用基于五边形数的欧拉递归公式(在 pents 中计算，连同正确的符号)。这是我的代码:

ps = 1 : map p [1..] where
  p n = 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])

而 ps似乎产生了正确的结果，它太慢了。有没有办法加快计算速度，还是我需要一种完全不同的方法？

Answer 1

xs !! n具有线性复杂度。您应该尝试使用对数或常量访问数据结构。

编辑:这是我通过复制 a similar one by augustss 提出的快速实现:

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]

在 ghci 中，我观察到您的列表版本没有明显的加速。没运气 !

编辑:
确实，使用 -O2正如 Chris Kuklewicz 所建议的那样，此解决方案比您的 n=5000 快八倍.结合 Hammar 对 10^6 求和的见解，我得到了一个足够快的解决方案(在我的机器上大约 10 秒内找到希望正确的答案):

import Data.List (find)
import Data.Array 

ps = 1 : map p [1..] where
  p n = sum $ map getP $ takeWhile ((<= n).fst) pents where
    getP (pent,sign) = sign * (ps !! (n-pent)) 

summod li = foldl (\a b -> (a + b) `mod` 10^6) 0 li

ps' = 1 : map p [1..] where
  p n = 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])

(我破坏了 psCache 抽象，所以你应该使用 psArr 而不是 psOpt ；这可以确保对 psArr 的不同调用将重用相同的内存数组。这在你编写 find ((== 0) . ...) 时很有用......好吧，我认为最好不要发布完整的解决方案。)

感谢大家的额外建议。