Есть ли какой-нибудь способ ускорить рекурсию, запомнив дочерние узлы?
https://stackoverflow.com/questions/23962
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Например, Посмотрите на код, который вычисляет n-е число Фибоначчи:
fib(int n)
{
if(n==0 || n==1)
return 1;
return fib(n-1) + fib(n-2);
}
Проблема с этим кодом заключается в том, что он будет генерировать ошибку переполнения стека для любого числа, большего 15 (на большинстве компьютеров).
Предположим, что мы вычисляем fib (10).В этом процессе, скажем, fib (5) вычисляется много раз.Есть ли какой-нибудь способ сохранить это в памяти для быстрого извлечения и тем самым увеличить скорость рекурсии?
Я ищу общий метод, который можно использовать практически во всех задачах.
Решение
Да, ваше понимание верно.Это называется динамическое программирование.Обычно это обычный компромисс между памятью и временем выполнения.
В случае фибоначчи вам даже не нужно все кэшировать :
[редактировать] Автор вопроса, похоже, ищет общий метод кэширования, а не метод вычисления Фибоначчи.Поищите в википедии или посмотрите код другого плаката, чтобы получить этот ответ.Эти ответы линейны по времени и памяти.
** Вот алгоритм линейного времени 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).Он содержит степени этих собственных значений, так что сложность по-прежнему будет логарифмической.
Фибоначчи часто берется в качестве примера для иллюстрации динамического программирования, но, как вы видите, на самом деле это неуместно.
@Джон:Я не думаю, что это имеет какое-то отношение к do with hash.
@Джон2:Карта - это слишком обобщенно, вам не кажется?Для случая Фибоначчи все ключи смежны, так что вектор подходит, опять же, есть гораздо более быстрые способы вычисления последовательности Фибоначчи, смотрите Мой пример кода вон там.
Другие советы
Это называется запоминанием, и есть очень хорошая статья о запоминании Мэтью Подвысоцкий опубликовано в эти дни.Он использует Фибоначчи, чтобы проиллюстрировать это.И также показывает код на C #.Прочитай это здесь.
Если вы используете C # и можете использовать Постшарповый, вот простой аспект запоминания вашего кода:
[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);
}
Быстрое и грязное запоминание в 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> (хотя для этого могло бы потребоваться больше памяти, если бы входные данные для рекурсивных вызовов функции не были последовательными целыми числами, как в данном случае), но карты в целом удобны в использовании.
Согласно википедия Fib (0) должно быть равно 0, но это не имеет значения.
Вот простое решение на C # с циклом for:
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;
}
Это довольно распространенный трюк для преобразования рекурсии в хвостовая рекурсия а затем перейти к циклу.Для получения более подробной информации смотрите, например, это лекция (п.п.).
Что это за язык?Это ничего не переполняет в c...Кроме того, вы можете попробовать создать таблицу подстановки в куче или использовать карту
кэширование, как правило, является хорошей идеей для такого рода вещей.Поскольку числа Фибоначчи постоянны, вы можете кэшировать результат после его вычисления.Краткий пример 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 поискам, однако это должно проиллюстрировать общую идею
Это намеренно выбранный пример?(например.крайний случай, который вы хотите протестировать)
Поскольку в настоящее время это 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 ]
[Еще одна правка:версия на Хаскелле (потому что я мазохист или что-то в этом роде)
fibs = 1:1:(zipWith (+) fibs (tail fibs))
fib n = fibs !! n
]
Попробуйте использовать карту, где n - ключ, а соответствующее ему число Фибоначчи - значение.
@Пол
Спасибо за информацию.Я этого не знал.Из самого Ссылка на Википедию вы упомянули:
Этот метод сохранения значений, которые уже были вычислены, называется запоминанием
Да, я уже просмотрел код (+1).:)
@ESRogs:
std::map поиск - это O(журнал регистрации 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];
}
Другие хорошо и точно ответили на ваш вопрос - вы ищете запоминание.
Языки программирования с оптимизация конечных вызовов (в основном функциональные языки) могут выполнять определенные случаи рекурсии без переполнения стека.Это не относится непосредственно к вашему определению Фибоначчи, хотя здесь есть свои хитрости..
Формулировка вашего вопроса навела меня на интересную мысль..Избегая переполнения стека чисто рекурсивной функции, сохраняя только подмножество фреймов стека и перестраивая их при необходимости..Действительно полезно только в нескольких случаях.Если ваш алгоритм только условно полагается на контекст, а не на возврат, и / или вы оптимизируете память, а не скорость.
В Mathematica есть особенно удобный способ запоминания, основанный на том факте, что хэши и вызовы функций используют один и тот же синтаксис:
fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]
Вот и все.Он кэширует (запоминает) fib [0] и fib [1] с места в карьер и кэширует остальное по мере необходимости.Правила для вызовов функций сопоставления с образцом таковы, что при этом всегда используется более конкретное определение перед более общим определением.
Еще одним отличным ресурсом для программистов на C # по рекурсии, партиалам, каррированию, запоминанию и иже с ними является блог Уэса Дайера, хотя он давно ничего не публиковал.Он хорошо объясняет процесс запоминания, приводя здесь солидные примеры кода:http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx
Проблема с этим кодом заключается в том, что он будет генерировать ошибку переполнения стека для любого числа, большего 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]);
}
}
Если вы используете язык с первоклассными функциями, такими как 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) поиск.
Как указывалось на других плакатах, запоминание это стандартный способ обмена памятью на скорость, вот некоторый псевдокод для реализации запоминания для любой функции (при условии, что функция не имеет побочных эффектов):
Начальный функциональный код:
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]
Кстати, в Perl есть запоминать модуль, который делает это для любой функции в вашем коде, которую вы укажете.
# 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 ;-)
@lassevk:
Это потрясающе, именно то, о чем я думал в своей голове после прочтения о мемуаризации в Perl более высокого порядка.Две вещи, которые, я думаю, были бы полезными дополнениями:
- Необязательный параметр для указания статического метода или метода-члена, который используется для генерации ключа к кэшу.
- Необязательный способ изменить объект кэша, чтобы вы могли использовать кэш с поддержкой диска или базы данных.
Не уверен, как делать подобные вещи с атрибутами (или если они вообще возможны при такой реализации), но я планирую попытаться разобраться.
(Не по теме:Я пытался опубликовать это как комментарий, но я не понимал, что комментарии имеют такую короткую разрешенную длину, так что это не совсем подходит в качестве "ответа")
