周六早上  做了下力扣的LRU 题目  后面接着看了LFU 缓存  难度提高了不少

首先 先说下 这2着 的差别把

LRU ：最近 最少使用算法（Least  Recently Used）.LRU 是淘汰最长时间没有被使用的页面。

LFU：最不经常使用淘汰算法（Least Frequently Used）LFU 是淘汰 一段时间内，使用次数最少的页面。

看到这些  感觉都差不多  不是很明白 下面举个实例说明下问题

假设内存块大小是3：

我们所需页面顺序 也就是缓存读取页面的顺序是 如下：

1  2   1  2  1  3   4

当我们去获取页面4的时候   内存块里面 存是应该 是  1  2  3  这个时候 就会发生缺页中断 ，而且内存已经满了  需要策略去替换页面

如果我们采用的是LRU 算法  应该替换掉的是2     因为  2 是最长时间 没被访问的  1，3 在4之前别访问  所以要替换2

但是 如果采用LFU 算法  那替换的就是3   因为  在 4被访问之前  这段时间内    1访问3次   2是2次   3是1次  所以要替换 3    如果存在访问次数相同低的  删除 最久的节点   

再次举例下  1  2   1  2  1  3   3   4   如果是这样的顺序     1是3次    2是 2次  3 页是2次      但是2访问顺序在3之前   也就是呆的久   所以替换  2节点

LRU  消耗CPU 资源少   LFU 消耗CPU 资源高   自己实现下 就知道这2个的难易程度了。

好了 说了这么多  下面show code:

public class LFUCache2 { private Dictionary<int, LFUCacheEntity> dicData; //KeyValuePair public Dictionary<int, LinkedList<LFUCacheEntity>> dicFrequenNodeList;// key 是频率 value是key频率下面 所挂的node 数据节点 private int _capacity;//容量大小 private int minFre;//频率值 public LFUCache2(int capacity) { _capacity = capacity; dicData = new Dictionary<int, LFUCacheEntity>(capacity); dicFrequenNodeList = new Dictionary<int, LinkedList<LFUCacheEntity>>(); minFre = 0; dicFrequenNodeList.Add(0, new LinkedList<LFUCacheEntity>()); } public int Get(int key) { if (!dicData.ContainsKey(key)) return -1; var value = dicData[key].Value; Put(key, value); return value; } public void Put(int key, int value) { if (_capacity == 0) return; var newCacheData = new LFUCacheEntity { Key = key, Value = value, Frequen = 0 }; if (dicData.ContainsKey(key)) { var cacheEntity = dicData[key]; var oldFrequen = cacheEntity.Frequen; var oldFrequenNodeList = dicFrequenNodeList[oldFrequen]; oldFrequenNodeList.Remove(cacheEntity); var newFrequen = oldFrequen + 1; if (!dicFrequenNodeList.ContainsKey(newFrequen)) { dicFrequenNodeList.Add(newFrequen, new LinkedList<LFUCacheEntity>()); } newCacheData.Frequen = newFrequen; dicFrequenNodeList[newFrequen].AddLast(newCacheData); dicData[key] = newCacheData; if (dicFrequenNodeList.ContainsKey(minFre) && dicFrequenNodeList[minFre].Count == 0) { minFre = newFrequen; } return; } if (_capacity == dicData.Count) { var deleteNodeList = dicFrequenNodeList[minFre]; var deleteFirstNode = deleteNodeList.First; deleteNodeList.RemoveFirst(); dicData.Remove(deleteFirstNode.Value.Key); } dicFrequenNodeList[0].AddLast(newCacheData); dicData.Add(key, newCacheData); minFre = 0; } } public class LFUCacheEntity { public int Key { get; set; } public int Value { get; set; } public int Frequen { get; set; } }

最后贴下 题目地址：https://leetcode-cn.com/problems/lfu-cache/

在贴下 执行的代码情况：