LRU 与 LFU 缓存数据算法

2023-10-20 08:38
文章标签 算法 lru lfu 缓存数据

本文主要是介绍LRU 与 LFU 缓存数据算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2. LRU
2.1. 原理

LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

2.2. 实现

最常见的实现是使用一个链表保存缓存数据,详细算法实现如下:


1. 新数据插入到链表头部;

2. 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;

3. 当链表满的时候,将链表尾部的数据丢弃。

2.3. 分析

【命中率】

当存在热点数据时,LRU的效率很好,但偶发性的、周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重。

【复杂度】

实现简单。

【代价】

命中时需要遍历链表,找到命中的数据块索引,然后需要将数据移到头部。


3. LRU-K
3.1. 原理

LRU-K中的K代表最近使用的次数,因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题,其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。

3.2. 实现

相比LRU,LRU-K需要多维护一个队列,用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候,才将数据放入缓存。当需要淘汰数据时,LRU-K会淘汰第K次访问时间距当前时间最大的数据。详细实现如下:


1. 数据第一次被访问,加入到访问历史列表;

2. 如果数据在访问历史列表里后没有达到K次访问,则按照一定规则(FIFO,LRU)淘汰;

3. 当访问历史队列中的数据访问次数达到K次后,将数据索引从历史队列删除,将数据移到缓存队列中,并缓存此数据,缓存队列重新按照时间排序;

4. 缓存数据队列中被再次访问后,重新排序;

5. 需要淘汰数据时,淘汰缓存队列中排在末尾的数据,即:淘汰“倒数第K次访问离现在最久”的数据。

LRU-K具有LRU的优点,同时能够避免LRU的缺点,实际应用中LRU-2是综合各种因素后最优的选择,LRU-3或者更大的K值命中率会高,但适应性差,需要大量的数据访问才能将历史访问记录清除掉。

3.3. 分析

【命中率】

LRU-K降低了“缓存污染”带来的问题,命中率比LRU要高。

【复杂度】

LRU-K队列是一个优先级队列,算法复杂度和代价比较高。

【代价】

由于LRU-K还需要记录那些被访问过、但还没有放入缓存的对象,因此内存消耗会比LRU要多;当数据量很大的时候,内存消耗会比较可观。

LRU-K需要基于时间进行排序(可以需要淘汰时再排序,也可以即时排序),CPU消耗比LRU要高。


1. LFU类

1.1. LFU
1.1.1. 原理

LFU(Least Frequently Used)算法根据数据的历史访问频率来淘汰数据,其核心思想是“如果数据过去被访问多次,那么将来被访问的频率也更高”。

1.1.2. 实现

LFU的每个数据块都有一个引用计数,所有数据块按照引用计数排序,具有相同引用计数的数据块则按照时间排序。

具体实现如下:

 

1. 新加入数据插入到队列尾部(因为引用计数为1);

2. 队列中的数据被访问后,引用计数增加,队列重新排序;

3. 当需要淘汰数据时,将已经排序的列表最后的数据块删除。

1.1.3. 分析

l 命中率

一般情况下,LFU效率要优于LRU,且能够避免周期性或者偶发性的操作导致缓存命中率下降的问题。但LFU需要记录数据的历史访问记录,一旦数据访问模式改变,LFU需要更长时间来适用新的访问模式,即:LFU存在历史数据影响将来数据的“缓存污染”效用。

l 复杂度

需要维护一个队列记录所有数据的访问记录,每个数据都需要维护引用计数。

l 代价

需要记录所有数据的访问记录,内存消耗较高;需要基于引用计数排序,性能消耗较高。

 

算法数据结构和实习




1.2. LFU*
1.2.1. 原理

基于LFU的改进算法,其核心思想是“只淘汰访问过一次的数据”。

1.2.2. 实现

LFU*数据缓存实现和LFU一样,不同的地方在于淘汰数据时,LFU*只淘汰引用计数为1的数据,且如果所有引用计数为1的数据大小之和都没有新加入的数据那么大,则不淘汰数据,新的数据也不缓存。

1.2.3. 分析

l 命中率

