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

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

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

В случае с fibo вам даже не нужно все кэшировать:

[править] Автор вопроса, похоже, ищет общий метод кеширования, а не метод вычисления Фибоначчи. Ищите википедию или посмотрите код другого автора, чтобы получить этот ответ. Эти ответы линейны по времени и памяти.

** Вот алгоритм линейного времени O (n), постоянный в памяти **

in OCaml:

let rec fibo n = 
    let rec aux = fun
        | 0 -> (1,1)
        | n -> let (cur, prec) = aux (n-1) in (cur+prec, cur)
    let (cur,prec) = aux n in prec;;



in C++:

int fibo(int n) {
    if (n == 0 ) return 1;
    if (n == 1 ) return 1;
    int p = fibo(0);
    int c = fibo(1);
    int buff = 0;
    for (int i=1; i < n; ++i) {
      buff = c;
      c = p+c;
      p = buff;
    };
    return c;
};

Это выполняется в линейное время. Но лог реально возможен !!! Программа Ру также линейна, но намного медленнее и использует память.

Вот алгоритм журнала O (log (n))

Теперь для алгоритма времени журнала (намного быстрее), вот метод: Если вы знаете, что u (n), u (n-1), вычисление u (n + 1), u (n) можно выполнить, применив матрицу:

| u(n+1) |  = | 1 1 | | u(n)   |
| u(n)   |    | 1 0 | | u(n-1) |    

Так что у вас есть:

| u(n)    |  = | 1 1 |^(n-1) | u(1) | = | 1 1 |^(n-1) | 1 |
| u(n-1)  |    | 1 0 |       | u(0) |   | 1 0 |       | 1 |

Вычисление экспоненты матрицы имеет логарифмическую сложность. Просто рекурсивно реализуй идею:

M^(0)    = Id
M^(2p+1) = (M^2p) * M
M^(2p)   = (M^p) * (M^p)  // of course don't compute M^p twice here.

Вы также можете просто диагонализировать его (не сложно), вы найдете золотое число и его сопряжение в его собственном значении, и в результате вы получите ТОЧНУЮ математическую формулу для u (n). Он содержит степени этих собственных значений, так что сложность все равно будет логарифмической.

Фибо часто берется в качестве примера для иллюстрации динамического программирования, но, как вы видите, это не совсем уместно.

@ Джон: Я не думаю, что это имеет какое-либо отношение к хешу.

@ John2: Карта немного общая, не правда ли? Для случая Фибоначчи все ключи являются смежными, так что вектор является подходящим, еще раз есть гораздо более быстрые способы вычисления последовательности Фибоначчи, см. Мой пример кода там.

Answer 2

Это называется напоминанием, и в эти дни опубликована очень хорошая статья о памятовании Мэттью Подвизоки . Он использует Фибоначчи, чтобы проиллюстрировать это. И показывает код в C # также. Прочитайте это здесь .

Answer 3

Если вы используете C # и можете использовать PostSharp , вот простой аспект запоминания для вашего кода:

[Serializable]
public class MemoizeAttribute : PostSharp.Laos.OnMethodBoundaryAspect, IEqualityComparer<Object[]>
{
    private Dictionary<Object[], Object> _Cache;

    public MemoizeAttribute()
    {
        _Cache = new Dictionary<object[], object>(this);
    }

    public override void OnEntry(PostSharp.Laos.MethodExecutionEventArgs eventArgs)
    {
        Object[] arguments = eventArgs.GetReadOnlyArgumentArray();
        if (_Cache.ContainsKey(arguments))
        {
            eventArgs.ReturnValue = _Cache[arguments];
            eventArgs.FlowBehavior = FlowBehavior.Return;
        }
    }

    public override void OnExit(MethodExecutionEventArgs eventArgs)
    {
        if (eventArgs.Exception != null)
            return;

        _Cache[eventArgs.GetReadOnlyArgumentArray()] = eventArgs.ReturnValue;
    }

    #region IEqualityComparer<object[]> Members

    public bool Equals(object[] x, object[] y)
    {
        if (Object.ReferenceEquals(x, y))
            return true;

        if (x == null || y == null)
            return false;

        if (x.Length != y.Length)
            return false;

        for (Int32 index = 0, len = x.Length; index < len; index++)
            if (Comparer.Default.Compare(x[index], y[index]) != 0)
                return false;

        return true;
    }

    public int GetHashCode(object[] obj)
    {
        Int32 hash = 23;

        foreach (Object o in obj)
        {
            hash *= 37;
            if (o != null)
                hash += o.GetHashCode();
        }

        return hash;
    }

    #endregion
}

Вот пример реализации Фибоначчи с его использованием:

