Почему одна и та же функция, написанная по-разному, имеет такое разное время результата?

Я игрался с языком wolfram и кое-что заметил: одна и та же функция, написанная по-разному, работает очень по-разному с точки зрения времени.

Рассмотрим эти две функции:

NthFibonacci[num_] := 
 If [num == 0 || num == 1, Return[ 1], 
   Return[NthFibonacci[num - 1] + NthFibonacci[num - 2]]
 ]

Fibn[num_] := {
 a = 1; 
 b =  1; 
 For[i = 0, i < num  - 1, i++,
  c = a + b;
  a = b;
  b = c;
  ];
 Return [b];
 }

Для оценки NthFibonacci[30] требуется около 5 секунд.
Для оценки Fibn[900 000] также требуется около 5 секунд.
Так же, как и для встроенной функции Fibonacci[50 000 000].

Я просто не могу понять, почему такая разница в скорости между тремя. Теоретически рекурсия должна быть более или менее эквивалентна циклу for. Чем это вызвано?


recursion performance wolfram-mathematica wolframalpha wolfram-language
person Арсен Гоян    schedule 28.06.2016    source источник
comment
«Теоретически рекурсия должна быть более или менее эквивалентна циклу for»: в общем случае это неверно, только для частного случая хвостовой рекурсии, трансформируемой компилятором в итерации.   -  person Renzo    schedule 28.06.2016

Ответы (3)


arrow_upward
3
arrow_downward

Это потому, что рекурсивная версия, которую вы представляете, выполняет много-много повторяющихся вычислений. Постройте дерево вызовов функций, чтобы понять, что я имею в виду. Даже для такого маленького аргумента, как 4, посмотрите, сколько вызовов функций генерируется, чтобы добраться до базового случая по каждой цепочке логики.

                 f(1)
                /
            f(2)
           /    \
       f(3)      f(0)
      /    \
     /      f(1)
    /
f(4)
    \
     \      f(1)
      \    /
       f(2)
           \
            f(0)

С вашей рекурсией количество вызовов функций растет экспоненциально с аргументом num.

Напротив, ваша зацикленная версия растет линейно в num. Не требуется очень большое значение n, прежде чем n будет намного меньше работы, чем 2n.

person pjs    schedule 28.06.2016

arrow_upward
1
arrow_downward

Есть много способов реализовать рекурсию; функция Фибоначчи — прекрасный пример. Как уже указывал pjs, классическое определение с двойной рекурсией растет экспоненциально. База

φ = (кв. кв. (5) + 1) / 2 = 1,618+

Ваша реализация NthFibonacci работает таким образом. Это порядок φ^n, что означает, что для больших n вызов f(n+1) занимает в φ раз больше времени, чем f(n).

Более мягкий подход вычисляет каждое функциональное значение только один раз в потоке выполнения. Вместо экспоненциального времени требуется линейное время, а это означает, что вызов f(2n) занимает в 2 раза больше времени, чем f(n).

Есть и другие подходы. Например, динамическое программирование (DP) хранит в кэше предыдущие результаты. В случае pjs f(4) реализация DP будет вычислять f(2) только один раз; второй вызов увидит, что результат первого находится в кеше, и вернет результат, а не будет делать дальнейшие вызовы f(0) и f(1). Это имеет тенденцию к линейному времени.

Существуют также реализации, которые создают контрольные точки, такие как кэширование f(k) и f(k)+1 для k, кратного 1000. Они экономят время, поскольку имеют начальную точку не слишком далеко от желаемого значения, что дает им верхнюю границу 998 итераций, чтобы найти нужное значение.

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

φ = (1+sqrt(5)) / 2 = 1.618...
ψ = (1-sqrt(5)) / 2 = -.618...
f(n) = (φ^n - ψ^n) / sqrt(5)
person Prune    schedule 28.06.2016

arrow_upward
0
arrow_downward

Проблема, отмеченная @pjs, может быть решена до некоторой степени, если рекурсивная функция запоминает предыдущие значения. (устранение If тоже помогает)

Clear[NthFibonacci]
NthFibonacci[0] = 1
NthFibonacci[1] = 1
NthFibonacci[num_] := 
 NthFibonacci[num] = NthFibonacci[num - 1] + NthFibonacci[num - 2]
NthFibonacci[300] // AbsoluteTiming

{0.00201479, 3.59 10^62}

Очистка вашей версии цикла (вы почти никогда не должны использовать Return в математике):

Fibn[num_] := Module[{a = 1, b = 1,c},
  Do[c = a + b; a = b; b = c, {num - 1}]; b]

Fibn[300] // AbsoluteTiming

{0.000522175 ,3.59 10^62}

вы видите, что рекурсивная форма медленнее, но не так ужасно. (Обратите внимание, что рекурсивная форма также достигает предела глубины около 1000)

person agentp    schedule 28.06.2016