3

次のようにオブジェクトを使用して戦略パターンを実装する計算機クラスがあるとstd::functionします（Scott Meyers、Effective C ++：プログラムとデザインを改善する55の特定の方法を参照）。

class Calculator
{
public:
  ...
  std::vector<double> Calculate(double x, double y)
  {
     std::vector<double> res;
     for(const Function& f : functions)
        res.push_back(f(x,y));
     return res;
  }

private:
  std::vector<Function> functions;
};

どこ

typedef std::function<double(double,double)> Function;

これが私が直面している問題です。関数fとg、両方のタイプFunctionが、最終結果を得るために内部で高価で同一の計算を実行するとします。効率を向上させるために、すべての一般的なデータをでラップし、structそれを1回計算して、引数として提供することができます。ただし、この設計にはいくつかの欠陥があります。たとえば、これにより、のシグネチャが変更され、Function一部の関数実装に不要な引数が渡される可能性があります。さらに、これらの共通データと内部データは、コード内の他のコンポーネントから隠されなくなり、コードの単純さを損なう可能性があります。

次の最適化戦略について説明したいと思います。次のようなクラスCacheFGを実装します。

  1. 与えられたdoubleと;Updateのペアを使用して内部データを計算するメソッドを定義します。とxy
  2. 現在の内部データが指定されたdoubleとCheckのペアで計算されたかどうかを判別するメソッドを定義します。xy

次にできることは、クラスの共通インスタンスを作成fして共有することです。これは、構成を使用して実行できます。したがって、以下は、補助関数とを使用した関数との作成です。gCacheFGstd::shared_ptrfgf_auxg_aux

double f_aux(double x, double y, const std::shared_ptr<CacheFG>& cache)
{
   if(not cache->Check(x,y))
      cache->Update(x,y);
   ...
}

std::shared_ptr<CacheFG> cache;
Function f = std::bind(f_aux, _1, _2, cache);
Function g = std::bind(g_aux, _1, _2, cache);

私の質問は次のとおりです。（1）これは最適化のための安全なアプローチですか？（2）この問題を解決するためのより良いアプローチはありますか？

編集：いくつかの回答の後、ここでの私の意図は、C++でメモ化手法を実装することであることがわかりました。私の目的には、最後に計算された状態だけで十分であることに注意してください。

DeadMGのおかげで、彼のアプローチを改善したものをここに書きます。彼のアイデアは、可変個引数テンプレートを使用したメモ化手法を使用することで構成されています。非参照型のみでstd::decay<Args>::typeの定義を確実にするために構成を使用する、わずかな変更を提供します。tupleそうしないと、const-reference引数を持つ関数がコンパイルエラーを引き起こします。

template<typename Ret, typename... Args>
std::function<Ret(Args...)> MemoizeLast(std::function<Ret(Args...)> f)
{
    std::tuple<typename std::decay<Args>::type...> cache;
    Ret result = Ret();
    return [=](Args... args) mutable -> Ret
    {
        if(std::tie(args...) == cache)
            return Ret(result);
        cache = std::make_tuple(args...);
        return result = f(args...);
    };
}

の移動を防ぐために、提供されたものがキャッシュされている場合resultは、そのコピーが返されます（return Ret(result)） 。args

4

2 に答える 2

6

なぜ独自のクラスを作成するのですか？のインターフェースの再作成に失敗する必要はありませんunordered_map。std::functionこの機能は、およびに基づいて再利用可能なアルゴリズムとして追加できますstd::unordered_map。可変個引数テンプレートを使用してからしばらく経ちましたが、ご理解いただければ幸いです。

template<typename Ret, typename... Args> 
std::function<Ret(Args...)> memoize(std::function<Ret(Args...)> t) {
    std::unordered_map<std::tuple<Args...>, Ret> cache;
    return [=](Args... a) mutable -> Ret {
        if (cache.find(std::make_tuple(a...)) != cache.end())
            return cache[std::make_tuple(a...)];
        else
            return cache[std::make_tuple(a...)] = t(a...);
    };
}

std::hashタプルをネイティブにサポートしているかどうかは、覚えていません。そうでない場合は、追加するか、std::mapネイティブでサポートされているものを使用する必要があります。

編集：うーん、あなたがキャッシュを共有したいと思っていることに気づきませんでした。まあ、これはそれほど難しい問題ではないはずですunordered_map。電卓にメンバーを貼り付けて参照によって渡すだけですが、そうすることのセマンティクスは少し...奇妙に思えます。

もう一度編集：最新の値だけですか？さらに簡単です。

template<typename Ret, typename... Args> 
std::function<Ret(Args...)> memoize_last(std::function<Ret(Args...)> t) {
    std::tuple<Args...> cache;
    Ret result;
    return [=](Args... a) mutable -> Ret {
        if (std::tie(a...) == cache)
            return result;
        cache = std::make_tuple(a...);
        return result = t(a...);
    };
}

複数の関数間で共有する場合、変更は同じです。クラスで宣言し、参照として渡すだけです。

于 2012-10-25T11:22:32.287 に答える
2

最適化する前に-測定します。次に、実際に同じ値で多くの計算を実行する場合は、このキャッシュオブジェクトを作成します。キャッシュのチェックと更新を非表示にして、のように CacheFG::get(x, y)使用したいと思いconst auto value = cache->get(x,y)ます。

于 2012-10-25T11:11:47.660 に答える