3

C++ とブースト、および C++11 仕様を使用したメモ化について学習しようとしています。しかし、頭を包むのに苦労しているという問題に遭遇しました。ここでチュートリアルに従っています: Memoization in Cとチュートリアルでは、テンプレートとラムダ関数を使用して再帰関数のメモ化を一般化できると述べています。このチュートリアルには、テンプレートで使用する再帰階乗関数とフィボナッチ関数もリストされています。ただし、ガイドはフィボナッチ関数のみを使用します。

これがどのように機能するかを確認し、メモ化されたフィボナッチ関数と階乗関数の両方を同じ実行で作成するテストプログラムを作成しました。つまり、メモ化テンプレートは静的マップを使用してキャッシュされた値を保存しますが、マップはメモ化された関数の各インスタンスに固有ではないようです。これは期待されていますか？各テンプレート インスタンスに固有のマップを作成するにはどうすればよいですか? C++11 の機能を使い始める前に、ブースト関数を受け入れてこのプロセスをカプセル化するテンプレート クラスを作成しようとしました。代わりに、静的マップはテンプレート クラスで一意になりますか?

メモ化された関数を作成するためのメイン ロジック

// Template function to create memoized versions of recursive lambda functions
template<typename inType, typename outType>
std::function<outType(inType) > memoize(std::function<outType(inType) > foo) {
   return [foo](inType n) {
      static std::map<inType, outType> memo;

      outType ret;
      if (memo.count(n) > 0) {
         cout << "Cache Hit" << endl;
         ret = memo[n];
         return ret;
      }
      ret = foo(n);
      memo[n] = ret;
      return ret;
   };
}

// Recursive lambda fibonacci function
std::function<int(int) > fibonacci_r = [](int n) {
   if (n <= 1) {
      return n;
   } else {
      return fibonacci_r(n - 1) + fibonacci_r(n - 2);
   }
};

// Recursive lambda factorial function
std::function<int(int) > factorial_r = [](int n) {
   if (n == 0) {
      return 1;
   } else {
      return n * factorial_r(n - 1);
   }
};

メモ化された関数をテストするためのロジック

int position = 7;
cout << "Fibonacci:" << endl;
cout << "Non Memo Fibonacci" << endl;
cout << position << "-> " << fibonacci_r(position) << endl;
cout << "Memo Fibonacci" << endl;
fibonacci_r = memoize(fibonacci_r);
cout << position << " -> " << fibonacci_r(position) << endl;

cout << endl;

cout << "Non Memo Factorial" << endl;
cout << position << " -> " << factorial_r(position) << endl;
cout << "Memo Factorial" << endl;
factorial_r = memoize(factorial_r);
cout << position << " -> " << factorial_r(position) << endl;

出力

Fibonacci:
Non Memo Fibonacci
7-> 13
Memo Fibonacci
Cache Hit
Cache Hit
Cache Hit
Cache Hit
Cache Hit
7 -> 13

Non Memo Factorial
7 -> 5040
Memo Factorial
Cache Hit
7 -> 13

出力の最後に、Memo factorial にキャッシュ ヒットがあることがわかります。ただし、キャッシュヒットが1回だけであってはならないと思います。いずれにせよ、 13 では7!なく、13はフィボナッチ メモ ラムダの下の 7 のキャッシュ値です。

4

1 に答える 1

2

あなたが書くとき

...メモ化された関数の各インスタンスに固有のマップではないようです。これは期待されていますか？

変数に対するインスタンスstaticは、パラメーターの値ではなく、型に基づいていることを忘れているようです。どちらの場合も型std::function<outType(inType)>は同じです。明らかに、インスタンスが 1 つしかない場合、 static も 1 つしかありませんmap。

部分的な解決策は次のようになります。

template<typename inType, typename outType>
std::function<outType(inType) > memoize(std::function<outType(inType) > foo) {
   static int i = 0;
   ++i;
   return [foo](inType n) {
      static std::map<int, std::map<inType, outType>> memo;
      auto& m = memo[i];
      outType ret;
      if (m.count(n) > 0) {
         cout << "Cache Hit" << endl;
         ret = m[n];
         return ret;
      }
      ret = foo(n);
      m[n] = ret;
      return ret;
   };
}

ただし、各呼び出しは独自の独立した を生成することに注意してくださいmap。もしあなたがそうするなら：

auto f1 = memoize(factorial_r);
auto f2 = memoize(factorial_r);

その後f1、同じものを共有しf2ませんmap。これは、これを非常に頻繁に行うと、最終的に大量のメモリを使用する可能性があることも意味します。

于 2013-10-22T20:33:17.010 に答える