¿Hay alguna implementación LRU de IDictionary?

Question

Me gustaría implementar un sistema simple de memoria caché LRU en memoria y estaba pensando en una solución basada en una implementación IDictionary que podría manejar un mecanismo LRU hash. Viniendo de Java, tengo experiencias con LinkedHashMap, que funciona bien para lo que necesito: no puedo encontrar en ninguna parte una solución similar para .NET.

¿Alguien lo ha desarrollado o alguien ha tenido experiencias como esta?

Answer 1

No hay nada en las bibliotecas de la clase base que haga esto.

En el lado libre, quizás algo como C5 HashedLinkedList funcionaría.

Si está dispuesto a pagar, tal vez eche un vistazo a this C# toolkit. Contiene una implementación.

Answer 2

No lo creo. Ciertamente he visto implementados a mano varias veces en varios proyectos no relacionados (lo cual más o menos confirma esto. Si hubiera uno, seguramente al menos uno de los proyectos lo habría usado).

Es bastante simple de implementar, y generalmente se hace creando una clase que contiene tanto un Dictionary como un List.

Las claves van en la lista (en orden) y los elementos van en el diccionario.
Cuando agrega un nuevo elemento a la colección, la función comprueba la longitud de la lista, saca la última clave (si es demasiado larga) y luego desaloja la clave y el valor del diccionario para que coincida. No mucho más en realidad

Answer 3

El Caching Application Block de EntLib tiene una opción LRU de eliminación de la caja y puede estar en la memoria. Puede ser un poco pesado para lo que quieras aunque.

Answer 4

Si se trata de una aplicación asp.net, puede usar la clase de caché [1] pero estará compitiendo por espacio con otras cosas en caché, que pueden ser lo que desee o no.

[1] http://msdn.microsoft.com/en-us/library/system.web.caching.cache.aspx

Answer 5

Esto una manera muy sencilla una implementación rápida que hemos desarrollado para un sitio web que poseemos.

Intentamos mejorar el código tanto como sea posible pero manteniéndolo seguro. Creo que el código es muy simple y claro, pero si necesita alguna explicación o una guía relacionada con cómo usarlo, no dude en preguntar.

namespace LRUCache 
{ 
    public class LRUCache<K,V> 
    { 
     private int capacity; 
     private Dictionary<K, LinkedListNode<LRUCacheItem<K, V>>> cacheMap = new Dictionary<K, LinkedListNode<LRUCacheItem<K, V>>>(); 
     private LinkedList<LRUCacheItem<K, V>> lruList = new LinkedList<LRUCacheItem<K, V>>(); 

     public LRUCache(int capacity) 
     { 
      this.capacity = capacity; 
     } 

     [MethodImpl(MethodImplOptions.Synchronized)] 
     public V get(K key) 
     { 
      LinkedListNode<LRUCacheItem<K, V>> node; 
      if (cacheMap.TryGetValue(key, out node)) 
      { 
       V value = node.Value.value; 
       lruList.Remove(node); 
       lruList.AddLast(node); 
       return value; 
      } 
      return default(V); 
     } 

     [MethodImpl(MethodImplOptions.Synchronized)] 
     public void add(K key, V val) 
     { 
      if (cacheMap.Count >= capacity) 
      { 
       RemoveFirst(); 
      } 

      LRUCacheItem<K, V> cacheItem = new LRUCacheItem<K, V>(key, val); 
      LinkedListNode<LRUCacheItem<K, V>> node = new LinkedListNode<LRUCacheItem<K, V>>(cacheItem); 
      lruList.AddLast(node); 
      cacheMap.Add(key, node); 
     } 

     private void RemoveFirst() 
     { 
      // Remove from LRUPriority 
      LinkedListNode<LRUCacheItem<K,V>> node = lruList.First; 
      lruList.RemoveFirst(); 

      // Remove from cache 
      cacheMap.Remove(node.Value.key); 
     } 
    } 

    class LRUCacheItem<K,V> 
    { 
     public LRUCacheItem(K k, V v) 
     { 
      key = k; 
      value = v; 
     } 
     public K key; 
     public V value; 
    } 
} 

