поточно-запоминание

Question

Давайте Wes Dyer's подход функционировать запоминание в качестве отправной точки:

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

Проблемы заключается в том, при его использовании из нескольких потоков, мы можем попасть в беду:

Func<int, int> f = ... 
var f1 = f.Memoize(); 
... 
in thread 1: 
var y1 = f1(1); 
in thread 2: 
var y2 = f1(1); 
// We may be recalculating f(1) here! 

Давайте попробуем избежать этого. Блокировка на map:

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

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

Вот два варианта я могу думать:

Предполагая Lazy<T> класс для ленивых оценок (см here):

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

Или держать дополнительный словарь объектов для синхронизации:

public static Func<A, R> Memoize<A, R>(this Func<A, R> f) 
{ 
    var map = new Dictionary<A, R>(); 
    var mapSync = new Dictionary<A, object>(); 
    return a => 
    { 
     R value; 
     object sync; 
     lock(mapSync) 
     { 
     if (!mapSync.TryGetValue(a, out sync)) 
     { 
      sync = new object(); 
      mapSync[a] = sync; 
     } 
     } 
     lock(map) 
     { 
     if (map.TryGetValue(a, out value)) 
      return value; 
     } 
     lock(sync) 
     { 
     value = f(a); 
     lock(map) 
     { 
      map[a] = value; 
     } 
     return value; 
     } 
    }; 
} 

Любые лучшие варианты?

Answer 1

Используйте .net 4.0's ConcurrentDictionary<A, R> без необходимости Lazy<R>.
Ключ GetOrAdd(A, Func<A, R>), который превращается в красиво тривиальную лямбду.

public static Func<A, R> Memoize<A, R>(this Func<A, R> f) 
{ 
    var cache = new ConcurrentDictionary<A, R>(); 
    return a => cache.GetOrAdd(a, f); 
}; 

Update Вышеуказанное решение действительно позволяет несколько одновременных читателей & авторов с минимальными затратами. Но он не предотвращает выполнение f(a) более одного раза за одно и то же значение (в течение периода, пока он вычисляется).

Если это жизненно важно для вас, вы можете обернуть значение в Lazy<R>, но вы несете цену за каждое чтение.

public static Func<A, R> Memoize<A, R>(this Func<A, R> f) 
{ 
    var cache = new ConcurrentDictionary<A, Lazy<R>>(); 
    return a => cache.GetOrAdd(a, new Lazy<R>(() => f(a))).Value; 
} 

Update Временные тесты на миллион читает из предварительно заполненного 1000-позиционным кэш-шоу 19ms для ConcurrentDictionary - такие же, как регулярные Dictionary - но 720ms для версии Lazy.

Если это звучит слишком круто, вы можете получить лучшее из обоих миров с более сложным решением.

public static Func<A, R> Memoize<A, R>(this Func<A, R> f) 
{ 
    var cache = new ConcurrentDictionary<A, R>(); 
    var syncMap = new ConcurrentDictionary<A, object>(); 
    return a => 
    { 
     R r; 
     if (!cache.TryGetValue(a, out r)) 
     { 
      var sync = syncMap.GetOrAdd(a, new object()); 
      lock (sync) 
      { 
       r = cache.GetOrAdd(a, f); 
      } 
      syncMap.TryRemove(a, out sync); 
     } 
     return r; 
    }; 
} 

Answer 2

Нет, они не лучшие варианты.

Версия с ленивой оценкой бессмысленна, так как вы оцениваете ее в любом случае. Версия со словарем синхронизации не работает должным образом, поскольку вы не защищаете словарь карт внутри замка перед его использованием.

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

Помните, что использование блокировки на объекте карты не защищает объект карты сам по себе, он использует только ссылку на карту в качестве идентификатора, чтобы поддерживать более одного потока за раз, чтобы запустить код внутри блокировки. Вы должны поместить весь код, который обращается к объекту внутри блокировки, а не только к коду, который меняет объект.

Answer 3

Если у вас уже есть, что Lazy<T> типа, я предполагаю, что вы используете .NET 4.0, так что вы можете также использовать ConcurrentDictionary<A,R>:

public static Func<A, R> Memoize<A, R>(this Func<A, R> f) 
{ 
    var map = new ConcurrentDictionary<A, Lazy<R>>(); 
    return a => 
    { 
     Lazy<R> lazy = new Lazy<R>(() => f(a), LazyExecutionMode.EnsureSingleThreadSafeExecution); 
     if(!map.TryAdd(a, lazy)) 
     { 
     return map[a].Value; 
     } 
     return lazy.Value; 
    }; 
} 

Answer 4

