加速Haskell中分区的计算

Question

我正在尝试解决Euler问题78,它基本上要求分区函数 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具有线性复杂度。您应该尝试使用对数或恒定访问数据结构。

编辑：这是我通过复制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 中，我没有观察到比您的列表版本有明显的加速。没有运气 ！

编辑： 确实，按照-O2Chris Kuklewicz 的建议，这个解决方案比你的 for 快八倍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) . ...)......好吧，我认为最好不要发布完整的解决方案。 ）

感谢大家的额外建议。