Función de caché resultados

Question

Para divertirme, estoy jugando con una clase para almacenar fácilmente los resultados de la función. La idea básica es que puede tomar cualquier función que desee — aunque solo desee usarla para funciones relativamente costosas — y envolverla fácilmente para usar búsquedas de diccionario relativamente económicas para ejecuciones posteriores con el mismo argumento. En realidad no hay mucho que ella:

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

Por desgracia, hay algunas restricciones adicionales que hacen que esta mucho menos útil de lo que podría ser. También hay algunas características que podríamos agregar y otras consideraciones para la implementación. Estoy buscando ideas sobre maneras en que esto se puede mejorar por cualquiera de los siguientes puntos:

• Esto requiere una función que devuelve el mismo resultado para un conjunto dado de argumentos (que debe ser sin estado). Probablemente no hay forma de cambiar esto.
• Está limitado a un rango delegado muy estrecho. ¿Podríamos expandirlo para que funcione fácilmente para cualquier función que acepte al menos un parámetro y devuelva un valor, tal vez envolviendo argumentos en un tipo anónimo? ¿O necesitaríamos una implementación adicional para cada delegado de Func que quisiéramos apoyar? Si es así, ¿podemos construir una clase abstracta para hacer esto más fácil?
• No es seguro para subprocesos.
• Sin invalidación automática. Esto lo hace peligroso para la recolección de basura. Debes mantenerlo por un tiempo para que sea útil, y eso significa que realmente nunca descartarás elementos de caché viejos y potencialmente innecesarios.
• ¿Podemos heredar esto para hacer que la memoria caché sea bidireccional para el caso en el que la función tiene un único argumento?

Como punto de referencia, si alguna vez uso esto en código real el lugar más probable que visualizo es como parte de una capa de lógica de negocios, donde utilizo este código para ajustar un método en la capa de acceso a datos que simplemente extrae datos de una tabla de búsqueda. En este caso, el viaje de la base de datos sería costoso en relación con el diccionario y casi siempre habría exactamente un valor 'clave' para la búsqueda, por lo que es una buena combinación.

Answer 1

Otro nombre para este almacenamiento en caché automático de los resultados de funciones es la memorización. Para una interfaz pública, considerar algo como lo siguiente:

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

... y simplemente usar el polimorfismo para almacenar T en un diccionario de objetos.

La extensión del rango de delegado podría implementarse mediante currying y la aplicación de función parcial. Algo como esto:

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

Desde Curry vueltas de funciones múltiples argumentos en las funciones de argumentos individuales (pero que puede volver funciones), los valores de retorno son elegibles para memoization sí mismos.

Otra forma de hacerlo sería utilizar la reflexión para inspeccionar el tipo de delegado y almacenar tuplas en el diccionario en lugar de simplemente el tipo de argumento. Una tupla simplista sería simplemente una envoltura de matriz cuya lógica de códigos hash y de igualdad utilizaba comparaciones profundas y hash.

La invalidación podría mejorarse con referencias débiles, pero la creación de diccionarios con las claves WeakReference es complicada: se realiza mejor con el soporte del tiempo de ejecución (los valores de WeakReference son mucho más fáciles). Creo que hay algunas implementaciones.

Seguridad de los hilos se realiza fácilmente mediante el bloqueo en el diccionario interno para eventos de mutación, pero tener un diccionario sin bloqueo puede mejorar el rendimiento en escenarios altamente concurrentes. Ese diccionario probablemente sea aún más difícil de crear, aunque hay un interesante presentation on one for Java here.

Answer 2

ya que este es de valor educativo sobre todo - usted debe echar un vistazo a la clase WeakReference, lo que permite que el GC para limpiar las manijas no utilizados de su clase en un entorno multihilo. Es un patrón de caché bastante común en .NET

Dicho esto: ¡Caveat Emptor! Cada caché es diferente. Al construir una solución global, a menudo termina en un caso patológico donde su "caché" es solo un diccionario glorificado con muchos métodos de ayuda complicados que hacen que su código sea difícil de leer.

Answer 3

Wow - what serendipity - Acabo de publicar una pregunta acerca de opaque keys in C# ... y porque estoy tratando de implementar algo relacionado con el almacenamiento en memoria caché de los resultados de las funciones. Qué divertido.

Este tipo de metaprogramming puede ser complicado con C# ... sobre todo porque los parámetros de tipo genérico puede dar lugar a la duplicación de código incómoda. A menudo termina repitiendo casi el mismo código en varios lugares, con diferentes parámetros de tipo, para lograr seguridad de tipo.

Así que aquí es mi variación en su enfoque que utiliza mi clave patrón opaco y cierres para crear funciones cacheables. El ejemplo siguiente muestra el patrón con uno o dos argumentos, pero es relativamente fácil extenderlo a más. También utiliza métodos de extensión para crear un patrón transparente para envolver un Func <> con un Func <> con el método AsCacheable(). Los cierres capturan la memoria caché que está asociada a la función y hacen que su existencia sea transparente para otras personas que llaman.

Esta técnica tiene muchas de las mismas limitaciones que su enfoque (seguridad de hilos, mantenimiento de referencias, etc.) - Sospecho que no son demasiado difíciles de superar - pero SOPORTA una manera fácil de extender a múltiples parámetros , y permite que las funciones almacenables en caché sean completamente sustituibles con las regulares, ya que son solo un delegado contenedor.

También vale la pena señalar que si se crea una segunda instancia de la CacheableFunction - se obtiene una caché separada. Esto puede ser tanto una fortaleza como una debilidad ... ya que en algunas situaciones puede que no te des cuenta de que esto está sucediendo.

Aquí está el código:

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

Answer 4

estoy usando esta extensión simple, que utiliza en este caso 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}); 

    } 
} 

Ejemplo/uso: (duraciones de caché es de 42 segundos):

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