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

您的代码看起来不错，但它不是线程安全的，因为您用于缓存先前计算的值的静态Dictionary不是线程安全的。当您对其执行读/写操作时，您需要使用适当的锁定机制。除此之外，您可能会发现函数 Memoization是一种有趣的技术。

于 2009-12-20T19:45:13.477 回答
1

非常感谢你的回答。只是在调查您的建议时分享我的发现的快速说明（我不是专业程序员）：

所以，我检查了 memoization（一个我不知道的概念），但发现它也不是线程安全的“本身”（即必须单独处理这个），并且据我所见，它实施时还有其他一些含义。

所以，我决定继续我的第一种方法，看看我是否可以让它成为线程安全的。幸运的是，我在 .NET 4.0 中找到了这个“ConcurrentDictionary”：

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

您正在寻找memoization。

在 c# 中有许多 不同的 方法可以实现这一点。

于 2009-12-20T19:45:14.833 回答