我正在尝试解决欧拉问题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 似乎产生了正确的结果，但速度太慢了。有没有方法可以加快计算速度，或者我需要完全不同的方法？
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]
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])
好的，一个观察是，由于您只对map (`mod` 10^6) ps感兴趣，因此您可能可以避免对大数进行计算。
我还没有做过那个欧拉问题，但通常在欧拉问题中有一个聪明的技巧可以加速计算。
当我看到这个：
sum $ map getP $ takeWhile ((<=n).fst) pents
我忍不住想，肯定有比每次计算ps的元素时都调用 sum . map getP 更聪明的方法。
现在看起来...先进行求和，然后再相乘会更快，而不是为每个元素执行乘法（在getP内部），然后再求和？
通常情况下，我会仔细研究并提供可行的代码；但这是一个欧拉问题（不想剧透！），所以这里只停留在这几个思考上。
sign 对它们所有的值都是相同的，所以 cx+cy = c(x+y)，但实际上并不是这样。我的错误。使用 id 和 negate 可能比分别使用 *1 和 *-1 更快，尽管这只是一个微小的加速。 - Dan Burton