3

「不変関数」または「不変メソッド」とは、同じ引数を与えても結果が決して変わらない関数を意味します。

不変関数の事前計算された値をキャッシュしたい場合、より一般的または冗長でない解決策を誰かが知っているかどうか知りたいです。

簡単な例で私が何を意味するかを説明しましょう。

//Let's assume that ComputeStuff() returns a widely used value 
//and that 
//1. It is immutable (it will always return the same result)
//2. its performance is critical, and it cannot be accepted to compute
//   the result at each call, because the computation is too slow
//I show here a way to solve the problem, based on a cached result.
//(this example works in a case of a method with no arguments. 
// A hash would be required in order to store multiple precomputed results 
//depending upon the arguments)
private string mComputeStuff_Cached = null;
public string ComputeStuff()
{
  if (mComputeStuff_Cached != null)
    return mComputeStuff_Cached ;

  string result;
  //
  // ...
  //Do lots of cpu intensive computation in order to compute "result" 
  //or whatever you want to compute
  //(for example the hash of a long file)
  //...
  //

  mComputeStuff_Cached  = result;
  return mComputeStuff_Cached ;
}

注:
- C++ のソリューションとして C++ というタグも追加しました。これも興味があります
- 関数は「不変」または「トランザクション内で不変」と定義できるため、「不変関数」の概念はデータベース開発者にとって一般的です (これは、クエリのパフォーマンスを向上させる良い方法です)。

前もって感謝します

4

8 に答える 8

2

「メモ化」は便利な用語かもしれません。そこにはいくつかのメモ化ライブラリがあります（boostに1つあったと断言できますが、現時点では見つかりません）。「memoize」または「memoization」と選択した言語で Web 検索を行うと、いくつかのヒットが表示されます。

これはウィキブックスのきちんとした記事です: C++ の最適化/一般的な最適化手法/メモ化

于 2009-05-06T22:20:14.513 に答える
2

次のようなことを試すことができます：

#include <functional>
#include <type_traits>
#include <map>
#include <tuple>

//requires c++14
auto add_function_cache = [](auto fun) {
    using fun_type = decltype(fun);
    return ([=](auto... run_args){
        using fun_return_type = std::result_of_t<fun_type(decltype(run_args)...)>;
        static std::map<
            std::tuple<decltype(run_args)...>,
            fun_return_type
        > result_cache;
        std::tuple<decltype(run_args)...> tuple(run_args...);
        if (result_cache.find(tuple) == result_cache.end()) {
            fun_return_type rv = fun(run_args...);
            result_cache[tuple] = rv; 
            return rv; 
        }   
        else {
            return result_cache[tuple];
        }   
    }); 
};

template <typename R, class... Args> auto
add_function_cache_old(std::function<R(Args...)> fun)
-> std::function<R(Args...)>
{
    std::map<std::tuple<Args...>, R> cache;
    return [=](Args... args) mutable  {
        std::tuple<Args...> t(args...);
        if (cache.find(t) == cache.end()) {
            R rv = fun(args...);
            cache[t] = rv; 
            return rv; 
        }   
        else {
            return cache[t];
        }   
    };  
};

そして、次のように使用します。

//function_cache - usage
auto fib_cache = add_function_cache(&fib);

//function_cache_old - usage
function<decltype(fib)> fib_fn = &fib;
auto fib_cache_old = add_function_cache_old(fib_fn);

fib_cache(10);
fib_cache(10);

アイデアは、関数 (fun) を引数として取り、別の関数を返す関数を作成することです。返された関数は fun をラップし、マップ フォームの入力パラメーター (run_args) を結果に提供します。したがって、マップ (キャッシュ) で指定されたパラメーター (run_args) の結果を見つけるために、fun と同じシグネチャーを持っています。次に、キャッシュされた値または fun によって計算された結果を返します。明らかに、ルックアップが失敗した場合に備えて、fun の結果をキャッシュに追加する必要があります。

よろしく

1月

于 2015-01-05T21:56:23.050 に答える
1

まあ、次のようなデリゲートをFunc<T>使用すると、ポリモーフィズム/継承を必要とせずに再利用可能になりますが、C# にはこれ以上「組み込み」のものはありません。

