代码之家 › 专栏 › 技术社区 › Joel Coehoorn

缓存函数结果

caching .net c#

Joel Coehoorn · 技术社区 · 17 年前

为了好玩,我在玩一个类来轻松缓存函数结果。基本的想法是,你可以使用任何你想要的函数——尽管你只想把它用于相对昂贵的函数——并且很容易地将它包装起来,以便使用相对便宜的字典查找,以便以后使用相同的参数运行。其实没什么大不了的:

public class AutoCache<TKey, TValue> 
{  
    public AutoCache(Func<TKey, TValue> FunctionToCache)
    {
        _StoredFunction = FunctionToCache;
        _CachedData = new Dictionary<TKey, TValue>();
    }

    public TValue GetResult(TKey Key)
    {
        if (!_CachedData.ContainsKey(Key)) 
            _CachedData.Add(Key, _StoredFunction(Key));
        return _CachedData[Key];
    }

    public void InvalidateKey(TKey Key)
    {
        _CachedData.Remove(Key);
    }

    public void InvalidateAll()
    {
        _CachedData.Clear();
    }

    private Dictionary<TKey, TValue> _CachedData;
    private Func<TKey, TValue> _StoredFunction; 
}

不幸的是,还有一些额外的限制,使得它远不如它可能的有用。我们还可以向实现中添加一些特性和其他注意事项。我正在思考如何改进以下任何一点:

这需要一个函数为给定的参数集返回相同的结果(它必须是无状态的)。可能没办法改变这个。
它被限制在非常狭窄的代表范围内。我们是否可以扩展它以方便地为任何接受至少一个参数并返回值的函数工作,也许可以将参数包装为匿名类型?或者,对于我们想要支持的每个func代表,我们需要一个额外的实施吗?如果是这样,我们可以构建一个抽象类来简化这个过程吗?
这不是线程安全的。
无自动失效。这使得垃圾收集变得很危险。您需要将其保留一段时间,以便它发挥作用,这意味着您不会真正放弃旧的和可能不需要的缓存项。
如果函数只有一个参数,我们可以从中继承来使缓存具有双向性吗?

作为一个参考点,如果我在实际代码中使用它,我最可能想到的地方是它作为业务逻辑层的一部分,在这里我使用这个代码将一个方法包装在数据访问层中,它只是从查阅表中提取数据。在这种情况下,相对于字典来说,数据库访问将是昂贵的,并且查找几乎总是只有一个“key”值,因此这是一个很好的匹配。

4 回复 | 直到 10 年前

Joel Coehoorn 17 年前

函数结果的自动缓存的另一个名称是memoization。对于公共接口,请考虑以下几点:

public Func<T,TResult> Memoize<T,TResult>(Func<T,TResult> f)

…简单地使用多态性将t存储在对象字典中。

扩展委托范围可以通过currying和分部函数应用来实现。像这样:

static Func<T1,Func<T2,TResult>> Curry(Func<T1,T2,TResult> f)
{
    return x => y => f(x, y);
}
// more versions of Curry

自从 Curry 将多个参数的函数转换为单个参数的函数(但这可能会返回函数),返回值本身就可以进行内存化。

另一种方法是使用反射检查委托类型,并将元组存储在字典中,而不仅仅是参数类型。简单的元组将只是一个数组包装器,其散列码和相等逻辑使用了深度比较和散列。

弱引用可以帮助无效化,但创建字典时 WeakReference 键是很棘手的-最好在运行时的支持下完成(weakreference值要容易得多)。我相信有一些实现。

线程安全很容易通过为突变事件锁定内部字典来实现,但是拥有一个无锁字典可以在严重并发的情况下提高性能。那本词典可能更难编纂——有一本有趣的 presentation on one for Java here 不过。

Community Mohan Dere 9 年前

哇-什么意外的事-我最近发布了一个关于 opaque keys in C# …因为我正试图实现一些与函数结果缓存相关的东西。真有趣。

这种类型的元编程在使用C时可能很困难。尤其是因为泛型类型参数会导致代码重复。为了实现类型安全,您常常在多个地方重复几乎相同的代码,使用不同的类型参数。

下面是我对您的方法的变体,它使用我的不透明键模式和闭包来创建可缓存函数。下面的示例用一个或两个参数演示了模式,但相对而言,扩展到更多参数比较容易。它还使用扩展方法创建一个透明的模式,用于使用可计算的func来包装func<gt;。 AsCacheable() 方法。闭包捕获与函数关联的缓存,并使其存在对其他调用方透明。

这种技术与您的方法有许多相同的限制(线程安全、保持引用等),我怀疑它们并不难克服,但它支持一种简单的方法来扩展到多个参数,并且它允许可缓存函数完全替换为常规函数,因为它们只是一个包装委托。

同样值得注意的是,如果您创建了cacheablefunction的第二个实例,您将得到一个单独的缓存。这既是一种优势,也是一种劣势……因为在某些情况下,你可能没有意识到这是在发生。

代码如下:

public interface IFunctionCache
{
    void InvalidateAll();
    // we could add more overloads here...
}

public static class Function
{
    public class OpaqueKey<A, B>
    {
        private readonly object m_Key;

        public A First { get; private set; }
        public B Second { get; private set; }

