16

このコードを含む記事を見つけました：

template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)>
memoize(std::function<ReturnType (Args...)> func)
{
    std::map<std::tuple<Args...>, ReturnType> cache;
    return ([=](Args... args) mutable {
            std::tuple<Args...> t(args...);
            if (cache.find(t) == cache.end())                
                cache[t] = func(args...);
            return cache[t];
    });
}

これを説明してもらえますか？ここでは多くのことを理解できませんが、最も奇妙なことは、キャッシュがローカルで静的ではないことですが、おそらく私は間違っていて...

4

5 に答える 5

26

これは、メモ化の単純なC++1x実装です。

この関数はクロージャmemoizeを返します。戻り値は、引数（この場合は変数）を介して渡されるもの以外の状態を持つ関数です。cache

[=]匿名関数のビットは、返された関数がすべてのローカル変数のコピーを取得する必要があることを示しています。cache変数は、返された関数の呼び出し間で共有されることを意図しているため、静的ではありません。

したがって、を呼び出すたびに、memoize独自の関数を持つ異なる関数が返されcacheます。によって返される特定のクロージャへの後続の呼び出しは、そのクロージャのmemoizeから値を挿入/フェッチします。cache

これは、より古い学校のOOPバージョンとある程度同等であると考えることができます。

template <typename ReturnType, typename... Args>
class Memoize
{
    std::map<std::tuple<Args...>, ReturnType> cache;
public:
    ReturnType operator() (Args... args)
    {
        std::tuple<Args...> t(args...);
        if (cache.find(t) == cache.end())                
            cache[t] = func(args...);
        return cache[t];
    }
};
于 2011-03-18T14:20:28.643 に答える
9

キャッシュはラムダ自体に埋め込まれており、ラムダに対してローカルです。

したがって、2つのラムダを作成すると、それぞれに独自のキャッシュがあります。

ラムダがスコープから外れるとすぐに使用されるメモリがパージされ、メモリが爆発的に増加することがないため、これは単純なキャッシュを実装するための優れた方法です。

于 2011-03-18T14:20:44.540 に答える
3

「この単純なコード」は、適切に呼び出されれば、再帰関数もメモ化できます。ここに完全な例を示します。

#include <functional>
#include <iostream>
#include <tuple>
#include <map>

template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)> memoize(std::function<ReturnType (Args...)> func) {
  std::map<std::tuple<Args...>, ReturnType> cache;
  return ([=](Args... args) mutable {
          std::tuple<Args...> t(args...);
          if (cache.find(t) == cache.end())
             cache[t] = func(args...);
          return cache[t];
  });
}

std::function<int (int)> f;
int fib(int n) {
  if  (n < 2) return n;
  return f(n-1) + f(n-2);
}

std::function<int (int, int)> b;
int binomial(int n, int k) {
  if (k == 0 || n == k) return 1;
  return b(n-1, k) + b(n-1, k-1);
}

int main(void) {
  f = memoize(std::function<int (int)>(fib));
  std::cout << f(20) << std::endl;
  b = memoize(std::function<int (int, int)>(binomial));
  std::cout << b(34,15) << std::endl;
}
于 2012-11-13T23:30:14.343 に答える
2

これを見つけたブログから引用するには、コードのすぐ下にあります。

...等号は、[=]「周囲のスコープ内のローカル変数を値でキャプチャする」ことを意味します。これは、ラムダ関数を返すために必要であり、ローカル変数はその時点で消えます。

したがって、cacheは、メンバーであるかのように、返された関数オブジェクトにコピーされます。

（この単純なコードは再帰関数をメモ化できないことに注意してください。C++ 0xでの固定小数点コンビネータの実装は、読者の練習問題として残されています。）

于 2011-03-18T14:11:03.023 に答える
0

語彙スコープの素晴らしい世界へようこそ。パブリックメンバーとプライベートメンバーでタイプ全体を作成するために使用できます。関数型言語では、それがそれを行う唯一の方法であることがよくあります。

http://mark-story.com/posts/view/picking-up-javascript-closures-and-lexical-scopingを読むことをお勧めします。これは、Javascriptに関するものですが、C ++ 0xは同じ概念を追加し、（ほぼ同じ）C++への動作。

于 2011-03-18T14:10:04.187 に答える