Как выполнить потокобезопасную функцию memoization в С#?

Здесь, при переполнении стека, я нашел код, который memoizes функции с одним аргументом:

static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
    var d = new Dictionary<A, R>();
    return a=> 
    {
        R r;
        if (!d.TryGetValue(a, out r))
        {
            r = f(a);
            d.Add(a, r);
        }
        return r;
    };
}

Хотя этот код выполняет свою работу для меня, он иногда не работает, когда memoized функция вызывается из нескольких потоков одновременно: метод Add вызывается дважды с тем же аргументом и выдает исключение.

Как я могу сделать memoization потокобезопасным?

Ответы

Ответ 1

Вы можете использовать ConcurrentDictionary.GetOrAdd, который делает все, что вам нужно:

static Func<A, R> ThreadsafeMemoize<A, R>(this Func<A, R> f)
{
    var cache = new ConcurrentDictionary<A, R>();

    return argument => cache.GetOrAdd(argument, f);
}

Функция f должна быть самой потокобезопасной, поскольку она может быть вызвана из нескольких потоков одновременно.

Этот код также не гарантирует, что функция f вызывается только один раз за уникальное значение аргумента. Его можно назвать много раз, по сути, в загруженной среде. Если вам нужен такой контракт, вы должны посмотреть ответы в этом вопросе , но имейте в виду, что они не столь компактны и требуют использования блокировок.

Ответ 2

Как упоминал Гман ConcurrentDictionary, это предпочтительный способ сделать это, однако, если это не доступно для простого оператора lock, будет достаточно.

static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
    var d = new Dictionary<A, R>();
    return a=> 
    {
        R r;
        lock(d)
        {
            if (!d.TryGetValue(a, out r))
            {
                r = f(a);
                d.Add(a, r);
            }
        }
        return r;
    };
}

Одна потенциальная проблема с использованием блокировок вместо ConcurrentDictionary заключается в том, что этот метод может вводить взаимоблокировки в вашу программу.

У вас есть две memoized функции _memo1 = Func1.Memoize() и _memo2 = Func2.Memoize(), где _memo1 и _memo2 являются переменными экземпляра.
вызовы Thread1 _memo1, Func1 начинает обработку.
Thread2 вызывает _memo2, внутри Func2 есть вызов блоков _memo1 и Thread2.
Обработка Thread1 Func1 переходит к вызову _memo2 в конце функции, блоки Thread1.
ТУПИК!

Итак, если это вообще возможно, используйте ConcurrentDictionary, но если вы не можете и вы используете блокировки, вместо этого не вызывайте другие Memoized функции, которые ограничены вне функции, в которой вы работаете, когда внутри Memoized функции или вы открываете себя (если _memo1 и _memo2 были локальными переменными вместо переменных экземпляра, тупик бы не произошел).

(Обратите внимание, что производительность может быть немного улучшена с помощью ReaderWriterLock, но у вас все еще будет такая же проблема взаимоблокировки.)

Ответ 3

используя System.Collections.Generic;

Dictionary<string, string> _description = new Dictionary<string, string>();
public float getDescription(string value)
{
     string lookup;
     if (_description.TryGetValue (id, out lookup)) {
        return lookup;
     }

     _description[id] = value;
     return lookup;
}