Почему моя программа haskell слишком медленная?

Question

Я попытался решить задачу 443 на ProjectEuler, https://projecteuler.net/problem=443.

Чтобы найти образец г, я просто реализован г в Haskell, как

g::Int->Int 
g 4=13 
g n=g (n-1)+n `gcd` g(n-1) 

Но вычисляя список t=[g i|i<-[4..100]] занимает гораздо больше, чем на 1 секунду. Почему это происходит? Даже без воспоминаний для каждого g (n) требуется только O (n).

Редактировать: когда я пробовал этот код в ideone, все в порядке, но на моем компьютере это не так. Это проблема с версией haskell? Я использую версию ghc 7.8.3 для Windows, тогда как ideone использует ghc 7.6.

Answer 1

он принимает только O (N) для каждого g (n)

Не совсем. В вашем случае рекурсивного

g n=g (n-1)+n `gcd` g(n-1) 

вы звоните gдважды. Это означает, что вы получаете экспоненциальное время выполнения (O(2n)).

Чтобы убедиться, что g (n-1) вычисляется только один раз в каждом шаге, используйте let или where заявление, так что вы можете обратиться к одному значению - результат одного вызова - дважды.

g :: Int -> Int 
g 4 = 13 
g n = let r = g (n-1) 
     in r + n `gcd` r 

, когда я попробовал этот код в ideone, это хорошо, но в моем компьютере это не так. Это проблема с версией haskell?

Возможно, хотя проблема с параметром уровня оптимизации довольно. Компилятор Haskell может оптимизировать такие функции, как ваш, когда он обнаруживает, что выражение (например, g (n-1)) появляется дважды, но поиск их является дорогостоящим и должен быть включен.

Answer 2

Если изменить определение g к: (., В отличие от ghc -O2)

g::Int->Int 
g 4=13 
g n=x+n `gcd` x 
    where x = g (n-1) 

я получить приемлемое время работать даже под ghci или runhaskell