Производительность Фибоначчи

Question

f[0] = 0;
f[1] = 1;
f[x_] := f[x-1] + f[x-2]

Эта функция работает медленно в Mathematica, и мне нужно увеличить скорость. Я должен использовать функциональное программирование и рекурсию. Я не уверен, почему это работает так медленно, и даже малейшая идея, как улучшить это, будет полезной

Answer 1

Хороший способ написать более быструю рекурсивную функцию - запоминать предыдущие значения. Конечно, это происходит за счет памяти, но в таких случаях это может помочь. Чтобы вычислить f[x], вы вычисляете f[x-1] и f[x-2] - и затем для вычисления f[x-1] вы снова вычисляете f[x-2]; в итоге вы пересчитываете много значений много раз. (Прости мою неточность!)

Чтобы хранить вещи по ходу дела, вы можете использовать эту идиому:

f[x_] := ( f[x] = (* calculation of f[x] goes here *)  )

Редактировать: у меня нет mathematica на этой машине, но я почти уверен, что нет способа это вычисляет неправильное значение.

f[0] = 0;
f[1] = 1;
f[x_] := ( f[x] = f[x-1] + f[x-2] );

f[256]

Как я уже сказал в комментарии ниже, если у вас есть другие определения f, вы можете сначала стереть их с помощью Clear[f].

Спасибо rcollyer: будьте осторожны с $RecursionLimit! По умолчанию используется значение 256. (Конечно, на это есть веские причины. Действительно глубокая рекурсия обычно является плохой идеей.)

Answer 2

Джефроми прав. Посмотрите на Памятка в Википедии. Они используют пример факториала и как ускорить его с помощью запоминания.

Answer 3

Заметка - это хороший способ написать более быструю рекурсивную функцию.Однако в этом случае существует рекурсивная альтернатива, которая работает чрезвычайно быстрее, чем исходная функция, не требуя запоминания.

Ключевое наблюдение состоит в том, чтобы увидеть, что исходное определение выполняет много избыточных вычислений.Рассмотрим, что произойдет, если мы вычислим fib[4]:

fib[4] = fib[3] + fib[2]
  fib[3] = fib[2] + fib[1]
    fib[2] = fib[1] + fib[0]
      fib[1] = 1
      fib[0] = 1
    ∴ fib[2] = 1 + 1 = 2
    fib[1] = 1
  ∴ fib[3] = 2 + 1 = 3
  fib[2] = fib[1] + fib[0]
    fib[1] = 1
    fib[0] = 1
  ∴ fib[2] = 1 + 1 = 2
∴ fib[4] = 2 + 1 = 3

. В этом процессе fib[2] и fib[0] вычислялись дважды каждый, а fib[1] - трижды.При больших вычислениях потери растут очень сильно - экспоненциально на самом деле.

Если вычислить одно и то же число Фибоначчи вручную, можно выполнить что-то вроде этого:

0: given   0
1: given   1
2: 0 + 1 = 1
3: 1 + 1 = 2
4: 1 + 2 = 3

Естьнет лишних расчетов.В любой данный момент нужно рассмотреть только два предыдущих результата.Этот последний подход можно выразить рекурсивно таким образом:

fib2[0] = 0;
fib2[n_] :=
  Module[{f},
    f[n, p1_, _] := p1;
    f[x_, p1_, p2_] := f[x + 1, p1 + p2, p1];
    f[1, 1, 0]
  ]

Block[{$IterationLimit = Infinity}, fib2[100000]]

Без сомнения, эта форма не так легко читается, как оригинал.С другой стороны, исходной функции потребовалось 35 секунд для вычисления fib[35] на моей машине, тогда как время выполнения пересмотренной функции для той же функции сообщалось как ноль.Кроме того, пересмотренная функция вычисляет fib2[100000] за 0,281 секунды, не требуя дополнительного хранения памяти.fib[100000] совершенно недоступен для исходной функции, а запомнившаяся версия разбила мое ядро ​​Mathematica 7.01 - возможно, слишком много запомненных правил?

Обратите внимание, что Mathematica, по умолчанию, будет повторятьсяфункция не более 4096 раз.Чтобы поднять этот предел, вы должны присвоить более высокое значение $IterationLimit, как показано в примере выше.

Конечно, в Mathematica есть множество нерекурсивных способов вычисления чисел Фибоначчи, вплоть довстроенная функция Fibonacci.Но это не главное в этом упражнении.

Оптимизация вызовов Tail?

Всегда желательно выражать рекурсивные функции, используя вызовы хвоста .Это позволяет выполнять рекурсию с помощью простой итерации, без необходимости сохранения промежуточных результатов в стеке.fib2 хвостовая рекурсия.Некоторые языки, такие как Scheme, требуют оптимизации хвостового вызова.Другие языки, такие как Java , могут поддерживать его, но не поддерживают (или не будут, как в случае Python ).

В случае Mathematica, не ясно, в какой степени выполняется оптимизация хвостового вызова.Для дальнейшего обсуждения этого вопроса см. другой вопрос SO .