Вы читали comment from Dyer связанные с поточно- в статье ?

Возможно, самый простой способ сделать Memoize потокобезопасным - это установить замок на карту.

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

В моем примере игры RoboRally я фактически использовал функцию memoization, чтобы действовать как «суррогатный синглтон».Это не синглтон, так как на заводском экземпляре может быть один экземпляр (если фабрика не статична). Но это именно то, что я хотел.

Answer 5

Вы не хотите вычислять одно и то же значение дважды, и вы хотите, чтобы многие потоки могли одновременно вычислять значения и/или извлекать значения. Для этого вам нужно будет использовать некоторую переменную состояния и систему мелкозернистого запирания.

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

public static Func<A, R> Memoize<A, R>(this Func<A, R> f) 
    { 
     var map = new Dictionary<A, R>(); 
     var mapSync = new Dictionary<A, object>(); 
     return a => 
     { 
      R value; 
      object sync = null; 
      bool calc = false; 
      bool wait = false; 
      lock (map) 
      { 
       if (!map.TryGetValue(a, out value)) 
       { 
        //its not in the map 
        if (!mapSync.TryGetValue(a, out sync)) 
        { 
         //not currently being created 
         sync = new object(); 
         mapSync[a] = sync; 
         calc = true; 

        } 
        else 
        { 
         calc = false; 
         wait = true; 
        } 
       } 
      } 
      if(calc) 
      { 
       lock (sync) 
       { 
        value = f(a); 
        lock (map) 
        { 
         map.Add(a, value); 
         mapSync.Remove(a); 
        } 
        Monitor.PulseAll(sync); 
        return value; 
       } 
      } 
      else if (wait) 
      { 
       lock (sync) 
       { 
        while (!map.TryGetValue(a, out value)) 
        { 
         Monitor.Wait(sync); 
        } 
        return value; 
       } 
      } 

      lock (map) 
      { 
       return map[a]; 
      } 

     }; 
    } 

Это просто первая попытка, но я думаю, что это демонстрирует технику. Здесь вы торгуете дополнительной памятью для скорости.

Answer 6

Ответ Томаса, похоже, не компилируется в .NET 4.0 из-за параметра перечисления в конструктор Lazy. Я пересмотрел его ниже. Я также добавил необязательный параметр для поставки собственного анализатора равенства. Это полезно, если TInput не реализует свои собственные Equals или если TInput является строкой, и вы хотите сделать его регистрозависимым, например.

public static Func<TInput, TResult> Memoize<TInput, TResult>(
     this Func<TInput, TResult> func, IEqualityComparer<TInput> comparer = null) 
    { 
     var map = comparer == null 
         ? new ConcurrentDictionary<TInput, Lazy<TResult>>() 
         : new ConcurrentDictionary<TInput, Lazy<TResult>>(comparer); 

     return input => 
       { 
        var lazy = new Lazy<TResult>(() => func(input), LazyThreadSafetyMode.ExecutionAndPublication); 

        return map.TryAdd(input, lazy) 
           ? lazy.Value 
           : map[input].Value; 
       }; 
    } 

Я сделал некоторые основные испытания этого метода, используя это как мой тест:

public void TestMemoize() 
    { 
     Func<int, string> mainFunc = i => 
            { 
             Console.WriteLine("Evaluating " + i); 
             Thread.Sleep(1000); 
             return i.ToString(); 
            }; 

     var memoized = mainFunc.Memoize(); 

     Parallel.ForEach(
      Enumerable.Range(0, 10), 
      i => Parallel.ForEach(Enumerable.Range(0, 10), j => Console.WriteLine(memoized(i)))); 
    } 

Это, кажется, работает правильно.

Answer 7

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

Я назвал его SynchronizedConcurrentDictionary, и это выглядит следующим образом:

public class SynchronizedConcurrentDictionary<TKey, TValue> : ConcurrentDictionary<TKey, TValue> 
{ 
    private readonly ReaderWriterLockSlim _cacheLock = new ReaderWriterLockSlim(); 

    public new TValue GetOrAdd(TKey key, Func<TKey, TValue> valueFactory) 
    { 
     TValue result; 

     _cacheLock.EnterWriteLock(); 
     try 
     { 
      result = base.GetOrAdd(key, valueFactory); 
     } 
     finally 
     { 
      _cacheLock.ExitWriteLock(); 
     } 

     return result; 
    } 
} 

Тогда функция Memoize становится два лайнера:

public static Func<A, R> Memoize<A, R>(this Func<A, R> f) 
{ 
    var cache = new SynchronizedConcurrentDictionary<A, R>(); 

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

Ура!