¿Hay alguna implementación LRU de IDictionary?

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?

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

En el lado libre, tal vez algo como la HashedLinkedList de C5 funcionaría.

Si está dispuesto a pagar, tal vez consulte este kit de herramientas de C #. Contiene una implementación.

Esta es una implementación muy simple y rápida que desarrollamos 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 { private int capacity; private Dictionary>> cacheMap = new Dictionary>>(); private LinkedList> lruList = new LinkedList>(); public LRUCache(int capacity) { this.capacity = capacity; } [MethodImpl(MethodImplOptions.Synchronized)] public V get(K key) { LinkedListNode> 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 cacheItem = new LRUCacheItem(key, val); LinkedListNode> node = new LinkedListNode>(cacheItem); lruList.AddLast(node); cacheMap.Add(key, node); } private void RemoveFirst() { // Remove from LRUPriority LinkedListNode> node = lruList.First; lruList.RemoveFirst(); // Remove from cache cacheMap.Remove(node.Value.key); } } class LRUCacheItem { public LRUCacheItem(K k, V v) { key = k; value = v; } public K key; public V value; } } 

Encontré tu respuesta mientras buscabas en Google, también encontré esto:

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

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

Esta es una clase de colección que funciona como una memoria caché utilizada menos recientemente. Implementa ICollection , pero también expone a otros tres miembros:

  • Capacity , la cantidad máxima de elementos que la memoria caché puede contener. Una vez que la colección está en capacidad, agregar un nuevo elemento a la memoria caché hará que se descarte el elemento utilizado menos recientemente. Si la Capacidad se establece en 0 en la construcción, la memoria caché no descartará automáticamente los elementos.
  • Oldest , el más antiguo (es decir, el que se usó menos recientemente) en la colección.
  • DiscardingOldestItem , un evento generado cuando la memoria caché está a punto de descartar su elemento más antiguo. Esta es una implementación extremadamente simple. Si bien sus métodos Agregar y Eliminar son seguros para la ejecución de subprocesos, no deberían usarse en entornos pesados ​​de subprocesamiento múltiple porque toda la colección está bloqueada durante esos métodos.

Recientemente he lanzado una clase llamada LurchTable para abordar la necesidad de una variante C # de LinkedHashMap. Puede encontrar una breve discusión de LurchTable aquí .

Caracteristicas basicas:

  • Diccionario concurrente vinculado por inserción, modificación o acceso
  • Soporte de la interfaz Dictionary / ConcurrentDictionary
  • Peek / TryDequeue / Dequeue accede a la entrada ‘más antigua’
  • Permite un límite estricto en los artículos aplicados durante 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.Colecciones

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

PM> Install-Package CSharpTest.Net.Collections

Esto toma el código de Martin con las sugerencias del Sr. T 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; ///  /// A least-recently-used cache stored like a dictionary. ///  ///  /// The type of the key to the cached item ///  ///  /// The type of the cached item. ///  ///  /// Derived from https://stackoverflow.com/a/3719378/240845 ///  public class LruCache { private readonly Dictionary> cacheMap = new Dictionary>(); private readonly LinkedList lruList = new LinkedList(); private readonly Action dispose; ///  /// Initializes a new instance of the  /// class. ///  ///  /// Maximum number of elements to cache. ///  ///  /// When elements cycle out of the cache, disposes them. May be null. ///  public LruCache(int capacity, Action dispose = null) { this.Capacity = capacity; this.dispose = dispose; } ///  /// Gets the capacity of the cache. ///  public int Capacity { get; } /// Gets the value associated with the specified key. ///  /// The key of the value to get. ///  ///  /// 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 ///  parameter. This parameter is passed /// uninitialized. ///  ///  /// true if the  /// contains an element with the specified key; otherwise, false. ///  public bool TryGetValue(TKey key, out TValue value) { lock (this.cacheMap) { LinkedListNode 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; } } ///  /// Looks for a value for the matching . If not found, /// calls  to retrieve the value and add it to /// the cache. ///  ///  /// The key of the value to look up. ///  ///  /// Generates a value if one isn't found. ///  ///  /// The requested value. ///  public TValue Get(TKey key, Func valueGenerator) { lock (this.cacheMap) { LinkedListNode 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(cacheItem); this.lruList.AddLast(node); this.cacheMap.Add(key, node); } return value; } } ///  /// Adds the specified key and value to the dictionary. ///  ///  /// The key of the element to add. ///  ///  /// The value of the element to add. The value can be null for reference types. ///  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 node = new LinkedListNode(cacheItem); this.lruList.AddLast(node); this.cacheMap.Add(key, node); } } private void RemoveFirst() { // Remove from LRUPriority LinkedListNode 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; } } } } 

Yo 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 una List .

Las teclas van en la lista (en orden) y los artículos van en el diccionario.
Cuando agrega un nuevo elemento a la colección, la función verifica 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 para eso realmente

El bloque de aplicación de almacenamiento en caché de EntLib tiene una opción de eliminación de LRU lista para usar y puede estar en la memoria. Puede ser un poco pesado para lo que quieras aunque.

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

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

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