Haskell неэффективная реализация фибоначчи

Question

Я новичок в haskell и просто изучаю удовольствие от функционального программирования. но сразу же столкнулись с проблемой реализации функции фибоначчи. Пожалуйста, найдите код ниже.

--fibonacci :: Num -> [Num] 
fibonacci 1 = [1] 
fibonacci 2 = [1,1] 
--fibonacci 3 = [2] 
--fibonacci n = fibonacci n-1 
fibonacci n = fibonacci (n-1) ++ [last(fibonacci (n-1)) + last(fibonacci (n-2))] 

Довольно неудобно, я знаю. Я не могу найти время, чтобы посмотреть и написать лучшую. Хотя мне интересно, что делает это настолько неэффективным. Я знаю, что я должен посмотреть на это, просто надеясь, что кто-то почувствует необходимость быть педагогикой и избавит меня от усилий.

Answer 1

orangegoat's answer и Sec Oe's answer содержат ссылку, вероятно, лучшее место, чтобы узнать, как правильно написать последовательность Фибоначчи в Haskell, но вот некоторые не причин, почему ваш код неэффективен (обратите внимание, что ваш код не отличается от классического naive definition Элегантный Конечно Efficient Совершенство, нет.?.?):

Давайте рассмотрим, что происходит, когда вы звоните

fibonacci 5 

Это расширяет в

(fibonacci 4) ++ [(last (fibonacci 4)) + (last (fibonacci 3))] 

В дополнение к конкатенации двух списков вместе с ++, мы уже можем видеть, что одно место, мы неэффективным в том, что мы вычислим fibonacci 4дважды (два места мы назвали fibonacci (n-1). Но это становится хуже.

Везде говорит fibonacci 4, что расширяется в

(fibonacci 3) ++ [(last (fibonacci 3)) + (last (fibonacci 2))] 

И везде он говорит fibonacci 3, что расширяется в

(fibonacci 2) ++ [(last (fibonacci 2)) + (last (fibonacci 1))] 

Понятно, что это наивное определение имеет много повторных вычислений и это только ухудшается, когда n становится все больше и больше (скажем, 1000). fibonacci не является списком, он просто возвращает списки, поэтому он не собирается волновать воспоминания о результатах предыдущих вычислений.

Кроме того, используя last, вам необходимо перейти по списку, чтобы получить его последний элемент, который добавляет поверх проблем с этим рекурсивным определением (помните, что списки в Haskell не поддерживают постоянный случайный доступ во времени) они не являются динамическими массивами, это linked lists).

---

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

fibs = 0 : 1 : zipWith (+) fibs (tail fibs) 

Здесь fibs на самом деле список, и мы можем принять преимущество ленивой оценки Хаскелла для генерации fibs и tail fibs по мере необходимости, в то время как предыдущие вычисления все еще хранятся внутри фиб.И, чтобы получить первые пять номеров, это так просто, как:

take 5 fibs -- [0,1,1,2,3] 

(При желании можно заменить первую 0 с 1, если вы хотите, чтобы последовательность, чтобы начать с 1).

Answer 2

Все способы реализации последовательности Фибоначчи в Haskell просто перейдите по ссылке http://www.haskell.org/haskellwiki/The_Fibonacci_sequence

Answer 3

Эта реализация неэффективна, поскольку она выполняет три рекурсивных вызова. Если бы мы должны были написать рекуррентное соотношение для вычисления fibonacci n к нормальной форме (примечание, педантичные читателей: не whnf), это будет выглядеть так:

T(1) = c 
T(2) = c' 
T(n) = T(n-1) + T(n-1) + T(n-2) + c'' 

(Здесь c, c' и c'' некоторые константы, которые мы не знаю) Вот рецидив, который меньше:.

S(1) = min(c, c') 
S(n) = 2 * S(n-1) 

... но это повторение имеет приятный легкий замкнутую форму, а именно S(n) = min(c, c') * 2^(n-1): это экспоненциальный! Плохие новости.

Мне нравится общее представление о вашей реализации (т. Е. Отслеживание второго и последнего членов последовательности вместе), но вы падали рекурсивно, вызывая fibonacci несколько раз, когда это совершенно не нужно. Вот версия, которая исправляет эту ошибку:

fibonacci 1 = [1] 
fibonacci 2 = [1,1] 
fibonacci n = case fibonacci (n-1) of 
    all@(last:secondLast:_) -> (last + secondLast) : all 

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

Answer 4

Так что, даже если вы не знаете более эффективных способов, как вы могли бы улучшить свое решение?

Во-первых, глядя на подпись, кажется, вам не нужен бесконечный список, а список заданной длины. Это прекрасно, бесконечный материал может быть слишком сумасшедшим для вас прямо сейчас.

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

fibRev 0 = [] 
fibRev 1 = [1] 
fibRev 2 = [1,1] 
fibRev n = let zs@(x:y:_) = fibRev (n-1) in (x+y) : zs 

Вот как работает последний случай: мы получаем список, который один элемент короче и называют его zs. В то же время мы сопоставляем шаблон (x:y:_) (это использование @ называется as-pattern). Это дает нам первые два элемента этого списка. Чтобы вычислить следующее значение последовательности, нужно просто добавить эти элементы. Мы просто положили сумму (x+y) перед списком zs у нас уже есть.

Теперь у нас есть список фибоначчи, но он обратный. Нет проблем, просто использовать reverse:

fibonacci :: Int -> [Int] 
fibonacci n = reverse (fibRev n) 

reverse функция не так дорого, и мы называем его здесь только один раз.