lru算法例题 lru算法？
lru算法？
LRU算法的设计原则是：如果一个数据最近一段时间没有被访问过，那么它在将来就不太可能被访问。换言之，当有限的空间充满数据时，应该消除最长时间未被访问的数据。
执行LRU
1。使用数组存储数据，用访问时间戳标记每个数据项。插入新数据项时，首先增加数组中现有数据项的时间戳，将新数据项的时间戳设置为0，然后将其插入数组中。每次访问数组中的数据项时，所访问数据项的时间戳都设置为0。当数组空间已满时，时间戳最大的数据项将被删除。
2. 使用链表实现，每次插入新数据时，将新数据插入链表的头部；每次缓存命中时，将数据移动到链表的头部（即访问数据）；然后在链表已满时丢弃链表末尾的数据。
3. 使用链表和HashMap。当需要插入新数据项时，如果新数据项存在于链表中（通常称为hit），请将节点移动到链表的头部。如果不存在，则创建一个新节点并将其放在链表的头部。如果缓存已满，请删除链表的最后一个节点。在访问数据时，如果链表中存在该数据项，则节点会移到链表的头，否则返回-1。这样，链表末尾的节点就是最近不可访问的数据项。
对于第一种方法，需要连续维护数据项的访问时间戳。另外，在插入数据、删除数据和访问数据时，时间复杂度为O（n）。对于第二种方法，链表的时间复杂度为O（n）。所以一般来说，第三种方法是实现LRU算法。
LFU算法LFU算法过程是什么，呵LRU算？
LRU是最近最少使用的页面替换算法（最近最少使用），即首先消除最长未使用的页面！LFU是最近使用最少的页面替换算法（最少频繁使用），即在一定时间内消除最少访问的页面！例如，第二方法的周期T是10分钟。如果每分钟分页一次，则内存块为3，如果所需的页方向为2121234，请注意，调用第4页时会出现缺页。根据LRU算法，第1页应该被替换（第1页的使用时间最长），但是第3页应该根据LFU算法被替换（第3页每十分钟才使用一次）。可以看出，LRU的关键是看页面从上次使用到调度的时间，而LFU的关键是看页面在一定时间段内的使用频率
最佳页面淘汰算法是怎样计算的？
1 50%指令序列执行225%前地址部分指令均匀走行325%后地址部分指令均匀走行：命中率=1-页面失败次数（仅使用2的幂次）/叶地址流长度算法：opt FIFO RLU（定义）（至少有两种算法）程序流程图开始：根据假设生成给定长度的指令地址流-> set initial calculation size=1~8（1，2，4，8）（第页）real memory=4~32（4，8，16，32）->输入消除算法->A->alg=FIFO（或）（LRU）->fifo->使用FIFO计算命中率->使用LRU计算命中率->输出结果->结束算法定义：理想消除算法-在最佳页面算法（OPT）之后不再需要或将在最远的将来使用的页面被淘汰了。FIFO选择内存中驻留时间最长的页并将其消除。LRU从当前时间中选择最后一次访问时间最长的页面，首先进行消页，LRU是最近一次未使用的消页算法。他的想法是删除那些没有被访问时间最长的页面。LFU是最新的最少使用页面消除算法，其思想是：永远把当前使用最少的页面去掉。
从字面上看，似乎这两种算法是相似的，很难理解。但是让我们举个例子，你可以完全理解它：
例如，内存可以存储6页，现在内存中的页是2，1，1，1，3，2
使用LRU：下一个要删除的页是1，因为它最近没有被使用过
使用LFU：要删除的页是3，因为3至少只被使用过一次说到缓存，必须考虑两点
缓存数据和目标数据的一致性。
缓存过期策略（机制）。
其中，缓存过期策略涉及消除算法。常用的消去算法如下：
FIFO:先进先出
LRU:最近最少使用
LFU:最近最少使用
注意LRU和LFU的区别。LFU算法根据数据项在一段时间内的使用次数来选择使用最少的数据项，即根据使用次数的不同来确定。LRU根据使用时间的不同而确定。
版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。
