加快在Haskell中分区的计算

Question

我正在尝试解决欧拉问题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中，我观察到与列表版本相比没有显著的加速。不走运!

编辑:

实际上，对于Chris Kuklewicz建议的-O2，此解决方案比n=5000快8倍。结合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) . ...)…嗯，我认为最好不要发表完整的解决方案。

感谢所有人的额外建议。

Answer 2

好吧，一个观察是，由于您只对map (`mod` 10^6) ps感兴趣，您可能能够避免对大数进行计算。

Answer 3

我还没有做过那个欧拉问题，但通常在欧拉问题中有一个聪明的技巧来加快计算速度。

当我看到这个时:

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

我不禁想到，每次计算ps的一个元素时，一定有比调用sum . map getP更聪明的方法。

现在我看着它…首先执行求和，然后相乘，而不是对每个元素执行乘法(在getP中)，然后求和，不是更快吗?

通常我会更深入地研究并提供工作代码;但这是一个欧拉问题(我不想破坏它!)，所以我就在这里停止这些想法。

Answer 4

受您问题的启发，我使用您的方法用Haskell解决欧拉78。所以我可以给你一些性能提示。

你缓存的专利列表应该是好的。

选择一个较大的数字maxN来限定搜索(pn)。

计划是使用(Array Int64 Integer)来存储(p n)的结果，下界为0，上界为maxN。这要求用'p'定义数组，用'p'定义数组，它们是相互递归定义的:

将(p n)重新定义为(pArray n)以查找对数组a中'p'的递归调用

使用Data.Array.IArray.listArray创建数组a

肯定用'ghc -O2'编译。