当前位置：网站首页>缓存淘汰算法初步认识（LRU和LFU）

缓存淘汰算法初步认识（LRU和LFU）

2022-04-23 20:28:00 【游戏编程】

API： 即 Application Programming Interface （应用程序编程接口）。操作系统会将一些复杂的底层操作封装成简单的函数，程序员只需要调用相应的函数就实现底层细节操作。（c中有printf、scanf、fopen，在c++中API包括函数和类）
缓存淘汰算法 ：内存容量是有限的，当你要缓存的数据超出容量，就得有部分数据删除，这时候哪些数据删除，哪些数据保留，就是LRU算法和LFU算法，FU强调的是 访问次数 ，而LRU强调的是 访问时间 。
LRU： 即 Least Recently Used （最近最少使用算法）。把长期不使用的数据被认定为无用数据，在缓存容量满了后，会优先删除这些被认定的数据。
LRU 为达到存入键值对和获取键值对的时间复杂度最小，使用 哈希链表 来实现算法核心，即哈希表存key，每个key映射双向链表中的键值对，以此来达到快速搜索链表的key（哈希表搜索时间复杂度O（1））。

缓存淘汰算法初步认识（LRU和LFU） - 第1张

LFU： 即 Least Frequently Used （最不经常使用算法）。把一定时期内被访问次数最少的数据看作在将来被访问到的几率也是最小的。在缓存容量满了后，会优先删除这些被认定的数据。
LFU 为了按照频率选择淘汰，所以采用的 双哈希表 为核心算法，第一个哈希表 fre_table，其key是访问的频次，其value是一个双向链表，双向链表的每一个节点包含三个元素：key，value，以及count。第二个哈希表key_table，其key即为双向链表的key，value为指向链表中相应位置的指针。

缓存淘汰算法初步认识（LRU和LFU） - 第2张

（后续补充代码部分）
作者：易风尘

游戏编程 ️，一个游戏开发收藏夹~

如果图片长时间未显示，请使用Chrome内核浏览器。

版权声明
本文为[游戏编程]所创，转载请带上原文链接，感谢
https://www.233tw.com/algorithm/118822

边栏推荐

猜你喜欢

随机推荐