using System;
static class Program {
    static void Main() {
        var func = CachedFunc.Create(() => int.Parse(Console.ReadLine()));

        Console.WriteLine(func.Value);
        Console.WriteLine(func.Value);
    }
}
static class CachedFunc {
    public static CachedFunc<T> Create<T>(Func<T> func) {
        return new CachedFunc<T>(func);
    }
}
class CachedFunc<T> {
    T value;
    Func<T> func;
    public CachedFunc(Func<T> func){
        if (func == null) throw new ArgumentNullException("func");
        this.func = func;
    }
    public T Value {
        get {
            if (func != null) {
                value = func();
                func = null;
            }
            return value;
        }
    }
    public static explicit operator T(CachedFunc<T> func) {
        return func.Value; }
}
于 2009-05-06T22:20:17.167 に答える
0

static関数内でキーワードを使用できます。一度だけ計算されます。

std::string GetWidelyUsedValue()
{
   static std::string value = ComputeStuff() ;
   return value ;
}

std::string ComputeStuff()
{
   // Compute the string here.
}
于 2009-05-06T22:25:10.570 に答える
0

constC++ ソリューションは、概説したものと非常に似ていますが、修飾されたパブリック インターフェイスと (一部の)mutableメンバーの激しい組み合わせのみが異なります。

class Computer {
    mutable string cache;
  public:
    // I wouldn't call it ComputeXXX
    // since I want to hide the implementation
    // details from my client: for the client
    // there is no change in state due to a call
    // to this function
    const string& StringVal() const {
         if (cache.empty()) {
                // compute cache
         }
         return cache;
    }
    // ...
};
于 2009-05-06T22:17:20.510 に答える
0

少し冗長にすることができます：

private string mComputeStuff_Cached = null;
public string ComputeStuff()
{
  if (mComputeStuff_Cached == null) {
    string result;
    //
    // ...
    //Do lots of cpu intensive computation in order to compute "result" 
    //or whatever you want to compute
    //(for example the hash of a long file)
    //...
    //

    mComputeStuff_Cached  = result;
  }

  return mComputeStuff_Cached ;
}

このタイプのパターンに関するその他の注意事項:

  • C++ などのメソッドを使用する場合、メンバーはそのメソッドのコンテキスト内でconst扱われるため、メンバーを変更することはできません。constただし、変更する必要があるメンバーを としてマークすることで、これをオーバーライドできますmutable。
  • 「セマンティック const」と「ビットごとの const」には違いがあります。作成者が何かを としてマークする場合、const通常は「セマンティック const」(この場合はこれを意味します) を意味しますが、コンパイラは「ビットごとの const」しか強制できません。
  • constメソッドは通常、副作用がないため、複数のスレッドから同時に呼び出すことができるという印象を呼び出し元に与えます。このタイプのパターンでは、「ビット単位」の副作用がありますが、「セマンティック」な副作用はありません。したがって、複数のスレッドがそのようなメソッドを呼び出す可能性がある場合は、この初期化を内部的に保護する必要があります。
于 2009-05-06T22:18:23.253 に答える
0

メンバー変数を可変 (キーワード) にすることができます。

これにより、const メンバー関数がこの値を変更できるようになります。中間結果をキャッシュするために常に使用しています。

于 2009-05-06T22:19:01.973 に答える
0

このコードは、C++ でほぼそのまま書き直すことができます。

class CClass
{

  private:
     std::string* mComputeStuff_Cached;

  public:
     CClass()
       mComputeStuff_Cached(NULL)
     {

     }

     ~CClass()
     {
           delete mComputeStuff_Cached;
     }


     std::string ComputeStuff()
     {
         if (mComputeStuff_Cached != NULL)
         {
             return mComputeStuff_Cached
         }
         else
         {
             std::string calcedAnswer;
             ...
             // store away answer
             mComputeStuff_Cached = new std::string(calcedAnswer);
         }
     }
};

mComputeStuff_Cached が empty() であるかどうかを確認するだけで十分かどうかはわかりません。empty() が合法的にキャッシュされた結果である可能性があります。

于 2009-05-06T22:19:42.597 に答える