Haskell: код работает слишком медленно
У меня есть код, который вычисляет число Моцкина как:
module Main where
-- Program execution begins here
main :: IO ()
main = interact (unlines . (map show) . map wave . (map read) . words)
-- Compute Motzkin number
wave :: Integer -> Integer
wave 0 = 1
wave 1 = 1
wave n = ((3 * n - 3) * wave (n - 2) + (2 * n + 1) * wave (n - 1)) `div` (n + 2)
Но вывод даже для простого числа, как 30 требуется время, чтобы вернуться.
Есть идеи по оптимизации??
4 ответа
Существует стандартный прием для вычисления чисел Фибоначчи, который можно легко адаптировать к вашей задаче. Наивное определение чисел Фибоначчи таково:
fibFunction :: Int -> Integer
fibFunction 0 = 1
fibFunction 1 = 1
fibFunction n = fibFunction (n-2) + fibFunction (n-1)
Однако это очень дорого: так как все листья рекурсии 1, если fib x = yтогда мы должны выполнить y рекурсивные звонки! Так как числа Фибоначчи растут в геометрической прогрессии, это плохое положение дел. Но с динамическим программированием мы можем разделить вычисления, необходимые в двух рекурсивных вызовах. Приятный однострочник для этого выглядит так:
fibList :: [Integer]
fibList = 1 : 1 : zipWith (+) fibList (tail fibList)
Поначалу это может показаться немного странным; здесь fibList аргумент zipWith служит рекурсией по двум показателям назад, тогда как tail fibList Аргумент служит рекурсией для одного индекса назад, что дает нам обоим fib (n-2) а также fib (n-1) ценности. Два 1в начале, конечно, базовые случаи. Здесь есть и другие хорошие вопросы, которые объясняют эту технику более подробно, и вы должны изучать этот код и эти ответы, пока не почувствуете, что не понимаете, как он работает и почему он очень быстрый.
При необходимости можно восстановить Int -> Integer введите подпись из этого с помощью (!!),
Давайте попробуем применить эту технику к вашей функции. Как и при вычислении чисел Фибоначчи, вам нужны предыдущие и предпоследние значения; и дополнительно нужен текущий индекс. Это можно сделать, включив [2..] в призыве к zipWith, Вот как это будет выглядеть:
waves :: [Integer]
waves = 1 : 1 : zipWith3 thisWave [2..] waves (tail waves) where
thisWave n back2 back1 = ((3 * n - 3) * back2 + (2 * n + 1) * back1) `div` (n + 2)
Как и прежде, можно восстановить версию функции с помощью (!!) или же genericIndex (если действительно нужно Integer индексы). Мы можем подтвердить, что он вычисляет ту же функцию (но быстрее и использует меньше памяти) в ghci:
> :set +s
> map wave [0..30]
[1,1,2,4,9,21,51,127,323,835,2188,5798,15511,41835,113634,310572,853467,2356779,6536382,18199284,50852019,142547559,400763223,1129760415,3192727797,9043402501,25669818476,73007772802,208023278209,593742784829,1697385471211]
(6.00 secs, 3,334,097,776 bytes)
> take 31 waves
[1,1,2,4,9,21,51,127,323,835,2188,5798,15511,41835,113634,310572,853467,2356779,6536382,18199284,50852019,142547559,400763223,1129760415,3192727797,9043402501,25669818476,73007772802,208023278209,593742784829,1697385471211]
(0.00 secs, 300,696 bytes)
При n=30 вам нужно вычислить wave 29 а также wave 28который, в свою очередь, должен вычислить wave 28, wave 27 дважды и wave 26 и так далее, это быстро уходит в миллиарды.
Вы можете использовать тот же трюк, который используется при вычислении чисел Фибоначчи:
wave 0 = 1
wave 1 = 1
wave n = helper 1 1 2
where
helper x y k | k <n = helper y z (k+1)
| otherwise = z
where z = ((3*k-3) * x + (2*k+1) * y) `div` (k+2)
Это работает за линейное время, и помощник, для каждого k значения для wave (k-2) а также wave (k-1) готовы.
Вот памятная версия
wave = ((1:1:map waveCalc [2..]) !!)
where waveCalc n = ( (2*n+1)*wave (n-1) + (3*n-3)*wave (n-2) ) `div` (n+2)
Спасибо всем за ваши ответы. Основываясь на моем понимании MemoizationЯ переписал код как:
mwave :: Int -> Int
mwave = (map wave [0..] !!)
where wave 0 = 1
wave 1 = 1
wave n = ((3 * n - 3) * mwave (n - 2) + (2 * n + 1) * mwave (n - 1)) `div` (n + 2)
digits :: Int -> Int
digits n = (mwave n) `mod` 10^(100::Int)
Есть мысли о том, как вывести ответ по модулю 10^100?