C#中的LFU缓存？

Question

在C#中是否有现成的LFU缓存可以使用？

- jsight

---

我想看看你最终编写/使用的代码。 - Anthony Mastrean

我曾经写过它，但后来删掉了，因为有更好的方法（而且我的代码非常低效）。 - jsight

@Sam：是的，没错。ajmastream说它不存在。据我所知，这才是正确的答案。 :) - jsight

Sam，你个线程亡灵术士。如果你真的想要这个徽章，你需要找更老的帖子。 - Randolpho

@Greg - 哈哈...因为我写了一个（糟糕的）实现，所以我知道它在技术上不正确。但是当时我找不到网络上的其他实现，这个是最接近正确的。 :) - jsight

Answer 1

Java有很多LFU缓存实现，应该很容易移植到C#，例如请参阅：http://faq.javaranch.com/view?CachingStrategies。此外，商业.NET库也可以做到LFU缓存，例如： http://www.kellermansoftware.com/pc-38-2-net-caching-library.aspx 和 http://www.sharedcache.com/cms/ 等。肯定还有其他的库可供选择。

以下是我为C#编写的基本LFU实现代码（带有老化功能），它不完美但是作为一个好的起点： 注意：此实现不是线程安全的。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LFU {

    class LFUCache<TKey,TValue> {

        Dictionary<TKey, LinkedListNode<CacheNode>> cache = new Dictionary<TKey, LinkedListNode<CacheNode>>();
        LinkedList<CacheNode> lfuList = new LinkedList<CacheNode>();

        class CacheNode {
            public TKey Key { get; set; }
            public TValue Data { get; set; }
            public int UseCount { get; set; }
        } 

        int size;
        int age = 0;
        int agePolicy;

        public LFUCache(int size) : this(size, 1000) {
        }


        /// <summary>
        /// 
        /// </summary>
        /// <param name="size"></param>
        /// <param name="agePolicy">after this number of gets the cache will take 1 off all UseCounts, forcing old stuff to expire.</param>
        public LFUCache(int size, int agePolicy) {
            this.agePolicy = 1000;
            this.size = size;
        }

        public void Add(TKey key, TValue val) {
            TValue existing;
            if (!TryGet(key, out existing)) {
                var node = new CacheNode() {Key = key, Data = val, UseCount = 1};
                if (lfuList.Count == size) {
                    cache.Remove(lfuList.First.Value.Key);
                    lfuList.RemoveFirst();
                }

                var insertionPoint = Nodes.LastOrDefault(n => n.Value.UseCount < 2);

                LinkedListNode<CacheNode> inserted; 

                if (insertionPoint == null) {
                    inserted = lfuList.AddFirst(node);
                } else {
                    inserted = lfuList.AddAfter(insertionPoint, node);
                }
                cache[key] = inserted;
            }
        }

        IEnumerable<LinkedListNode<CacheNode>> Nodes {
            get {
                var node = lfuList.First;
                while (node != null) {
                    yield return node;
                    node = node.Next;
                }
            }
        }

        IEnumerable<LinkedListNode<CacheNode>> IterateFrom(LinkedListNode<CacheNode> node) {
            while (node != null) {
                yield return node;
                node = node.Next;
            }
        }

        public TValue GetOrDefault(TKey key) {
            TValue val;
            TryGet(key, out val);
            return val;
        }

        public bool TryGet(TKey key, out TValue val) {

            age++;
            if (age > agePolicy) {
                age = 0;
                foreach (var node in cache.Values) {
                    var v = node.Value;
                    v.UseCount--;
                }
            }

            LinkedListNode<CacheNode> data;
            bool success = false;

            if (cache.TryGetValue(key, out data)) {
                var cacheNode = data.Value;
                val = cacheNode.Data;
                cacheNode.UseCount++;

                var insertionPoint = IterateFrom(data).Last(n => n.Value.UseCount <=  cacheNode.UseCount);

                if (insertionPoint != data) {
                    lfuList.Remove(data);
                    lfuList.AddAfter(insertionPoint, data);
                }

            } else {
                val = default(TValue);
            }

            return success;
        }
    }

    class Program {


        public static void Assert(bool condition, string message) {
            if (!condition) {
                Console.WriteLine("Assert failed : " + message);
                throw new ApplicationException("Test Failed"); 
            }
        }

        public static void RunAllTests(Program prog){
            foreach (var method in prog.GetType().GetMethods()) {
                if (method.Name.StartsWith("Test")) {
                    try {
                        method.Invoke(prog, null);
                        Console.WriteLine("Test Passed: " + method.Name);
                    } catch (Exception) {
                        Console.WriteLine("Test Failed : " + method.Name);
                    }

                }
            }
        }

        public void TestItemShouldBeThereOnceInserted() {
            var cache = new LFUCache<string, int>(3);

            cache.Add("a", 1);
            cache.Add("b", 2);
            cache.Add("c", 3);
            cache.Add("d", 4); 

            Assert(cache.GetOrDefault("a") == 0, "should get 0");
            Assert(cache.GetOrDefault("b") == 2, "should get 2");
            Assert(cache.GetOrDefault("c") == 3, "should get 3");
            Assert(cache.GetOrDefault("d") == 4, "should get 4");
        }

        public void TestLFUShouldWorkAsExpected() {

            var cache = new LFUCache<string, int>(3);

            cache.Add("a", 1);
            cache.Add("b", 2);
            cache.Add("c", 3);

            cache.GetOrDefault("a");
            cache.GetOrDefault("a");
            cache.GetOrDefault("b");

            cache.Add("d", 4);
            cache.Add("e", 5);


            Assert(cache.GetOrDefault("a") == 1, "should get 1");
            Assert(cache.GetOrDefault("b") == 2, "should get 0");
            Assert(cache.GetOrDefault("c") == 0, "should get 0");
            Assert(cache.GetOrDefault("d") == 0, "should get 4");
            Assert(cache.GetOrDefault("e") == 5, "should get 5");

        } 


        static void Main(string[] args) {
            RunAllTests(new Program());
            Console.ReadKey();
        }


    }
}

- Sam Saffron

Answer 2

截至.NET 3.5，框架中不存在这样的集合。Ayende创建了一个最近最少使用的集合，这可能是一个很好的起点（代码）。

- Anthony Mastrean

---

我添加了一个实现，因此这不再是正确的答案 :p - Sam Saffron

Sam，从框架的角度来看，我的答案仍然是正确的。你的答案非常好，我甚至会点赞，但是我先到这里了 B-) - Anthony Mastrean

我已更新代码链接，以便跳转到 GitHub 上的最新存储库。 - Anthony Mastrean

Answer 3

我自己制作了一个，供参考：

https://github.com/ysharplanguage/GenericMemoryCache

（它不仅支持LFU，还支持LRU/MRU，并且可以扩展到其他驱逐和替换策略，如果有需要的话）

希望这可以帮助到您，

- YSharp

Answer 4

你可以查阅 MS "Velocity"。我不确定它们提供了什么样的缓存策略，但这值得一看。另外，你也可以扩展Caching Application Block所提供的策略。

- JP Alioto

Answer 5

试试CacheCrow，它是一个简单的LFU、基于时间的缓存。

- Rishabh Kumar