加速 Haskell 中的分区计算

发布于 2024-11-03 19:21:43 字数 568 浏览 6 评论 0原文

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

原文

I'm trying to solve Euler problem 78, which basically asks for the first number where the partition function p(n) is divisible by 1000000.

I use Euler's recursive fomula based on pentagonal numbers (calculated here in pents together with the proper sign). Here is my code:

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])

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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

水晶透心 2024-11-10 19:21:43

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 的解决方案快八倍。结合哈马尔对模 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) ...)...好吧，我认为最好不要发布完整的解决方案。）

感谢大家的额外建议。

xs !! n has a linear complexity. You should rather try using a logarithmic or constant-access data structure.

Edit : here is a quick implementation I came up with by copying 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]

In ghci, I observe no spectacular speedup over your list version. No luck !

Edit :
Indeed, with -O2 as suggested by Chris Kuklewicz, this solution is eight times faster than your for n=5000. Combined with Hammar insight of doing sums modulo 10^6, I get a solution that is fast enough (find the hopefully correct answer in about 10 seconds on my machine):

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])

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

Thanks to all for the additional advice.

回复收藏 0 原文

风月客 2024-11-10 19:21:43

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

回复收藏 0 原文

故笙诉离歌 2024-11-10 19:21:43

我还没有做过欧拉问题，但通常在欧拉问题中都有一个巧妙的技巧来加速计算。

当我看到这一点时：

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

我不禁想到一定有比调用 sum 更聪明的方法。每次计算 ps 的元素时都会映射 getP。

现在我看看它......先执行求和，然后乘法不是比对每个元素执行乘法（在 getP 内部）然后再执行乘法更快吗？总结？

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

I haven't done that Euler problem, but usually with Euler problems there is a clever trick to speed up the calculation.

When I see this:

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

I can't help but think there must be a smarter way than to invoke sum . map getP every time you compute an element of ps.

Now that I look at it...wouldn't it be faster to perform the sum first, and then multiply, rather than performing the multiply (inside of getP) for every element and then summing?

Normally I'd take a deeper look and provide working code; but it's an Euler problem (wouldn't want to spoil it!), so I'll just stop here with these few thoughts.

回复收藏 0 原文