Answer 6

Me gusta la implementación de Lawrence. Hashtable + LinkedList es una buena solución. En cuanto a enhebrar, no bloquearía este [MethodImpl (MethodImplOptions.Synchronized)], sino que usaré ReaderWriterLockSlim o spin lock (ya que la contención generalmente es rápida). En la función get comprobaría si ya es el primer elemento primero, en lugar de siempre eliminar y agregar. Esto le da la posibilidad de mantenerse dentro de un bloqueo de lector que no bloquea a otros lectores.

Answer 7

Found su respuesta, mientras que buscando en Google, también encontramos esto:

http://code.google.com/p/csharp-lru-cache/

csharp-lru-cache: biblioteca de clases LRU colección caché

Ésta es una clase de colección que funciona como un menos recientemente- utilizado caché. Implementa ICollection<T>, pero también expone otros tres miembros:

• Capacity, el número máximo de elementos la caché puede contener. Una vez que la colección está en capacidad, agregar un nuevo elemento a la memoria caché hará que el elemento usado menos recientemente sea descartado. Si la capacidad se establece en 0 en la construcción, la memoria caché no eliminará automáticamente los elementos .
• Oldest, la más antigua (es decir, la menos recientemente utilizada) elemento de la colección.
• DiscardingOldestItem, un evento provocó cuando la memoria caché está a punto de descartar su elemento más antiguo . Esta es una implementación simple extremadamente . Si bien su Agregar y Eliminar métodos son seguros para subprocesos, no se debe utilizar en entornos pesados ​​de subprocesamiento porque la colección completa está bloqueada durante esos métodos.

Answer 8

he publicado recientemente una clase llamada LurchTable para hacer frente a la necesidad de un C# variante del LinkedHashMap. Una breve discusión del LurchTable can be found here.

Características básicas:

• Vinculado concurrente Diccionario de inserción, modificación o acceso
• Soporte de diccionario/interfaz ConcurrentDictionary
• Peek/TryDequeue/Quitar de la cola de acceso a la entrada 'más antiguo'
• Permite que dura -limit on items forzado en la inserción
• Expone eventos para agregar, actualizar y eliminar

Código

Fuente: http://csharptest.net/browse/src/Library/Collections/LurchTable.cs

GitHub: https://github.com/csharptest/CSharpTest.Net.Collections

Ayuda HTML: http://help.csharptest.net/

PM> Install-Package CSharpTest.Net.Collections

Answer 9

Esto toma Martin 's código con Mr T' s sugerencias y lo hace amigable con Stylecop. Ah, también permite la eliminación de valores a medida que salen de la memoria caché.

namespace LruCache 
{ 
    using System; 
    using System.Collections.Generic; 

    /// <summary> 
    /// A least-recently-used cache stored like a dictionary. 
    /// </summary> 
    /// <typeparam name="TKey"> 
    /// The type of the key to the cached item 
    /// </typeparam> 
    /// <typeparam name="TValue"> 
    /// The type of the cached item. 
    /// </typeparam> 
    /// <remarks> 
    /// Derived from https://stackoverflow.com/a/3719378/240845 
    /// </remarks> 
    public class LruCache<TKey, TValue> 
    { 
     private readonly Dictionary<TKey, LinkedListNode<LruCacheItem>> cacheMap = 
      new Dictionary<TKey, LinkedListNode<LruCacheItem>>(); 

     private readonly LinkedList<LruCacheItem> lruList = 
      new LinkedList<LruCacheItem>(); 

     private readonly Action<TValue> dispose; 

     /// <summary> 
     /// Initializes a new instance of the <see cref="LruCache{TKey, TValue}"/> 
     /// class. 
     /// </summary> 
     /// <param name="capacity"> 
     /// Maximum number of elements to cache. 
     /// </param> 
     /// <param name="dispose"> 
     /// When elements cycle out of the cache, disposes them. May be null. 
     /// </param> 
     public LruCache(int capacity, Action<TValue> dispose = null) 
     { 
      this.Capacity = capacity; 
      this.dispose = dispose; 
     } 