        public OpaqueKey(A k1, B k2)
        {
            m_Key = new { K1 = k1, K2 = k2 };
            First = k1;
            Second = k2;
        }

        public override bool Equals(object obj)
        {
            var otherKey = obj as OpaqueKey<A, B>;
            return otherKey == null ? false : m_Key.Equals(otherKey.m_Key);
        }

        public override int GetHashCode()
        {
            return m_Key.GetHashCode();
        }
    }

    private class AutoCache<TArgs,TR> : IFunctionCache
    {
        private readonly Dictionary<TArgs,TR> m_CachedResults 
            = new Dictionary<TArgs, TR>();

        public bool IsCached( TArgs arg1 )
        {
            return m_CachedResults.ContainsKey( arg1 );
        }

        public TR AddCachedValue( TArgs arg1, TR value )
        {
            m_CachedResults.Add( arg1, value );
            return value;
        }

        public TR GetCachedValue( TArgs arg1 )
        {
            return m_CachedResults[arg1];
        }

        public void InvalidateAll()
        {
            m_CachedResults.Clear();
        }
    }

    public static Func<A,TR> AsCacheable<A,TR>( this Func<A,TR> function )
    {
        IFunctionCache ignored;
        return AsCacheable( function, out ignored );
    }

    public static Func<A, TR> AsCacheable<A, TR>( this Func<A, TR> function, out IFunctionCache cache)
    {
        var autocache = new AutoCache<A,TR>();
        cache = autocache;
        return (a => autocache.IsCached(a) ?
                     autocache.GetCachedValue(a) :
                     autocache.AddCachedValue(a, function(a)));
    }

    public static Func<A,B,TR> AsCacheable<A,B,TR>( this Func<A,B,TR> function )
    {
        IFunctionCache ignored;
        return AsCacheable(function, out ignored);
    }

    public static Func<A,B,TR> AsCacheable<A,B,TR>( this Func<A,B,TR> function, out IFunctionCache cache )
    {
        var autocache = new AutoCache<OpaqueKey<A, B>, TR>();
        cache = autocache;
        return ( a, b ) =>
                   {
                       var key = new OpaqueKey<A, B>( a, b );
                       return autocache.IsCached(key)
                                  ? autocache.GetCachedValue(key)
                                  : autocache.AddCachedValue(key, function(a, b));
                   };
    }
}

public class CacheableFunctionTests
{
    public static void Main( string[] args )
    {
        Func<string, string> Reversal = s => new string( s.Reverse().ToArray() );

        var CacheableReverse = Reversal.AsCacheable();

        var reverse1 = CacheableReverse("Hello");
        var reverse2 = CacheableReverse("Hello"); // step through to prove it uses caching

        Func<int, int, double> Average = (a,b) => (a + b)/2.0;
        var CacheableAverage = Average.AsCacheable();

        var average1 = CacheableAverage(2, 4);
        var average2 = CacheableAverage(2, 4);
    }
}

Doug 17 年前

因为这主要是为了教育价值——您应该看看weakreference类,它允许GC在多线程环境中清除类中未使用的句柄。这是.NET中非常常见的缓存模式

那是说-警告清空者!每个缓存都是不同的。通过构建一个“一网打尽”的解决方案,您通常会遇到一个病态的情况,即您的“缓存”只是一个光荣的字典,其中包含许多复杂的助手方法,这些方法使您的代码难以预测。

user2958194 10 年前

我使用的是这个简单的扩展,在本例中使用的是memorycache:

public static class FuncHelpers
{
   /// <summary>
   /// Returns a same function wrapped into cache-mechanism
   /// </summary>
   public static Func<TIn, TRes> Cached<TIn, TRes>(this Func<TIn, TRes> func, 
      Func<TIn,string> keySelector, 
      Func<TIn,CacheItemPolicy> policy)
    {
        var cache = new MemoryCache(Guid.NewGuid().ToString());

        Func<TIn, TRes> f = (item) =>
        {
            var key = keySelector(item);
            var newItem = new Lazy<TRes>(() => func(item));
            var oldItem = cache.AddOrGetExisting(key,newItem , policy(item)) as Lazy<TRes>;
            try
            {
                return (oldItem ?? newItem).Value;
            }
            catch
            {
                // Handle cached lazy exception by evicting from cache.
                cache.Remove(key);
                throw;
            }

        };
        return f;
    }

   //simplified version
   public static Func<TIn, TRes> Cached<TIn, TRes>(this Func<TIn, TRes> func, Func<TIn, string> keySelector,
        TimeSpan duration)
    {
        if (duration.Ticks<=0) return func;
        return Cached(func, keySelector,
          item => new CacheItemPolicy() {AbsoluteExpiration = DateTimeOffset.Now + duration});

    }
}

示例/用法:(缓存持续时间为42秒):

    public class CachedCalculator
    {
        private Func<int, int> _heavyExpensiveMultiplier;

        public Calculator(Func<int,int> heavyExpensiveMultiplier )
        {
            //wrap function into cached one
            this._heavyExpensiveMultiplier 
              = heavyExpensiveMultiplier.Cached(x =>/*key for cache*/ x.ToString(), TimeSpan.FromSeconds(42));
        }

        //this uses cached algorithm
        public int Compute(int x)
        {
            return _heavyExpensiveMultiplier(x);
        }
    }