Haskell Memoization Codewars Количество конечных нулей факториала n

Question

Я пытаюсь решить проблему Codewars: Number of trailing нули N! с Haskell. Я знаю, что мне не нужно вычислять факториал, чтобы знать конечные нули, и на самом деле я просто подсчитываю, сколько много чисел делится на 5 и сколько раз для каждого. Я написал 2 версию, которая использует memoization при деактивации числа, чтобы получить, сколько раз делится на 5 и другое, которое не использует memoization. Меня удивляет то, что предполагаемый подход 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) 

То, что я пытаюсь memoize является результатом функции defact, например, если я уже вычислить defact 200, то было бы повторно использовать этот результат для расчета defact 1000 .

Я довольно новый для DP в Haskell.

Answer 1

Если вы протестировали свой код с trace и show здесь, то есть проблема: они очень медленны по сравнению с основным кодом. Если нет, производительность вариантов должна быть примерно одинаковой.

Функция def является плохим кандидатом на замещение. Средняя глубина рекурсии не сильно отличается от 1. Остальная сложность сводится к операции mod, т. Е. Деление, которое вряд ли дороже, чем поиск таблицы (и деление на константу может быть оптимизировано для умножения).