Haskell Memoizationコードワードファクタリアルnの末尾の0の数

Question

コードワードの問題を解決しようとしています。Nの末尾のゼロの数。ハスケルと 私は、後続のゼロを知るために階乗を計算する必要はなく、実際には、どれだけ多くの数が5で割り切れるか、そしてそれぞれ何回であるかを数えていることを知っています。 私は2つのバージョンを書いています.1つは数値をデファクタリングして何回何回に分けられるかを知るためにメモを使用し、もう1つはメモを使用しません。 私にとって驚いたことに、仮定されたDPのアプローチは、些細な再帰的なアプローチよりも時間がかかります。私はおそらく私のコードで非常にばかげた何かをやっている。

これらは機能している：私はmemoizeしようとしています何

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) 

は、私はすでにdefact 200を計算している場合、それはdefact 1000年を計算し、この結果を再利用します例えば、defact関数の結果であります

私はハスケルでDPにかなり新しいです。

Answer 1

traceとshowでコードパフォーマンスをテストした場合、それは問題です。メインコードに比べて非常に遅いです。そうでない場合、変種のパフォーマンスはほぼ同じでなければなりません。

defの機能は、メモの作成には適していません。平均再帰深度は1とあまり変わりません。複雑さの残りの部分は、操作modに縮小されます。つまり、テーブルルックアップ（および除算を定数に分割することは乗算に最適化できます）よりもコストがかかりません。