[Memoize]
private Int32 Fibonacci(Int32 n)
{
    if (n <= 1)
        return 1;
    else
        return Fibonacci(n - 2) + Fibonacci(n - 1);
}

Answer 4

Быстрое и грязное запоминание в C ++:

Любой рекурсивный метод type1 foo(type2 bar) { ... } легко запоминается с помощью map<type2, type1> M.

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

// with memoization
map<int, int> M = map<int, int>();
int fib(int n)
{
    if(n==0 || n==1)
        return 1;

    // only compute the value for fib(n) if we haven't before
    if(M.count(n) == 0)
        M[n] = fib(n-1) + fib(n-2);

    return M[n];
}

РЕДАКТИРОВАТЬ: @Konrad Rudolph
Конрад отмечает, что std :: map не самая быстрая структура данных, которую мы могли бы использовать здесь. Это правда, vector<something> должен быть быстрее, чем map<int, something> (хотя это может потребовать больше памяти, если входные данные для рекурсивных вызовов функции не были последовательными целыми числами, как в этом случае), но карты удобны в использовании в общем-то.

Answer 5

Согласно Википедии Fib (0) должно быть 0, но это не имеет значения.

Вот простое решение C # для цикла:

ulong Fib(int n)
{
  ulong fib = 1;  // value of fib(i)
  ulong fib1 = 1; // value of fib(i-1)
  ulong fib2 = 0; // value of fib(i-2)

  for (int i = 0; i < n; i++)
  {
    fib = fib1 + fib2;
    fib2 = fib1;
    fib1 = fib;
  }

  return fib;
}

Довольно распространенная уловка - преобразовать рекурсию в хвостовую рекурсию и затем выполнить цикл. Более подробно см., Например, эту лекцию (ppt).

Answer 6

Это сознательно выбранный пример? (например, крайний случай, который вы хотите проверить)

Поскольку в настоящее время это O (1.6 ^ n), я просто хочу убедиться, что вы просто ищете ответы на обработку общего случая этой проблемы (кэширование значений и т. Д.), А не просто написание плохого кода: D

Глядя на этот конкретный случай, вы можете получить что-то вроде:

var cache = [];
function fib(n) {
    if (n < 2) return 1;
    if (cache.length > n) return cache[n];
    var result = fib(n - 2) + fib(n - 1);
    cache[n] = result;
    return result;
}

Который вырождается в O (n) в худшем случае: D

[Редактировать: * не равно +: D]

[Еще одно редактирование: версия на Haskell (потому что я мазохист или что-то в этом роде)

fibs = 1:1:(zipWith (+) fibs (tail fibs))
fib n = fibs !! n

]

Answer 7

кеширование, как правило, хорошая идея для такого рода вещей. Поскольку числа Фибоначчи постоянны, вы можете кэшировать результат, как только вы его вычислите. Пример быстрого c / псевдокода

class fibstorage {


    bool has-result(int n) { return fibresults.contains(n); }
    int get-result(int n) { return fibresult.find(n).value; }
    void add-result(int n, int v) { fibresults.add(n,v); }

    map<int, int>   fibresults;

}


fib(int n ) {
    if(n==0 || n==1)
            return 1;

    if (fibstorage.has-result(n)) {
        return fibstorage.get-result(n-1);
    }

    return ( (fibstorage.has-result(n-1) ? fibstorage.get-result(n-1) : fib(n-1) ) +
             (fibstorage.has-result(n-2) ? fibstorage.get-result(n-2) : fib(n-2) )
           );
}


calcfib(n) {
    v = fib(n);
    fibstorage.add-result(n,v);
}

Это будет довольно медленно, так как каждая рекурсия приводит к 3 поискам, однако это должно иллюстрировать общую идею

Answer 8

Попробуйте использовать карту, n - это ключ, а соответствующее ему число Фибоначчи - это значение.

@ Paul

Спасибо за информацию. Я этого не знал. Из ссылки Википедии вы упомянули:

Это техника сохранения значений, уже подсчитано называется мемоизации

Да, я уже посмотрел код (+1). :)

Answer 9

Mathematica имеет очень удобный способ делать заметки, полагаясь на тот факт, что хеши и вызовы функций используют один и тот же синтаксис:

fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]

Вот и все. Он кэширует (запоминает) fib [0] и fib [1], и кэширует остальное по мере необходимости. Правила для вызовов функций сопоставления с образцом таковы, что перед более общим определением всегда используется более конкретное определение.

Answer 10

Еще один отличный ресурс для программистов на C #, посвященный рекурсии, частичным вычислениям, каррированию, запоминанию и тому подобному, - это блог Уэса Дайера, хотя он и не публиковал сообщения в течение некоторого времени. Он хорошо объясняет запоминание, с примерами твердого кода здесь: http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx