この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に基づいて再帰式を計算する上記のコードサンプル。同じ式を使用する純粋に再帰的な関数を記述したため、これはメモ化を使用することを知っていますが、これはif(as[n]<=0)のより大きな値に対してはるかに高速です。ベクトルを使用したことはありませんが、いくつかの研究を行ったことがあり、それらの概念を理解しています。メモ化は各計算値を保存することになっていることを理解しているため、同じ計算を繰り返し実行する代わりに、既に計算された値を簡単に取得できます。

私の質問は、このメモ化はどのように行われ、どのように機能するのかということです。コードには、nの値が既に存在するかどうかを確認する時点で確認できないようです。また、<=>の目的がわかりません。この式は正と負の値を生成する可能性があるため、このチェックが何を探しているのかわかりません。

---

ありがとう、私はこれがどのように機能するかを理解しつつあると思います。実際には思っていたよりも少し簡単です。

シーケンス内の値が0になることはないと思うので、nを1から開始する必要があると思うので、これはうまくいくはずです。

ただし、ゼロがシーケンス内で実行可能な数値であった場合、それを解決できる別の方法は何ですか？たとえば、5つが表示されない場合はどうなりますか？ベクトルを5で埋めるだけでいいですか？

編集：うわー、コードをチェックしてこのコードを入力すると、他にもたくさんの応答がありました。皆の助けに感謝します、私は今それを理解していると思います。

Answer 1

if (as[n] <= 0)はチェックです。あなたが言うように有効な値が負になる可能性がある場合は、チェックするために別のセンチネルが必要です。有効な値をゼロにすることはできますか？そうでない場合は、テストをif (as[n] == 0)にしてください。これにより、デフォルトでint sのベクトルがゼロで埋められるため、コードを記述しやすくなります。

Answer 2

コードは（[[]] <！> lt; = 0）を誤ってチェックしているように見え、関数の負の値（ほぼ1つおきの値であるように見える）を再計算します。これにより、再帰的ソリューションでは2 ^ nではなくnで作業スケールが線形になり、はるかに高速に実行されます。

それでも、（as [n] == 0）かどうかをテストすることで、システムで3倍高速に動作するように見えます。関数が0を返すことができる場合でも、0値は計算に少し時間がかかることを意味します（ただし、0が頻繁な戻り値である場合、値が計算されたかどうかのフラグを立てる別のベクトルを考慮することをお勧めします）単一のベクトルを使用して関数の値とその値が計算されたかどうかを保存します）

Answer 3

式が正と負の両方の値を生成できる場合、この関数には重大なバグがあります。チェックif(as[n]<=0)は、計算のこの値をすでにキャッシュしていたかどうかをチェックすることを想定しています。しかし、式が負になる可能性がある場合、この関数はこのキャッシュされた値を再計算します...

本当に望んでいたのはvector<pair<bool, unsigned> >で、値が計算されたかどうかをブールが示します。

Answer 4

コードは、投稿されたとおり、約40％の時間のみを記憶しています（正確に記憶された値が正の場合）。 Chris Jester-Youngが指摘したように、正しい実装では代わりにif(as[n]==0)をチェックします。あるいは、メモ化コード自体を変更してas[n]=mod(-4*a(n-1)-4*a(n-2),65535);

を読み取ることができます

（==0チェックでさえ、メモされた値が0であった場合に労力を費やすことになります。幸いなことに、あなたの場合、これは起こりません！）

Answer 5

このコードにはバグがあります。 as [n] <！> lt; = 0に対してas [n]の値を再計算し続けます。結果が正であることが判明したaの値をメモします。 as []の正の値が十分であるため、メモ化なしのコードよりもはるかに高速に動作し、再帰がすぐに終了します。これを改善するには、65535より大きい値を番人として使用します。ベクトルが展開されると、ベクトルの新しい値はゼロに初期化されます。