Ответ 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;
};

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

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

Теперь для алгоритма log-time (путь путь быстрее), вот способ: Если вы знаете 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). Он содержит мощности этих собственных значений, так что сложность будет по-прежнему логарифмической.

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

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

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

Ответ 2

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

Ответ 3

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

[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);
}

Ответ 4

Быстрая и грязная memoization в С++:

Любой рекурсивный метод 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];
}

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

Ответ 5

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

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

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).

Ответ 6

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

@Paul

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

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

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

Ответ 7

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

Ответ 8

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

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 поискам, однако это должно проиллюстрировать общую идею

Ответ 9

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

Как и в настоящее время 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

]

Ответ 10

@ESRogs:

std::map lookup - это 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];
}

Ответ 11

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

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

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

Ответ 12

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

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

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

Ответ 13

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

Ответ 14

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

(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)))))))

Первый блок предоставляет средство memoization, а второй блок - последовательность фибоначчи с использованием этого средства. Это теперь имеет O (n) время выполнения (в отличие от O (2 ^ n) для алгоритма без memoization).

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

Ответ 15

Проблема с этим кодом заключается в том, что он будет генерировать ошибку для любого числа, которое больше 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]);
    }
}

Ответ 16

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

Начальный код функции:

 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]

Ответ 17

Кстати, у 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 ;-)

Ответ 18

@lassevk:

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

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

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

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