Как эта функция 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.

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

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

Answer 1

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

Answer 2

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

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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