Будьте в спящем режиме HQL: как использовать комплекс, оставленный выборку соединения

Мемуализация обменивает время на пространство.

Мемоизация может превратить экспоненциальное время (или хуже) в линейное время (или лучше) применительно к задачам, которые являются многорекурсивными по своей природе. Стоимость, как правило, составляет O (n) место.

Классическим примером является вычисление последовательности Фибоначчи. Определение из учебника является рекуррентным соотношением:

F (n) = F (n-1) + F (n-2)

Реализовано наивно, похоже this:

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

Вы можете видеть, что время выполнения растет экспоненциально с n, потому что каждая из частичных сумм вычисляется несколько раз.

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

int fib(int n) {
  static bool initialized = false;
  static std::vector<int> memo;

  if (!initialized) {
    memo.push_back(0);
    memo.push_back(1);
    initialized = true;
  }

  if (memo.size() > n) {
    return memo[n];
  }
  else {
    const int val = fib(n-1) + fib(n-2);
    memo.push_back(val);
    return val;
  }
}

Синхронизация этих двух реализаций на моем ноутбуке, для n = 42, наивная версия занимает 6,5 секунды. Записанная версия занимает 0,005 секунды (все системное время, то есть оно связано с вводом / выводом). При n = 50 запомненная версия по-прежнему занимает 0,005 секунды, а наивная версия, наконец, заканчивается через 5 минут & amp; 7 секунд (не говоря уже о том, что они оба переполнили 32-битное целое число).