массивы — C ++ Memoization понимание
Я пытался понять, как работает запоминание в C ++, поэтому я посмотрел на пример запоминания, используемый в Fib. последовательность.
std::map<int, int> fibHash;
int memoized_fib (int n)
{
std::map<int, int>::iterator fibIter = fibHash.find(n);
if( fibIter != fibHash.end() ) return *fibIter;
int fib_val;
if( n <=1 ) fib_val = 1;
else fib_val = memoized_fib ( n-1 ) + memoized_fib ( n-2 );
fibHash[ n ] = fib_val;
return fib_val;
}
Я был немного смущен тем, как работает fibHash [n]. Это просто содержит отдельные значения каждого FIB (#)? Кроме того, итератор пересекает индекс, чтобы найти правильное значение в таблице, и возвращает это? Например, fib (6) = найти fib (5) и fib (4), уже сохранены и просто добавить их?
Решение
Код действительно сохранить каждый fib_val в fibHash карта. находить метод вызван fibHash ищет карту, чтобы увидеть, было ли ранее вычислено значение. Если так, find возвращает итератор для этого значения, а функция возвращает его (return *fibIter).
fibHash[ n ] = fib_val; добавляет новое значение в карту.
Другие решения
То, что вы говорите, по сути правильно.
«Это [fibHash] просто содержит отдельные значения каждого fib (#)?»
Да, точно. Значения заполняются по мере их расчета (с fibHash[ n ] = fib_val;). Более низкие значения FIB используются для расчета более высоких значений.
fibHash отобразить карты X в fib (X), простые и простые.
Преимущество такого способа состоит в том, что если вы вычисляете fib (20), а затем fib (21) и fib (23), то, возможно, fib (15), вам нужно вычислить промежуточные значения только один раз.
Стоимость этого ускорения заключается в хранении значений в fibHash,
Это просто содержит отдельные значения каждого FIB (#)?
Да.
Кроме того, итератор пересекает индекс, чтобы найти правильное значение в таблице, и возвращает это?
Да.
Например, fib (6) = найти fib (5) и fib (4), уже сохранены и просто добавить их?
Зависит. Сначала выполняется поиск fib (6), чтобы узнать, был ли вызван fib (6) раньше. Если это так, то сохраненный ответ возвращается. Если он никогда не вызывался, то были названы fib (5) и fib (4). Интересно то, что если fib (5) нужно вычислить, он вызывает fib (4) до того, как fib (6) сделает *, а затем, когда fib (6) также вызывает fib (4), результат гарантированно будет найден в fibHash, потому что fib (5) уже называется fib (4). Это то, что вызывает коллапс fib (n) из экспоненциального времени в нечто более похожее на линейное.
Наивная рекурсивная реализация Фибоначчи сводится к тому, чтобы складывать 1 много раз.
fib(5) =
fib(4) + fib(3) =
fib(3) + fib(2) + fib(2) + fib(1) =
fib(2) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) =
fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) =
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 =
8
Фактически, чтобы вычислить fib (n), вы в конечном итоге делаете сложения fib (n) -1. Но если в процессе вычисления fib (n) вы сохраняете и используете ранее вычисленные числа Фибоначчи, вам больше не нужно выполнять столько дополнений. Для вычисления fib (n) этот способ требует только n дополнений:
fib(5) =
fib(4) + fib(3) =
fib(3) + fib(2) + fib(3) =
fib(2) + fib(1) + fib(2) + fib(3) =
fib(1) + fib(0) + fib(1) + fib(2) + fib(3) =
1 + 1 + 1 + 2 + 3 =
8
* Хотя заказ не гарантирован. fib (6) может сначала вызвать fib (4), а затем, когда fib (6) вызывает fib (5), fib (5) вызывает fib (4), который теперь гарантированно вернет сохраненное значение.