мета-данные страницы
  •  
Загрузка не удалась. Возможно, проблемы с правами доступа?

Различия

Показаны различия между двумя версиями страницы.

Ссылка на это сравнение

Предыдущая версия справа и слеваПредыдущая версия
Следующая версия		Предыдущая версия
haskell:fibb [19/02/2014 18:40] – vlasovhaskell:fibb [15/10/2014 18:59] (текущий) – vlasov
Строка 5: Строка 5:
 <code haskell> <code haskell>
 fib :: Int -> Int fib :: Int -> Int
 +-- fib :: Integer -> Integer избыточно, так как не достигнем
 fib 1 = 1 fib 1 = 1
 fib 2 = 1 fib 2 = 1
Строка 17: Строка 18:
 Однако данный способ вычисления является хоть и простым, но крайне затратным, так как вынужден делать бинарное дерево ветвлений вычислений при рекурсивном спуске. При этом хотя все вычисления одинаковые, но они делаются независимо и вынуждены занимать всю доступную память. Таким образом, на некоторых компьютерах вычислить даже 40-й элементы последовательности является проблематичным, а 45-й, тем более 50-й вычислить нереально практически на всех доступных персональных компьютерах. Однако данный способ вычисления является хоть и простым, но крайне затратным, так как вынужден делать бинарное дерево ветвлений вычислений при рекурсивном спуске. При этом хотя все вычисления одинаковые, но они делаются независимо и вынуждены занимать всю доступную память. Таким образом, на некоторых компьютерах вычислить даже 40-й элементы последовательности является проблематичным, а 45-й, тем более 50-й вычислить нереально практически на всех доступных персональных компьютерах.
  
-Согласно сайту [[http://www.cubbi.org/serious/fibonacci/haskell.html|Внешняя ссылка]]+Согласно сайту [[http://www.cubbi.org/serious/fibonacci/haskell.html|cubbi.com: fibonacci numbers in haskell]] 
 +возможно улучшить даже бинарную рекурсию мемоизацией (кэшированием) промежуточных результатов: 
 + 
 +<code haskell> 
 +import Data.MemoTrie 
 + 
 +-- Naive binary recursion: F(n) = F(n-1) + F(n-2) with  
 +-- using memotrie from http://haskell.org/haskellwiki/MemoTrie 
 +fib :: Integer -> Integer 
 +fib 0 = 0 
 +fib 1 = 1 
 +fib n = mfib (n-2) + mfib (n-1) where mfib = memo fib 
 +</code> 
 + 
 +(Эксперименты показывают, что вычисления с мемоизацией не ускоряют бинарную рекурсию, лавиноообразное число вызовов с ростом n становится слишком велико). 
 + 
 +Рассмотрим императивное решение с циклом на Паскале: 
 + 
 +<code pascal> 
 +program fibb; 
 +var 
 +  f1,f2,f3: Int64; 
 +  n,i: integer; 
 +begin 
 +f1:=1; f2:=1; 
 +write ('please, input n='); read(n); 
 +for i:=1 to (n-2) do  
 +begin 
 + f3 := f2 + f1;  f1 := f2;  f2 := f3 
 +end; 
 +writeln ('f=', f3); 
 +end. 
 +</code> 
 + 
 +Эта программа позволяет быстро вычислять до 92-го члена последовательности (дальше возникают проблемы с превышением числового диапазона Int64). 
 + 
 +Сделаем аналог его, но уже с рекурсией вместо цикла. Рекурсия получится линейной, и добавится новый параметр "__//аккумулятор//__": 
 + 
 +<code haskell> 
 +f a b 0 = b 
 +f a b n = f b (a+b) (n-1) 
 +fib n = f 1 1 n 
 +</code> 
 + 
 +запуск осуществляется так: 
 +<code haskell> 
 +fib n 
 +</code> 
 + 
 +Этот вариант уже не имеет проблемных мест и позволяет вычислять даже 100000-й элемент последовательности за 0.5-1.5 минуты на ноутбуке. 
 + 
 +Другой вариант из сайта [[http://www.haskell.org/haskellwiki/The_Fibonacci_sequence|The Fibonacci sequence]] с аккумулятором и //хвостовой рекурсией// (используя расширения языка): 
 + 
 +<code haskell> 
 +{-# LANGUAGE BangPatterns #-} 
 +fib n = go n (0,1) 
 +  where 
 +    go !n (!a, !b) | n==0      = a 
 +                   | otherwise = go (n-1) (b, a+b) 
 +</code> 
 + 
 +Вот //императивный вариант// с монадой состояния (оттуда же): 
 + 
 +<code haskell> 
 +import Control.Monad.State 
 +fib n = flip evalState (0,1) $ do 
 +  forM [0..(n-1)] $ \_ -> do 
 +    (a,b) <- get 
 +    put (b,a+b) 
 +  (a,b) <- get 
 +  return a 
 +</code> 
 + 
 +А статья [[http://rsdn.ru/article/haskell/haskell_part1.xml|Мягкое введение в Haskell-1]] предлагает решение в виде циклического бесконечного списка: 
 + 
 +<code haskell> 
 +fib = 1 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ] 
 +</code>