2016 - 2024

感恩一路有你

lru算法例题 lru算法?

浏览量:1253 时间:2021-03-16 19:37:06 作者:admin

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的关键是看页面在一定时间段内的使用频率!

lru算法例题 lru算法图解 lru是什么算法

版权声明:本文内容由互联网用户自发贡献,本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。