Haskell记忆码与阶乘n的尾随零数

Question

我试图解决代码战问题，称为：N的尾随零的数量！和哈斯克尔。我知道我不需要计算阶乘来知道尾随零，事实上我只是计算有多少个数字可以被5整除，以及每个数字可以被5整除多少次。我写了两个版本，一个版本在对一个数字进行去噪时使用回忆录，以得到可以被5整除的次数，另一个版本不使用回忆录。令我惊讶的是，假设的DP方法比普通的递归方法耗时更长。我可能在代码中做了一些非常愚蠢的事情。

以下是功能：

zeros x = helperZeros [1..x]
helperZeros :: [Integer] -> Integer
helperZeros  = sumArrayTuple . filter (\x -> x `mod` 5 == 0)
sumArrayTuple = foldl (\acc x -> acc + (fastDef x)) 0
data Tree a = Tree (Tree a) a (Tree a)
instance Functor Tree where
  fmap f (Tree l m r) = Tree (fmap f l) (f m) (fmap f r)
index :: Tree Integer -> Integer -> Integer
index (Tree _ m _) 0 = m
index (Tree l _ r) n = case (n-1) `divMod` 2 of
  (q,0) -> index l q
  (q,1) -> index r q
nats = go 0 1
  where
    go n s = Tree (go l s') n (go r s' )
      where
        l = n + s
        r = l + s
        s' = s * 2
fastDef:: Integer -> Integer
fastDef x = trace (show x) index memTreetDef x
memTreetDef = fmap (defact fastDef) nats
defact f n
  | n `mod` 5 /= 0 = 0
  | otherwise =  1 + f (n `div` 5)



zeros' x = helperZeros' [1..x]
helperZeros' :: [Integer] -> Integer
helperZeros'  = sumArrayTuple' . filter (\x -> x `mod` 5 == 0)
sumArrayTuple' = foldl (\acc x -> acc + (def x)) 0
def n
  | n `mod` 5 /= 0 = 0
  | otherwise = 1 + def (n `div` 5)

我试图记下的是默认函数的结果，例如，如果我已经计算了默认值200，那么它会重用这个结果来计算默认值1000。

我对哈斯克尔的DP相当陌生。

Answer 1

如果您在此处使用trace和show测试代码性能，这就是问题所在：它们与主代码相比非常慢。否则，变体的性能必须大致相同。

def功能不适合记忆。递归的平均深度与1相差不大。其余的复杂度降低到操作mod，也就是说，除法几乎不比查表更昂贵（常数除法可以优化为乘法）。