     /// <summary> 
     /// Gets the capacity of the cache. 
     /// </summary> 
     public int Capacity { get; } 

     /// <summary>Gets the value associated with the specified key.</summary> 
     /// <param name="key"> 
     /// The key of the value to get. 
     /// </param> 
     /// <param name="value"> 
     /// When this method returns, contains the value associated with the specified 
     /// key, if the key is found; otherwise, the default value for the type of the 
     /// <paramref name="value" /> parameter. This parameter is passed 
     /// uninitialized. 
     /// </param> 
     /// <returns> 
     /// true if the <see cref="T:System.Collections.Generic.Dictionary`2" /> 
     /// contains an element with the specified key; otherwise, false. 
     /// </returns> 
     public bool TryGetValue(TKey key, out TValue value) 
     { 
      lock (this.cacheMap) 
      { 
       LinkedListNode<LruCacheItem> node; 
       if (this.cacheMap.TryGetValue(key, out node)) 
       { 
        value = node.Value.Value; 
        this.lruList.Remove(node); 
        this.lruList.AddLast(node); 
        return true; 
       } 

       value = default(TValue); 
       return false; 
      } 
     } 

     /// <summary> 
     /// Looks for a value for the matching <paramref name="key"/>. If not found, 
     /// calls <paramref name="valueGenerator"/> to retrieve the value and add it to 
     /// the cache. 
     /// </summary> 
     /// <param name="key"> 
     /// The key of the value to look up. 
     /// </param> 
     /// <param name="valueGenerator"> 
     /// Generates a value if one isn't found. 
     /// </param> 
     /// <returns> 
     /// The requested value. 
     /// </returns> 
     public TValue Get(TKey key, Func<TValue> valueGenerator) 
     { 
      lock (this.cacheMap) 
      { 
       LinkedListNode<LruCacheItem> node; 
       TValue value; 
       if (this.cacheMap.TryGetValue(key, out node)) 
       { 
        value = node.Value.Value; 
        this.lruList.Remove(node); 
        this.lruList.AddLast(node); 
       } 
       else 
       { 
        value = valueGenerator(); 
        if (this.cacheMap.Count >= this.Capacity) 
        { 
         this.RemoveFirst(); 
        } 

        LruCacheItem cacheItem = new LruCacheItem(key, value); 
        node = new LinkedListNode<LruCacheItem>(cacheItem); 
        this.lruList.AddLast(node); 
        this.cacheMap.Add(key, node); 
       } 

       return value; 
      } 
     } 

     /// <summary> 
     /// Adds the specified key and value to the dictionary. 
     /// </summary> 
     /// <param name="key"> 
     /// The key of the element to add. 
     /// </param> 
     /// <param name="value"> 
     /// The value of the element to add. The value can be null for reference types. 
     /// </param> 
     public void Add(TKey key, TValue value) 
     { 
      lock (this.cacheMap) 
      { 
       if (this.cacheMap.Count >= this.Capacity) 
       { 
        this.RemoveFirst(); 
       } 

       LruCacheItem cacheItem = new LruCacheItem(key, value); 
       LinkedListNode<LruCacheItem> node = 
        new LinkedListNode<LruCacheItem>(cacheItem); 
       this.lruList.AddLast(node); 
       this.cacheMap.Add(key, node); 
      } 
     } 

     private void RemoveFirst() 
     { 
      // Remove from LRUPriority 
      LinkedListNode<LruCacheItem> node = this.lruList.First; 
      this.lruList.RemoveFirst(); 

      // Remove from cache 
      this.cacheMap.Remove(node.Value.Key); 

      // dispose 
      this.dispose?.Invoke(node.Value.Value); 
     } 

     private class LruCacheItem 
     { 
      public LruCacheItem(TKey k, TValue v) 
      { 
       this.Key = k; 
       this.Value = v; 
      } 

      public TKey Key { get; } 

      public TValue Value { get; } 
     } 
    } 
}