1

これが私が持っているコードです：

===========================

public class Foo
{
    //Class field to store factorial values as those are calculated
    private static Dictionary<uint, double> _factorialCache;

    public Foo()
    {
        _factorialCache = new Dictionary<uint, double>();
    }

    public double Factorial(uint inputValue)
    {
        if (inputValue < 2) return 1;

        if (_factorialCache.ContainsKey(inputValue))
            return _factorialCache[inputValue];

        _factorialCache.Add(inputValue, (double)inputValue * Factorial(inputValue - 1));

        return _factorialCache[inputValue];
    }        
}

===========================

数学的に言えば、これは機能します。興味深いことに、たとえば5の階乗が最初に計算された値である場合、キャッシュはこの計算中に2、3、4、および5の階乗を格納します（つまり、すべての「中間」階乗を格納します）。私の場合、同時に複数のFooクラスのインスタンスが存在することはありませんが、この例では、Fooの複数のインスタンスが同時に存在する可能性がある場合もカバーするために、辞書を静的として宣言することにしました。時間。

私の質問は次のとおりです。

  • これは、技術的な観点（スレッドセーフなど）から同じ値の階乗の再計算を回避するための最良の方法ですか？

  • 以前に計算された値を格納するための（静的）クラススコープ変数の必要性を回避する他のアプローチ（たとえば、遅延評価などに関連するもの）はありますか？

すべての提案を歓迎します。

ありがとう、

d。

4

3 に答える 3

2

コードは正常に見えますが、以前に計算された値をキャッシュするために使用している静的ディクショナリはスレッドセーフではないため、スレッドセーフではありません。読み取り/書き込み操作を実行するときは、適切なロックメカニズムを使用する必要があります。それ以外に、関数のメモ化は興味深いテクニックだと思うかもしれません。

于 2009-12-20T19:45:13.477 に答える
1

ご回答ありがとうございます。あなたの提案を調査している間、私の発見を共有するための簡単なメモ（私はプロのプログラマーではありません）：

それで、メモ化（私が気付いていなかった概念）をチェックしましたが、それはスレッドセーフではないこともわかりました（つまり、これを個別に処理する必要があります）。それを実装するとき、他のいくつかの意味があります。

そこで、最初のアプローチを続行して、スレッドセーフにできるかどうかを確認することにしました。幸いなことに、私はこの「ConcurrentDictionary」を.NET4.0で見つけました。

http://msdn.microsoft.com/en-us/library/dd287191(VS.100).aspx

[4.0には他にも同時コンテナがあります。]

そこで、私はこの変更されたバージョンを思いつきました。これは、キャッシュの（おそらく静的な）クラススコープのフィールドに依然依存していますが、メモ化されたバージョンよりも実装上の制約や影響が少ないと思います。

public class Foo
{
    private static ConcurrentDictionary<uint, double> _factorialCache;

    public Foo()
    {            
        if (_factorialCache == null)
            _factorialCache = new ConcurrentDictionary<uint, double>();
    }

    public double Factorial(uint inputValue)
    {
        double returnValue = 0;

        if (inputValue < 2) return 1;

        if (_factorialCache.TryGetValue(inputValue, out returnValue))
            return returnValue;

        returnValue = inputValue * Factorial(inputValue - 1);

        if (!_factorialCache.TryAdd(inputValue, returnValue))
            throw new Exception("Failed to add factorial value to the factorial cache.");

        return returnValue;
    }
}

私は今このバージョンにかなり満足していますが、改善のための提案は大歓迎です。

どうもありがとう、

d.

PS-質問を「解決済み」としてマークするにはどうすればよいですか？

于 2009-12-21T00:20:35.830 に答える
0

あなたはメモ化を探しています。

C＃でこれを実現するにはさまざま な 方法があります。

于 2009-12-20T19:45:14.833 に答える