Как эта функция C++ использует мемоизацию?

Question

#include <vector>
std::vector<long int> as;

long int a(size_t n){
  if(n==1) return 1;
  if(n==2) return -2;
  if(as.size()<n+1)
    as.resize(n+1);
  if(as[n]<=0)
  {
    as[n]=-4*a(n-1)-4*a(n-2);
  }
  return mod(as[n], 65535);
}

Приведенный выше пример кода использует мемоизацию для расчета рекурсивной формулы на основе некоторых входных данных. n.Я знаю, что здесь используется мемоизация, потому что я написал чисто рекурсивную функцию, использующую ту же формулу, но гораздо быстрее для гораздо больших значений. n.Я никогда раньше не использовал векторы, но провел небольшое исследование и понял их концепцию.Я понимаю, что мемоизация должна хранить каждое вычисленное значение, чтобы вместо повторного выполнения одних и тех же вычислений можно было просто извлечь те, которые уже были рассчитаны.

Мой вопрос:как это мемоизация и как она работает?Кажется, я не вижу в коде, в какой момент он проверяет, существует ли уже значение для n.Кроме того, я не понимаю цели if(as[n]<=0).Эта формула может давать как положительные, так и отрицательные значения, поэтому я не уверен, что именно ищет эта проверка.

---

Спасибо, я думаю, что я близок к пониманию того, как это работает, на самом деле все немного проще, чем я думал.

Я не думаю, что значения в последовательности могут когда-либо быть равными 0, поэтому у меня это должно сработать, поскольку я думаю, что n должно начинаться с 1.

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

Редактировать:Ух ты, я получил много других ответов, пока проверял код и печатал этот.Спасибо всем за помощь, думаю, теперь я это понимаю.

Answer 1

if (as[n] <= 0) это чек.Если действительные значения могут быть отрицательными, как вы говорите, тогда вам нужен другой дозорный для проверки.Могут ли действительные значения когда-либо быть равными нулю?Если нет, то просто сделайте тест if (as[n] == 0).Это упрощает написание кода, поскольку по умолчанию векторы ints заполнены нулями.

Answer 2

Кажется, что код неправильно проверяет (так как [n] <= 0) и пересчитывает отрицательные значения функции (которые кажутся примерно любыми остальными значениями).Это делает работу масштабируемой линейно с n, а не с 2^n при рекурсивном решении, поэтому она выполняется намного быстрее.

Тем не менее, лучшей проверкой было бы проверить, если (as[n] == 0), что в моей системе работает в 3 раза быстрее.Даже если функция может вернуть 0, значение 0 просто означает, что ее вычисление займет немного больше времени (хотя, если 0 является частым возвращаемым значением, вы можете рассмотреть возможность использования отдельного вектора, который помечает, было ли вычислено значение или нет, вместо использование одного вектора для хранения значения функции и того, было ли оно вычислено)

Answer 3

Если формула может возвращать как положительные, так и отрицательные значения, значит, в этой функции есть серьезная ошибка.Чек if(as[n]<=0) является предполагаемый чтобы проверить, кэшировало ли оно уже это значение вычисления.Но если формула может быть отрицательной, эта функция многократно пересчитывает это кэшированное значение...

На самом деле, вероятно, он хотел vector<pair<bool, unsigned> >, где логическое значение указывает, было ли значение рассчитано или нет.

Answer 4

Код в опубликованном виде запоминается только около 40% времени (именно тогда, когда запоминаемое значение положительное).Как отметил Крис Джестер-Янг, правильная реализация вместо этого будет проверять if(as[n]==0).Альтернативно, можно изменить сам код запоминания, чтобы он читал as[n]=mod(-4*a(n-1)-4*a(n-2),65535);

(Даже ==0 проверка будет тратить усилия, когда запоминаемое значение будет равно 0.К счастью, в вашем случае этого никогда не происходит!)

Answer 5

В этом коде есть ошибка.Он продолжит пересчитывать значения as[n] для as[n] <= 0.Он запомнит значения, которые окажутся положительными.Он работает намного быстрее, чем код без мемоизации, поскольку в as[] достаточно положительных значений, поэтому рекурсия быстро завершается.Вы можете улучшить это, используя значение больше 65535 в качестве контрольного значения.Новые значения вектора инициализируются нулем, когда вектор расширяется.