我们以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;
      }
    };
}

有更好的选择吗？

最佳答案

使用 .net 4.0 的 ConcurrentDictionary<A, R>没有不必要的Lazy<R> .
关键是GetOrAdd(A, Func<A, R>)它呈现为一个非常简单的 lambda。

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);
};

更新 上述解决方案确实允许多个同时读取器和写入器以最小的开销。但是，它并不能阻止 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;
}

更新 对预填充的 1000 项缓存的一百万次读取的计时测试显示 19 毫秒 ConcurrentDictionary -- 与常规相同 Dictionary -- 但是对于 Lazy 是 720ms版本。

如果这听起来太陡峭，您可以通过更复杂的解决方案来两全其美。

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;
    };
}

关于c# - 线程安全的内存，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1254995/