在 C# 中实现记忆

Question

我知道这个话题（记忆）已经被讨论了很多（比如 here），但是我找不到满足 DRY 原则的答案，所以请阅读整篇文章问题和我想说的三点。

我有一个简单的支持class像这样：

public class Memoized<T1, TResult>
{
    private readonly Func<T1, TResult> _f;

    private readonly Dictionary<T1, TResult> _cache = new Dictionary<T1, TResult>();

    public Memoized(Func<T1, TResult> f)
    {
        _f = f;
    }

    public TResult Invoke(T1 p1)
    {
        if (p1 == null) throw new ArgumentNullException(nameof(p1));

        if (_cache.TryGetValue(p1, out var res)) return res;

        return _cache[p1] = _f(p1);
    }
    public static Func<T1, TResult> Of(Func<T1, TResult> f)
    {
        var memo = new Memoized<T1, TResult>(f);

        return x => memo.Invoke(x);
    }
}

没什么特别的，但它允许我这样做：

public class MyClass
{
    public Func<int, bool> MemoizedMethod { get; }

    private bool UncachedMethod(int v)
    {
        return v > 0;
    }

    public MyClass()
    {
        MemoizedMethod = Memoized<int, bool>.Of(UncachedMethod);
    }
}

现在，即使生成的代码不是很嘈杂，我也在尝试弄清楚实现是否可以更优雅，因为目前我需要:

作为方法的可调用属性。
不应直接调用的真实方法。
构造函数中的一行（不能是内联初始化）链接两者（函数签名的第三次重复！）。

任何关于允许删除上述点中的一个（或两个！）的策略的建议都会很棒。

Answer 1

如果您在 lambda 中捕获字典，您的状态将被隐式维护。

public class Memoized
{
    // Example with a single parameter. That parameter becomes the key to the dictionary.
    public static Func<T1, TRet> Of<T1, TRet>(Func<T1, TRet> f)
    {
        ConcurrentDictionary<T1, TRet> cache = new ConcurrentDictionary<T1, TRet>();
        return (arg1) => cache.GetOrAdd(arg1, xarg=>f(xarg));
    }
    // Example with two parameters. The key is a tuple, and it must be unpacked before calling func.
    // Three or more parameters generalize from this
    public static Func<T1, T2, TRet> Of<T1, T2, TRet>(Func<T1, T2, TRet> f)
    {
        ConcurrentDictionary<Tuple<T1,T2>, TRet> cache = new ConcurrentDictionary<Tuple<T1, T2>, TRet>();
        return (arg1, arg2) => cache.GetOrAdd(new Tuple<T1,T2>(arg1, arg2), 
            (xarg)=>f(xarg.Item1, xarg.Item2)
            );
    }

}

用法示例：

class Test
{
    public int Method(String s, String s2)
    {
        return 99;
    }
}
class Program
{
    static bool UncachedMethod(int x) { return x > 0; }
    static void Main(string[] args)
    {
        var cached = Memoized.Of<int,bool>(UncachedMethod);

        var exampleCall = cached(44);
        var exampleCall2 = cached(44);

        // Capture a non-static member function
        var x = new Test();
        var cachedX = Memoized.Of<String, String,int>(x.Method);

        var exampleCall3 = cachedX("a","b");

    }
}

Answer 2

在我为优雅而奋斗的过程中，我终于找到了我认为是我在任何地方看到的最好的语法：

private class MemoizedTest
{
    private int _counter = 0;

    public int Method(int p) => this.Memoized(p, x =>
    {
        return _counter += x;
    });
}

实施（一个非常小的扩展class）：

namespace System
{
    public static class MemoizerExtension
    {
        internal static ConditionalWeakTable<object, ConcurrentDictionary<string, object>> _weakCache =
            new ConditionalWeakTable<object, ConcurrentDictionary<string, object>>();

        public static TResult Memoized<T1, TResult>(
            this object context,
            T1 arg,
            Func<T1, TResult> f,
            [CallerMemberName] string? cacheKey = null)
            where T1 : notnull
        {
            if (context == null) throw new ArgumentNullException(nameof(context));
            if (cacheKey == null) throw new ArgumentNullException(nameof(cacheKey));

            var objCache = _weakCache.GetOrCreateValue(context);

            var methodCache = (ConcurrentDictionary<T1, TResult>) objCache
                .GetOrAdd(cacheKey, _ => new ConcurrentDictionary<T1, TResult>());

            return methodCache.GetOrAdd(arg, f);
        }
    }
}

说明在实现中，我使用 ConditionalWeakTable 进行缓存，有效地扩展了调用记忆的对象的内部结构。作为附加键，CallerMemberName 被用作第二个键（例如，如果显式传递 cacheKey 参数，这允许更多的记忆，并且可选地每个方法更多的记忆）。第三个键是调用的参数。

因此，我们有 3 个运行时类似字典的搜索而不是 1 个，但语法更清晰，IMO。

值得吗？不知道，但我对优雅的渴望得到了满足。

如果其他人有兴趣，我将测试包括在内以供参考：

[TestFixture]
public class MemoizerTest
{
    [Test]
    public void MemoizationWorksOnFuncs()
    {
        int counter = 0;

        Func<int, int> f = x => counter += x;

        Assert.That(this.Memoized(1, f), Is.EqualTo(1));

        Assert.That(this.Memoized(2, f), Is.EqualTo(3));

        Assert.That(this.Memoized(2, f), Is.EqualTo(3));

        Assert.That(this.Memoized(1, f), Is.EqualTo(1));
    }

    private class MemoizedTest
    {
        private int _counter = 0;

        public int Method(int p)
            => this.Memoized(p, x => { return _counter += x; });
    }

    [Test]
    public void MemoizationWorksOnInstances()
    {
        var obj1 = new MemoizedTest();

        Assert.That(obj1.Method(5), Is.EqualTo(5));
        Assert.That(obj1.Method(4), Is.EqualTo(9));
        Assert.That(obj1.Method(5), Is.EqualTo(5));
        Assert.That(obj1.Method(1), Is.EqualTo(10));
        Assert.That(obj1.Method(4), Is.EqualTo(9));

        obj1 = new MemoizedTest();

        Assert.That(obj1.Method(5), Is.EqualTo(5));
        Assert.That(obj1.Method(4), Is.EqualTo(9));
        Assert.That(obj1.Method(5), Is.EqualTo(5));
        Assert.That(obj1.Method(1), Is.EqualTo(10));
        Assert.That(obj1.Method(4), Is.EqualTo(9));
    }

    [Test]
    [Ignore("This test passes only when compiled in Release mode")]
    public void WeakMemoizationCacheIsCleared()
    {
        var obj1 = new MemoizedTest();

        var r1 = obj1.Method(5);

        MemoizerExtension._weakCache.TryGetValue(obj1, out var cache);

        var weakRefToCache = new WeakReference(cache);

        cache = null;
        GC.Collect(2);

        obj1 = null;

        GC.Collect();
        GC.Collect();

        var msg = weakRefToCache.TrackResurrection;

        Assert.That(weakRefToCache.IsAlive, Is.False, "The weak reference should be dead.");

        Assert.That(r1, Is.EqualTo(5));
    }
}

在 C# 中实现记忆

Implementing memoization in C#

c#

functional-programming

memoization