Haskell: Почему моя реализация последовательности Фибоначчи неэффективна?

Я написал следующую программу воспроизведения Фибоначчи как часть изучения Haskell:

fibonacci 0 = [0]       
fibonacci 1 = [0,1]          
fibonacci n = let   
                foo'1 = last (fibonacci (n-1))
                foo'2 = last (fibonacci (n-2))
              in  reverse((foo'1 + foo'2):reverse (fibonacci (n-1)))

Программа работает:

ghci>fibonacci 6
[0,1,1,2,3,5,8]

Но производительность падает экспоненциально с n. Если я дам ему аргумент 30, он запустится примерно через минуту, в отличие от мгновенного запуска в 6. Кажется, ленивое выполнение сжигает меня, и фибоначчи запускается один раз для каждого элемента в окончательном списке.

Я делаю что-то глупое или что-то упускаю?

(Я уже избавился от ++, думая, что это может быть сделано)


memoization haskell fibonacci
person Ray Salemi    schedule 28.12.2014    source источник
comment
Это похоже на пример из учебника, где memoization становится полезным.   -  person icktoofay    schedule 29.12.2014
comment
Вы делаете три рекурсивных вызова, тогда как одного было бы достаточно. Я бы написал reverseFib, чтобы вернуть числа Фибоначчи в обратном направлении, так как это проще. Как только это будет определено, вы можете определить fibonacci = reverse . reverseFib, чтобы вы переворачивали список только один раз в конце. (Конечно, в Haskell есть и другие известные подходы, например, рекурсия по спискам вместо функций... но пока забудьте об этом)   -  person chi    schedule 29.12.2014
comment
Я думаю, что ключевым моментом здесь является запоминание, так как я продолжаю пересчитывать список каждый раз, когда хочу сослаться на одного из участников. Я проверю это! (Ха! Я вижу, рекурсивный пример использует последовательность Фибоначчи).   -  person Ray Salemi    schedule 29.12.2014

Ответы (3)


arrow_upward
5
arrow_downward

Как указано в комментариях, ваш подход немного сложен. В частности, вам не нужно использовать рекурсивные вызовы или даже функцию reverse для генерации последовательности Фибоначчи.

Реализация с линейным временем

В дополнение к вашему собственному ответу, вот однострочный учебник, в котором используется мемоизация:

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Если у вас есть fibs, написание функции fib становится тривиальной задачей:

fib :: Int -> [Integer]
fib n
    | n < 0     = error "fib: negative argument"
    | otherwise = take (n+1) fibs

Эта реализация fib имеет сложность Θ(n), которая, очевидно, намного лучше, чем Θ(exp(n)).

Тест в GHCi

λ> :set +s
λ> fib 6
[0,1,1,2,3,5,8]
(0.02 secs, 7282592 bytes)
λ> fib 30
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040]
(0.01 secs, 1035344 bytes)

Как видите, fib 30 на моей машине вычисляется менее чем за минуту.

дальнейшее чтение

Для получения более подробной информации о том, как генерировать последовательность Фибоначчи в Haskell, я отсылаю вас к этому haskell.org. вики

person jub0bs    schedule 29.12.2014
comment
Это элегантно! Ух ты. - person Ray Salemi; 29.12.2014

arrow_upward
1
arrow_downward

Вот ответ на вопрос с использованием указателя @icktoofay на memoization. Ответ включал функцию, которая быстро возвращала заданное число Фибоначчи, поэтому я использовал их пример для создания решения моей первоначальной проблемы — создания списка чисел Фибоначчи до запрошенного числа.

Это решение запускается почти мгновенно (у страницы есть дополнительное преимущество, поскольку мой подход называется «наивным»)

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
   where fib 0 = 0
         fib 1 = 1
         fib n = memoized_fib (n-2) + memoized_fib (n-1)

fib 0 = [0]
fib 1 = [0,1]
fib n = reverse ((memoized_fib (n-2) + memoized_fib(n-1)) : reverse (fib (n-1)))
person Ray Salemi    schedule 29.12.2014
comment
Эх... у этого старого PERL-мозга проблемы со сменой парадигмы. (Хороший!) - person Ray Salemi; 30.12.2014
comment
не как это сделать, а что это такое... это наводит меня на мысль: reverse действительно нужно было назвать reversed. проверьте также inits и tails из Data.List, если вы еще этого не сделали. :) - person Will Ness; 31.12.2014

arrow_upward
1
arrow_downward

Вам не нужно добавлять мемоизацию к вашей функции — она уже имеет все предыдущие результаты, создавая список. Вам просто нужно перестать игнорировать эти результаты, как вы это делаете сейчас, используя last.

Прежде всего, если более естественно строить список в обратном порядке, нет причин не делать этого:

revFib 0 = [0]       
revFib 1 = [1,0]          
revFib n | n > 0 = let  f1 = head (revFib (n-1))
                        f2 = head (revFib (n-2))
                   in  f1 + f2 : revFib (n-1)

Это по-прежнему медленно, так как мы по-прежнему игнорируем все предыдущие результаты, кроме самого последнего, расположенного в начале списка. Мы можем перестать это делать,

revFib 0 = [0]       
revFib 1 = [1,0]          
revFib n | n > 0 = let  f1 = head (revFib (n-1))
                        f2 = head (tail (revFib (n-1)))
                   in  f1 + f2 : revFib (n-1)

а затем мы назовем общее подвыражение, чтобы оно было общим для всех его применений и вычислялось только один раз:

revFib 0 = [0]       
revFib 1 = [1,0]          
revFib n | n > 0 = let  prevs = revFib (n-1)
                        [f1,f2] = take 2 prevs
                   in  f1 + f2 : prevs

и внезапно она становится линейной, а не экспоненциальной.

person Will Ness    schedule 31.12.2014