标签：时间 first 应该 nta 节点 消耗cpu count div contains
周六早上 做了下力扣的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 Dictionaryint, LFUCacheEntity> dicData; //KeyValuePair
public Dictionaryint, LinkedList> dicFrequenNodeList;// key 是频率 value是key频率下面 所挂的node 数据节点
private int _capacity;//容量大小
private int minFre;//频率值
public LFUCache2(int capacity)
{
_capacity = capacity;
dicData = new Dictionaryint, LFUCacheEntity>(capacity);
dicFrequenNodeList = new Dictionaryint, LinkedList>();
minFre = 0;
dicFrequenNodeList.Add(0, new LinkedList());
}
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());
}
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/
在贴下 执行的代码情况：
但是很奇怪的是：LFUCacheEntity 这个如果设置称类 耗时特别的块三百多毫秒 如果设置成结构就是近600毫秒 上面是我执行的结果情况
明天去研究下
LFU C# 实现
标签：时间 first 应该 nta 节点 消耗cpu count div contains
原文地址：https://www.cnblogs.com/burg-xun/p/11756317.html