Почему эта реализация Фибоначчи чрезвычайно быстро?

Это просто запутывание, чтобы скрыть тот факт, что введенный номер используется в качестве счетчика. Я надеюсь, что если бы вы увидели нечто подобное, вы бы поняли, почему:

fib2 n = fastFib2 0 1 0 n

fastFib2 current previous count 0 = 0
fastFib2 current previous count 1 = 1
fastFib2 current previous count n
  | count == n = current
  | otherwise  =
     fastFib2 (current + previous) current (count + 1) n

В приведенном выше коде мы сделали счетчик явным: когда он равен нашему входу, n, мы возвращаем наш аккумулятор, current; в противном случае мы отслеживаем эту «прямую» рекурсию текущего и предыдущего чисел (« двух предыдущих »)), всего, что необходимо для построения последовательности Фибоначчи.

Код, которым вы поделились, делает то же самое. (c - 1) делает его похожим на более традиционное «обратное» повторение, когда он фактически запускает аккумулятор при первом вызове, а затем добавляет к нему

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

fib1 n = slow n id
  where
    slow 0 k = k 0
    slow 1 k = k 1
    slow n k = slow (n - 1) (\a ->
               slow (n - 2) (\b ->
               k (a + b)))

fib2 n = fast n 0 1
  where
    fast 0 a _ = a
    fast n a b = fast (n - 1) b (a + b)

Воздействие на крошечные числа, такие как n = 10 незначительно -

fib1 10
-- 55
-- (0.01 secs, 138,264 bytes)

fib2 10
-- 55
-- (0.01 secs, 71,440 bytes)

Но даже вокруг n = 20 мы замечаем огромный спад в fib1 производительности -

fib1 20
-- 6765
-- (0.70 secs, 8,787,320 bytes)

fib2 20
-- 6765
-- (0.01 secs, 76,192 bytes)

В n = 30, воздействие смешно. Обе программы все еще достигают одного и того же результата, так что это хорошо, но fib1 занимает более 30 секунд. fib2 все еще занимает долю секунды -

fib1 30
-- 832040
-- (32.91 secs, 1,072,371,488 bytes) LOL so bad

fib2 30
-- 832040 (0.09 secs, 80,944 bytes)

Причина этого в том, что первая программа, fib1, делает два рекурсивных вызова. Процесс для этой функции использует экспоненциальное время и пространство по мере роста n. В n = 30 медленная программа выполнит 1 073 741 824 (2 ^{30 ) рекурсивных вызова. Быстрая программа будет повторяться только 30 раз.}

На n = 1000 мы столкнулись с серьезной проблемой с fib1. Основываясь на производительности fib1 30, мы оцениваем, что потребуется 1.041082353242204e286 лет для завершения 2 ^{1000 рекурсивных вызовов. Между тем, fib2 1000 легко обрабатывает 1000 рекурсий -}

fib2 1000
-- 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
-- (0.13 secs, 661,016 bytes)

Исходное переписывание вашей первой программы может быть затруднено с добавленным параметром k. Использование Cont позволяет нам увидеть четкую последовательность шагов в знакомой нотации Хаскелла do -

import Control.Monad.Cont

fib1 n = runCont (slow n) id
  where
    slow 0 = return 0
    slow 1 = return 1
    slow n = do
      a <- slow (n - 1)
      b <- slow (n - 2)
      return (a + b)

Почему первая реализация медленная?

Что ж, она медленная, потому что каждый вызов fib может привести к двум (в среднем более 1,6) вызовам fib, поэтому для вычисления [ 1110] вы называете fib 4 и fib 3, которые соответственно называют fib 3 и fib 2, а также fib 2 и fib 1, поэтому мы видим, что каждый вызов fib (n+1) приводит к чему-то вдвое большему количеству работы как зовет fib n.

Одна вещь, которую мы могли бы заметить, это то, что мы много раз выполняем одно и то же, например, выше мы разрабатываем fib 3 дважды. Это может занять много времени, если вы должны работать, например, fib 100 дважды.

