是否存在IDictionary的LRU实现？

Question

我想实现一个简单的内存LRU缓存系统,我正在考虑一个基于IDictionary实现的解决方案,它可以处理散列LRU机制.来自java,我有经验LinkedHashMap,可以满足我的需要:我找不到任何类似的.NET解决方案.

有人开发过它或有没有人有这样的经历？

Answer 1

这是我们为我们拥有的网站开发的一个非常简单的快速实现.

我们尽可能地改进代码但保持线程安全.我认为代码非常简单明了,但是如果您需要一些解释或指导如何使用它,请不要犹豫.

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 2

基类库中没有任何内容可以执行此操作.

在免费方面,也许像C5的HashedLinkedList这样的东西可行.

如果您愿意付费,可以查看这个C#工具包. 它包含一个实现.

Answer 3

LRUCache上面示例代码的答案（由 Martin 提供）使用，MethodImplOptions.Synchronized这相当于放置lock(this)每个方法调用。虽然正确，但此全局锁将显着降低并发负载下的吞吐量。

为了解决这个问题，我实现了一个专为并发工作负载设计的线程安全伪 LRU。性能非常接近ConcurrentDictionary，比传统 LRU 快约 10 倍MemoryCache，命中率优于传统 LRU。下面的 GitHub 链接提供了完整的分析。

用法如下：

int capacity = 500;
var lru = new ConcurrentLru<int, SomeItem>(capacity);

var value = lru.GetOrAdd(1, (k) => new SomeItem(k));

GitHub： https: //github.com/bitfaster/BitFaster.Caching

Install-Package BitFaster.Caching

Answer 4

发现你在google搜索时回答,也发现了这个:

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

csharp-lru-cache:LRU缓存集合类库

这是一个集合类,它起到最近最少使用的缓存的作用.它实现了ICollection<T>,但也暴露了其他三个成员:

• Capacity,缓存可以包含的最大项目数.一旦集合处于容量状态,向缓存中添加新项将导致最近最少使用的项被丢弃.如果在构造时将容量设置为0,则缓存不会自动丢弃项目.
• Oldest,集合中最早的(即最近最少使用的)项目.
• DiscardingOldestItem,当缓存即将丢弃其最旧的项目时引发的事件.这是一个非常简单的实现.虽然它的Add和Remove方法是线程安全的,但它不应该用在繁重的多线程环境中,因为整个集合在这些方法中被锁定.

Answer 5

我最近发布了一个名为 LurchTable 的类来满足对 LinkedHashMap 的 C# 变体的需求。可以在此处找到对LurchTable 的简要讨论。

基本功能：

• 通过插入、修改或访问链接的并发字典
• Dictionary/ConcurrentDictionary 接口支持
• Peek/TryDequeue/Dequeue 访问“最旧”条目
• 允许对插入时强制执行的项目进行硬限制
• 公开事件以进行添加、更新和删除

源代码：http : //csharptest.net/browse/src/Library/Collections/LurchTable.cs

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

HTML 帮助：http : //help.csharptest.net/

PM> 安装包CSharpTest.Net.Collections