Почему первая реализация медленная?
Что ж, она медленная, потому что каждый вызов fib может привести к двум (в среднем более 1,6) вызовам fib, так что для вычисления fib 5 вы вызываете 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)
Действительно, мы можем записать его и на Haskell:
fastFib n | n < 2 = n
| otherwise = go 0 1 2 where
go pp p i | i = n = pp + p
| otherwise = go p (pp + p) (i + 1)
Теперь это довольно быстро, и мы можем преобразовать это в функцию, которая у вас тоже есть.Вот шаги:
- Поменяйте местами порядок аргументов
pp (предварительный) и p (предыдущий) - Вместо того, чтобы считать
i, начните с n и обратный отсчет. - Извлечение
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 шагов, что намного меньше миллиарда.