代码之家 › 专栏 › 技术社区 › Alberto Chiesa

在C#[关闭]中实现记忆化

memoization functional-programming c#

Alberto Chiesa · 技术社区 · 6 年前

我知道这个话题(回忆录)已经讨论了很多次了(比如 here ),但是没有一个答案能像我所希望的那样满足干涸的原则,所以请阅读整个问题和我想说的三点。

我有这样一个简单的支持类:

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

现在,即使生成的代码不是很吵, :

构造函数中的一行(不能是内联初始化),用于链接这两行(函数签名的第三次重复!)。

有没有关于删除一个(或两个)策略的建议以上几点都可以。

2 回复 | 直到 6 年前

Alberto Chiesa 6 年前

在我为优雅而奋斗的过程中,我终于找到了我认为最好的语法:

private class MemoizedTest
{
    private int _counter = 0;

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

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

Ben 6 年前

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

    }
}