6

我正在尝试解决欧拉问题 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似乎产生了正确的结果，但它太慢了。有没有办法加快计算速度，还是我需要一种完全不同的方法？

4

4 回答 4

4

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 中，我观察到您的列表版本没有明显的加速。没运气 ！

编辑： 确实，-O2正如 Chris 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) . ...)......好吧，我认为最好不要发布完整的解决方案。 )

感谢大家的额外建议。

于 2011-04-25T16:25:42.037 回答
2

好吧，一个观察结果是，由于您只对 感兴趣map (`mod` 10^6) ps，您也许可以避免对大量数字进行计算。

于 2011-04-25T16:57:37.647 回答
1

我没有做过那个欧拉问题，但通常对于欧拉问题，有一个聪明的技巧可以加快计算速度。

当我看到这个：

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

我不禁认为必须有一种比sum . map getP每次计算ps.

现在我看了一下......先执行求和然后相乘，而不是getP对每个元素执行乘法（内部）然后求和，难道不是更快吗？

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

于 2011-04-25T18:42:52.460 回答
1

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

您缓存的 pent 列表应该是好的。

选择一些大数 maxN 来限制您对 (pn) 的搜索。

计划是使用 (Array Int64 Integer) 来记忆 (pn) 的结果，下限为 0，上限为 maxN。这需要用 'p' 定义数组，用数组定义 'p'，它们是相互递归定义的：

将 (pn) 重新定义为 (pArray n) 以查找对数组 A 中“p”的递归调用。

使用新的 pArray 和 Data.Array.IArray.listArray 创建数组 A。

绝对用'ghc -O2'编译。这在 13 秒内运行。

于 2011-04-26T08:53:16.483 回答