和LFU类似,但由于其不淘汰引用计数大于1的数据,则一旦访问模式改变,LFU*无法缓存新的数据,因此这个算法的应用场景比较有限。

l 复杂度

需要维护一个队列,记录引用计数为1的数据。

l 代价

相比LFU要低很多,不需要维护所有数据的历史访问记录,只需要维护引用次数为1的数据,也不需要排序。

1.3. LFU-Aging
1.3.1. 原理

基于LFU的改进算法,其核心思想是“除了访问次数外,还要考虑访问时间”。这样做的主要原因是解决LFU缓存污染的问题。

1.3.2. 实现

虽然LFU-Aging考虑时间因素,但其算法并不直接记录数据的访问时间,而是通过平均引用计数来标识时间。

LFU-Aging在LFU的基础上,增加了一个最大平均引用计数。当当前缓存中的数据“引用计数平均值”达到或者超过“最大平均引用计数”时,则将所有数据的引用计数都减少。减少的方法有多种,可以直接减为原来的一半,也可以减去固定的值等。

1.3.3. 分析

l 命中率

LFU-Aging的效率和LFU类似,当访问模式改变时,LFU-Aging能够更快的适用新的数据访问模式,效率要高。

l 复杂度

在LFU的基础上增加平均引用次数判断和处理。

l 代价

和LFU类似,当平均引用次数超过指定阈值(Aging)后,需要遍历访问列表。

 

1.4. LFU*-Aging
1.4.1. 原理

LFU*和LFU-Aging的合成体。

1.4.2. 实现

略。

1.4.3. 分析

l 命中率

和LFU-Aging类似。

l 复杂度

比LFU-Aging简单一些,不需要基于引用计数排序。

l 代价

比LFU-Aging少一些,不需要基于引用计数排序。


1.5. Window-LFU
1.5.1. 原理

Windows-LFU是LFU的一个改进版,差别在于Window-LFU并不记录所有数据的访问历史,而只是记录过去一段时间内的访问历史,这就是Window的由来,基于这个原因,传统的LFU又被称为“Perfect-LFU”。

1.5.2. 实现

与LFU的实现基本相同,差别在于不需要记录所有数据的历史访问数据,而只记录过去一段时间内的访问历史。具体实现如下:

 

1)记录了过去W个访问记录;

2)需要淘汰时,将W个访问记录按照LFU规则排序淘汰

 

举例如下:

假设历史访问记录长度设为9,缓存大小为3,图中不同颜色代表针对不同数据块的访问,同一颜色代表针对同一数据的多次访问。

样例1:黄色访问3次,蓝色和橘色都是两次,橘色更新,因此缓存黄色、橘色、蓝色三个数据块

样例2:绿色访问3次,蓝色两次,暗红两次,蓝色更新,因此缓存绿色、蓝色、暗红三个数据块

 

1.5.3. 分析

l 命中率

Window-LFU的命中率和LFU类似,但Window-LFU会根据数据的访问模式而变化,能够更快的适应新的数据访问模式,”缓存污染“问题不严重。

l 复杂度

需要维护一个队列,记录数据的访问流历史;需要排序。

l 代价

Window-LFU只记录一部分的访问历史记录,不需要记录所有的数据访问历史,因此内存消耗和排序消耗都比LFU要低。

1.6. LFU类算法对比

由于不同的访问模型导致命中率变化较大,此处对比仅基于理论定性分析,不做定量分析。

 

对比点

对比

命中率

Window-LFU/LFU-Aging > LFU*-Aging > LFU > LFU*

复杂度

LFU-Aging > LFU>  LFU*-Aging  >Window-LFU > LFU*

代价

LFU-Aging > LFU > Window-LFU > LFU*-Aging  > LFU*

这篇关于LRU 与 LFU 缓存数据算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/245974

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

最大公因数:欧几里得算法

简述         求两个数字 m和n 的最大公因数,假设r是m%n的余数,只要n不等于0,就一直执行 m=n,n=r 举例 以18和12为例 m n r18 % 12 = 612 % 6 = 06 0所以最大公因数为:6 代码实现 #include<iostream>using namespace std;/