有没有IDictionary的LRU实现？

Question

有没有IDictionary的LRU实现？

c#dictionarycachinglru

40

我想实现一个简单的内存LRU缓存系统，考虑使用基于IDictionary实现的哈希LRU机制解决方案。由于我的经验来自Java，我熟悉LinkedHashMap，它对我所需的功能很好：但是我在.NET中找不到类似的解决方案。

有人开发过这样的解决方案或者有类似的经验吗？

- Antonello

13个回答

10

基类库中没有实现这个功能。

在免费的方案中，像是C5的HashedLinkedList可能会有用。

如果您愿意付费，可以考虑查看这个 C# 工具包，它包含了一种实现方法。

- Reed Copsey

1

@Antonello，链接的c5似乎没有按访问顺序排序（就像LinkedHashMap能够做到的那样）。我有什么遗漏的吗？或者当它们被访问时，您是否删除并重新插入了项目？ - zod

8

LRUCache 的答案如上方示例代码（由 Martin 提供）使用了 MethodImplOptions.Synchronized，它等效于在每个方法调用周围添加 lock(this)。虽然是正确的做法，但这种全局锁会显著降低并发负载下的吞吐量。

为解决这个问题，我实现了一个适用于并发工作负载的线程安全伪LRU设计。其性能非常接近于 ConcurrentDictionary，比 MemoryCache 快约 10 倍，而且命中率比传统的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

- Alex Peck

这是正确的答案。 - Ian Kemp

6

我最近发布了一个名为LurchTable的类，以解决需要C#变体的LinkedHashMap的需求。可以在此处找到关于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

- csharptest.net

1

➕ 1 new LurchTable<string, Foo>(LurchTableOrder.Access, 10*1000) 已准备就绪。 - Chris Marisic

4

在谷歌搜索时找到了您的答案，还发现了这个：

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

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

这是一个作为最近最少使用缓存的集合类。它实现了ICollection<T>，但还暴露了其他三个成员：

Capacity，缓存可以包含的最大项目数。一旦集合达到容量，向缓存添加新项将导致最近最少使用的项被丢弃。如果在构造时将Capacity设置为0，则缓存不会自动丢弃项目。

Oldest，集合中最老（即最近最少使用）的项目。

DiscardingOldestItem，当缓存即将丢弃其最老的项时引发的事件。这是一个非常简单的实现。虽然它的Add和Remove方法是线程安全的，但不应该在重度多线程环境中使用，因为这些方法期间整个集合都被锁定。

- mcintyre321

4

这将采用Martin的代码和Mr T的建议，并使其符合Stylecop标准。同时，它也允许在值从缓存中循环出时进行处理。

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://dev59.com/MXRA5IYBdhLWcg3w_DLF#3719378
    /// </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; }
        }
    }
}

- mheyman

TryGetValue、Add和Get之间存在一些代码重复。你能否通过调用其他两个方法来实现Get方法？ - Dejan

如果你在实现Get()方法时，首先使用TryGetValue()，然后如果失败了再执行Add()，那么当另一个线程在这两个调用之间插入Add()时，就会产生潜在的错误。话虽如此，你可以将公共代码提取到私有方法中，在正确持有锁时调用它们。 - mheyman

3

EntLib的缓存应用程序块自带LRU清理选项，并且可以在内存中。但可能对于您想要的功能来说有点过重。

- JP Alioto

2

我喜欢Lawrence的实现方式。哈希表和链表结合起来是一个好的解决方案。

关于线程，我不会使用[MethodImpl(MethodImplOptions.Synchronized)]来锁定它，而是使用ReaderWriterLockSlim或自旋锁（因为争用通常很快）。

在Get函数中，我会先检查它是否已经是第一个项目，而不总是删除并添加。这样你就可以在不阻塞其他读者的情况下保持读取器锁。

- Jerry Ju

2

我不这样认为。在各种无关项目中，我肯定已经看到手动实现的几次了（可以更或少证明这一点。如果有一个，至少其中一个项目应该会使用它）。

实现起来非常简单，通常通过创建一个包含Dictionary和List的类来完成。

键放在列表中（按顺序），项放在字典中。
当向集合添加新项时，函数检查列表的长度，提取最后一个键（如果太长），然后从字典中删除键和值以进行匹配。真的没有更多的内容了。

- Orion Edwards

这是一个简单且有效的解决方案，虽然双重访问两个集合会导致性能损失（首先访问List以检索键，然后再访问Dictionary以检索值），但它确实能工作... - Antonello

1

我刚刚偶然发现了aws-sdk-net中的LruCache.cs文件：https://github.com/aws/aws-sdk-net/blob/master/sdk/src/Core/Amazon.Runtime/Internal/Util/LruCache.cs。

- Stanislav

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Martin · Accepted Answer

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

我们尽可能地改进了代码，同时确保其线程安全。我认为代码非常简单明了，但如果您需要一些解释或与如何使用它相关的指南，请不要犹豫询问。

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.TryGetValue(key, out var existingNode))
            {
                lruList.Remove(existingNode);
            }
            else 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); - here's bug if try to add already existing value
            cacheMap[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;
    }
}