Как сделать выдумку быстрее?

Я думаю, что лучше начать с этого, чем пытаться прыгнуть прямо в fastFib. Если бы я попросил вас вычислить десятое число Фибоначчи вручную, я ожидаю, что вы не будете вычислять третье число десятки раз, применяя алгоритм. Возможно, вы помните, что у вас было до сих пор. Действительно, это можно сделать в Хаскеле. Просто напишите программу для генерации списка чисел Фибоначчи (лениво) и внесите в него индекс:

mediumFib = (\n -> seq !! n) where
  seq = 0:1:[mediumFib (i-1) + mediumFib (i-2)| i <- [2..]]

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

Чтобы вычислить одно число Фибоначчи с нуля (то есть, не вычисляя его уже), требуется квадратичное время.

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

fib(n):
  if (n<2) return n
  preprevious = 0
  previous = 1
  i = 2
  while true:
    current = preprevious + previous
    if (i = n) return current
    preprevious, previous = previous, current

Это просто пошаговое выполнение рекуррентного соотношения:

f_n = f_(n-2) + f_(n-1)

Действительно, мы можем написать это и на Хаскеле:

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

1. Поменяйте местами порядок аргументов pp (предварительный) и p (предыдущий)
2. Вместо подсчета i, начните с n ] и обратный отсчет.
3. Извлеките go в функцию верхнего уровня, поскольку она больше не зависит от n.

Этот алгоритм должен делать только одну сумму на каждом шаге, так что это линейное время, и это довольно быстро. Вычислить fib (n+1) - это лишь небольшая постоянная дополнительная работа, чем вычисления fib n. Сравните это с тем, что было в 1,6 раза больше.

Есть ли быстрее fib?

Конечно, есть. Оказывается, есть умный способ выразить последовательность Фибоначчи. Мы считаем преобразование a,b -> a+b,a частным случаем семейства преобразований T_pq:

T_pq : a -> bq + aq + ap
       b -> bp + aq

В частности, это особый случай, когда p = 0 и q = 1. Теперь мы можем выполнить некоторую алгебру, если есть простой способ выразить применение T_pq дважды:

T_pq T_pq :
  a -> (bp + aq)q + (bq + aq + ap)(q + p)
  b -> (bp + aq)p + (bq + aq + ap)q
=
  a -> (b + a)(q^2 + 2pq) + a(q^2 + p^2)
  b -> b(q^2 + p^2) + a(q^2 + 2pq)
= T_(q^2 + p^2),(q^2 + 2pq)

Так что теперь давайте напишем простую функцию для вычисления T_pq^n (a,b) и fib n

tPow p q a b n | n = 1 = (b*q + a*q + a*p, b*p + a*q)
               | otherwise = let (a', b') = tPow p q a b 1 in tPow p q a' b' (n-1)

fib 0 = 0
fib 1 = 1
fib n = fst $ tPow 0 1 1 0 (n-1)

И теперь мы можем использовать наше отношение, чтобы сделать tPow быстрее:

tPow p q a b n | n = 1 = (b*q + a*q + a*p, b*p + a*q)
               | odd n = let (a', b') = tPow p q a b 1 in tPow p q a' b' (n-1)
               | even n = tPow (q*q + p*p) (q*q + 2*p*q) a b (n `div` 2)

Почему это быстрее? Ну, это быстрее, потому что тогда вычисление fib (2*n) - это лишь небольшая постоянная дополнительная работа, чем вычисление fib n, тогда как раньше это было вдвое больше работы, а до этого было в четыре раза больше работы, а до этого это был квадрат суммы работы. Действительно, число шагов - это что-то вроде количества битов n в двоичном формате плюс число 1 с в двоичном представлении n. Для вычисления fib 1024 требуется всего около 10 шагов, тогда как предыдущий алгоритм занимал около 1000. Вычисление миллиардного числа Фибоначчи занимает всего 30 шагов, что намного меньше миллиарда.