Есть ли способ ускорить рекурсию, запомнив дочерние узлы?

Question

Например, Посмотрите на код, который вычисляет n-е число Фибоначчи:

fib(int n)
{
    if(n==0 || n==1)
        return 1;
    return fib(n-1) + fib(n-2);
}

Проблема с этим кодом заключается в том, что он генерирует ошибку переполнения стека для любого числа больше 15 (на большинстве компьютеров).

Предположим, что мы вычисляем fib (10). В этом процессе, скажем, fib (5) вычисляется много раз. Есть ли способ сохранить это в памяти для быстрого поиска и тем самым увеличить скорость рекурсии?

Я ищу общую технику, которая может использоваться практически во всех задачах.

Answer 1

Другие ответили на ваш вопрос хорошо и точно - вы ищете памятку.

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

Формулировка вашего вопроса заставила меня задуматься об одной интересной идее: избежать переполнения стека чисто рекурсивной функции, сохранив только подмножество фреймов стека, и перекомпилировав при необходимости. В некоторых случаях это действительно полезно. Если ваш алгоритм только условно зависит от контекста, а не от возврата, и / или вы оптимизируете память, а не скорость.

Answer 2

@ ESRogs:

std::map поиск - O (log n ), что замедляет процесс Лучше использовать вектор.

vector<unsigned int> fib_cache;
fib_cache.push_back(1);
fib_cache.push_back(1);

unsigned int fib(unsigned int n) {
    if (fib_cache.size() <= n)
        fib_cache.push_back(fib(n - 1) + fib(n - 2));

    return fib_cache[n];
}

Answer 3

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

Answer 4

@ lassevk:

Это удивительно, именно то, о чем я думал в своей голове после прочтения памятки в Perl высшего порядка . Две вещи, которые я считаю полезными дополнениями:

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

Не уверен, как делать подобные вещи с Атрибутами (или, если они вообще возможны, с такой реализацией), но я планирую попытаться выяснить.

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

Answer 5

Кстати, в Perl есть модуль memoize , который делает это для любой функции в вашем коде, которую вы укажете.

# Compute Fibonacci numbers
sub fib {
      my $n = shift;
      return $n if $n < 2;
      fib($n-1) + fib($n-2);
}

Чтобы запомнить эту функцию, все, что вам нужно сделать, это запустить вашу программу с

use Memoize;
memoize('fib');
# Rest of the fib function just like the original version.
# Now fib is automagically much faster ;-)

Answer 6

Как отмечали другие авторы, памятка - это стандартный способ обмена памяти на скорость, здесь приведен псевдокод для реализации памятки для любой функции (при условии, что функция не имеет побочных эффектов):

Исходный код функции:

 function (parameters)
      body (with recursive calls to calculate result)
      return result

Это должно быть преобразовано в

 function (parameters)
      key = serialized parameters to string
      if (cache[key] does not exist)  {
           body (with recursive calls to calculate result)
           cache[key] = result
      }
      return cache[key]

Answer 7

Если вы используете язык с первоклассными функциями, такими как Scheme, вы можете добавить памятку без изменения исходного алгоритма:

(define (memoize fn)
  (letrec ((get (lambda (query) '(#f)))
           (set (lambda (query value)
                  (let ((old-get get))
                    (set! get (lambda (q)
                                (if (equal? q query)
                                    (cons #t value)
                                    (old-get q))))))))
    (lambda args
      (let ((val (get args)))
        (if (car val)
            (cdr val)
            (let ((ret (apply fn args)))
              (set args ret)
              ret))))))


(define fib (memoize (lambda (x)
                       (if (< x 2) x
                           (+ (fib (- x 1)) (fib (- x 2)))))))

Первый блок обеспечивает средство запоминания, а второй блок представляет собой последовательность Фибоначчи, использующую это средство. Теперь он имеет время выполнения O (n) (в отличие от O (2 ^ n) для алгоритма без запоминания).

Примечание: предоставленное средство запоминания использует цепочку замыканий для поиска предыдущих вызовов. В худшем случае это может быть O (n). В этом случае, однако, требуемые значения всегда находятся наверху цепочки, обеспечивая поиск O (1).

Answer 8

Проблема с этим кодом заключается в том, что он генерирует ошибку переполнения стека для любого числа больше 15 (на большинстве компьютеров).

В самом деле? Какой компьютер вы используете? Это занимает много времени в 44, но стек не переполняется. Фактически, вы собираетесь получить значение, превышающее целое число (~ 4 миллиарда без знака, ~ 2 миллиарда со знаком) до того, как стек переполнится (Fibbonaci (46)).

Это будет работать для того, что вы хотите сделать, хотя (работает быстро вики)

class Program
{
    public static readonly Dictionary<int,int> Items = new Dictionary<int,int>();
    static void Main(string[] args)
    {
        Console.WriteLine(Fibbonacci(46).ToString());
        Console.ReadLine();
    }

    public static int Fibbonacci(int number)
    {
        if (number == 1 || number == 0)
        {
            return 1;
        }

        var minus2 = number - 2;
        var minus1 = number - 1;

        if (!Items.ContainsKey(minus2))
        {
            Items.Add(minus2, Fibbonacci(minus2));
        }

        if (!Items.ContainsKey(minus1))
        {
            Items.Add(minus1, Fibbonacci(minus1));
        }

        return (Items[minus2] + Items[minus1]);
    }
}