Каков оптимальный способ реализации небольшого кэша в C # для хранения факторных значений?

Question

Вот код, который у меня есть:

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

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 могут существовать одновременно время.

Мои вопросы:

• Является ли это наилучшим способом избежать пересчета факториала для тех же значений с технической точки зрения (например, безопасность потока или подобное)?

• Существует ли какой-либо другой подход (например, связанный с отложенной оценкой или аналогичным), который позволил бы избежать необходимости (статической) переменной области действия класса для хранения ранее вычисленных значений?

Все предложения приветствуются.

Спасибо

* +1025 * д.

Answer 1

Ваш код выглядит нормально, но он не является потокобезопасным, так как статический Словарь , который вы используете для кэширования ранее вычисленных значений, не является потокобезопасным. Вам необходимо использовать надлежащие механизмы блокировки при выполнении операций чтения / записи на нем. Кроме этого вы можете найти Функция Memoization интересная техника.

Answer 2

Большое спасибо за ваши ответы. Просто короткая заметка, чтобы поделиться моими выводами при изучении ваших предложений (я не профессиональный программист):

Итак, я проверил мемоизацию (концепция, о которой я не знал), но обнаружил, что она не является поточно-ориентированной "как таковой" (т.е. об этом нужно заботиться отдельно) и, исходя из того, видно, это имеет некоторые другие последствия при его реализации.

Итак, я решил продолжить свой первый подход и посмотреть, смогу ли я сделать его поточно-ориентированным. К счастью, я нашел этот «ConcurrentDictionary» в .NET 4.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 - Как пометить вопрос как "решенный"?

Answer 3

Вы ищете памятка .

Есть много разных способов для достижения этого в c #.