Как правильно создать тег SVN из соединительной линии?

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

Что ж, она медленная, потому что каждый вызов 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 шагов, что намного меньше миллиарда.