干货|漫画算法:LRU从实现到应用层层剖析(第一讲)
今天为大家分享很出名的LRU算法,第一讲共包括4节。
- LRU概述
- LRU使用
- LRU实现
- Redis近LRU概述
第一部分:LRU概述
LRU是Least Recently Used的缩写,译为最近最少使用。它的理论基础为“最近使用的数据会在未来一段时期内仍然被使用,已经很久没有使用的数据大概率在未来很长一段时间仍然不会被使用”由于该思想非常契合业务场景 ,并且可以解决很多实际开发中的问题,所以我们经常通过LRU的思想来作缓存,一般也将其称为LRU缓存机制。因为恰好leetcode上有这道题,所以我干脆把题目贴这里。但是对于LRU而言,希望大家不要局限于本题(大家不用担心学不会,我希望能做一个全网最简单的版本,希望可以坚持看下去!)下面,我们一起学习一下。
题目:运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作:获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。
进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作?
示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
第二部分:LRU使用
首先说一下LRUCache的示例解释一下。
-
第一步:我们申明一个LRUCache,长度为2
-
第二步:我们分别向cache里边put(1,1)和put(2,2),这里因为最近使用的是2(put也算作使用)所以2在前,1在后。
- 第三步:我们get(1),也就是我们使用了1,所以需要将1移到前面。
- 第四步:此时我们put(3,3),因为2是最近最少使用的,所以我们需要将2进行作废。此时我们再get(2),就会返回-1。
- 第五步:我们继续put(4,4),同理我们将1作废。此时如果get(1),也是返回-1。
- 第六步:此时我们get(3),实际为调整3的位置。
- 第七步:同理,get(4),继续调整4的位置。
第三部分:LRU 实现(层层剖析)
通过上面的分析大家应该都能理解LRU的使用了。现在我们聊一下实现。LRU一般来讲,我们是使用双向链表实现。这里我要强调的是,其实在项目中,并不绝对是这样。比如Redis源码里,LRU的淘汰策略,就没有使用双向链表,而是使用一种模拟链表的方式。因为Redis大多是当内存在用(我知道可以持久化),如果再在内存中去维护一个链表,就平添了一些复杂性,同时也会多耗掉一些内存,后面我会单独拉出来Redis的源码给大家分析,这里不细说。
回到题目,为什么我们要选择双向链表来实现呢?看看上面的使用步骤图,大家会发现,在整个LRUCache的使用中,我们需要频繁的去调整首尾元素的位置。而双向链表的结构,刚好满足这一点(再啰嗦一下,前几天我刚好看了groupcache的源码,里边就是用双向链表来做的LRU,当然它里边做了一些改进。groupcache是memcache作者实现的go版本,如果有go的读者,可以去看看源码,还是有一些收获。)
下面,我们采用hashmap+双向链表的方式进行实现。
首先,我们定义一个LinkNode,用以存储元素。因为是双向链表,自然我们要定义pre和next。同时,我们需要存储下元素的key和value。val大家应该都能理解,关键是为什么需要存储key?举个例子,比如当整个cache的元素满了,此时我们需要删除map中的数据,需要通过LinkNode中的key来进行查询,否则无法获取到key。
type LRUCache struct { m map[int]*LinkNode cap int head, tail *LinkNode }
现在有了LinkNode,自然需要一个Cache来存储所有的Node。我们定义cap为cache的长度,m用来存储元素。head和tail作为Cache的首尾。
type LRUCache struct { m map[int]*LinkNode cap int head, tail *LinkNode }
接下来我们对整个Cache进行初始化。在初始化head和tail的时候将它们连接在一起。
func Constructor(capacity int) LRUCache { head := &LinkNode{0, 0, nil, nil} tail := &LinkNode{0, 0, nil, nil} head.next = tail tail.pre = head return LRUCache{make(map[int]*LinkNode), capacity, head, tail} }
大概是这样:
现在我们已经完成了Cache的构造,剩下的就是添加它的API了。因为Get比较简单,我们先完成Get方法。这里分两种情况考虑,如果没有找到元素,我们返回-1。如果元素存在,我们需要把这个元素移动到首位置上去。
func (this *LRUCache) Get(key int) int { head := this.head cache := this.m if v, exist := cache[key]; exist { v.pre.next = v.next v.next.pre = v.pre v.next = head.next head.next.pre = v v.pre = head head.next = v return v.val } else { return -1 } }
大概就是下面这个样子(假若2是我们get的元素)
我们很容易想到这个方法后面还会用到,所以将其抽出。
func (this *LRUCache) moveToHead(node *LinkNode){ head := this.head //从当前位置删除 node.pre.next = node.next node.next.pre = node.pre //移动到首位置 node.next = head.next head.next.pre = node node.pre = head head.next = node } func (this *LRUCache) Get(key int) int { cache := this.m if v, exist := cache[key]; exist { this.moveToHead(v) return v.val } else { return -1 } }
现在我们开始完成Put。实现Put时,有两种情况需要考虑。假若元素存在,其实相当于做一个Get操作,也是移动到最前面(但是需要注意的是,这里多了一个更新值的步骤)。
func (this *LRUCache) Put(key int, value int) { head := this.head tail := this.tail cache := this.m //假若元素存在 if v, exist := cache[key]; exist { //1.更新值 v.val = value //2.移动到最前 this.moveToHead(v) } else { //TODO } }
假若元素不存在,我们将其插入到元素首,并把该元素值放入到map中。
func (this *LRUCache) Put(key int, value int) { head := this.head tail := this.tail cache := this.m //存在 if v, exist := cache[key]; exist { //1.更新值 v.val = value //2.移动到最前 this.moveToHead(v) } else { v := &LinkNode{key, value, nil, nil} v.next = head.next v.pre = head head.next.pre = v head.next = v cache[key] = v } }
但是我们漏掉了一种情况,如果恰好此时Cache中元素满了,需要删掉最后的元素。处理完毕,附上Put函数完整代码。
func (this *LRUCache) Put(key int, value int) { head := this.head tail := this.tail cache := this.m //存在 if v, exist := cache[key]; exist { //1.更新值 v.val = value //2.移动到最前 this.moveToHead(v) } else { v := &LinkNode{key, value, nil, nil} if len(cache) == this.cap { //删除最后元素 delete(cache, tail.pre.key) tail.pre.pre.next = tail tail.pre = tail.pre.pre } v.next = head.next v.pre = head head.next.pre = v head.next = v cache[key] = v } }
最后,我们完成所有代码:
type LinkNode struct { key, val int pre, next *LinkNode } type LRUCache struct { m map[int]*LinkNode cap int head, tail *LinkNode } func Constructor(capacity int) LRUCache { head := &LinkNode{0, 0, nil, nil} tail := &LinkNode{0, 0, nil, nil} head.next = tail tail.pre = head return LRUCache{make(map[int]*LinkNode), capacity, head, tail} } func (this *LRUCache) Get(key int) int { cache := this.m if v, exist := cache[key]; exist { this.moveToHead(v) return v.val } else { return -1 } } func (this *LRUCache) moveToHead(node *LinkNode) { head := this.head //从当前位置删除 node.pre.next = node.next node.next.pre = node.pre //移动到首位置 node.next = head.next head.next.pre = node node.pre = head head.next = node } func (this *LRUCache) Put(key int, value int) { head := this.head tail := this.tail cache := this.m //存在 if v, exist := cache[key]; exist { //1.更新值 v.val = value //2.移动到最前 this.moveToHead(v) } else { v := &LinkNode{key, value, nil, nil} if len(cache) == this.cap { //删除末尾元素 delete(cache, tail.pre.key) tail.pre.pre.next = tail tail.pre = tail.pre.pre } v.next = head.next v.pre = head head.next.pre = v head.next = v cache[key] = v } }
优化后:
type LinkNode struct { key, val int pre, next *LinkNode } type LRUCache struct { m map[int]*LinkNode cap int head, tail *LinkNode } func Constructor(capacity int) LRUCache { head := &LinkNode{0, 0, nil, nil} tail := &LinkNode{0, 0, nil, nil} head.next = tail tail.pre = head return LRUCache{make(map[int]*LinkNode), capacity, head, tail} } func (this *LRUCache) Get(key int) int { cache := this.m if v, exist := cache[key]; exist { this.MoveToHead(v) return v.val } else { return -1 } } func (this *LRUCache) RemoveNode(node *LinkNode) { node.pre.next = node.next node.next.pre = node.pre } func (this *LRUCache) AddNode(node *LinkNode) { head := this.head node.next = head.next head.next.pre = node node.pre = head head.next = node } func (this *LRUCache) MoveToHead(node *LinkNode) { this.RemoveNode(node) this.AddNode(node) } func (this *LRUCache) Put(key int, value int) { tail := this.tail cache := this.m if v, exist := cache[key]; exist { v.val = value this.MoveToHead(v) } else { v := &LinkNode{key, value, nil, nil} if len(cache) == this.cap { delete(cache, tail.pre.key) this.RemoveNode(tail.pre) } this.AddNode(v) cache[key] = v } }
因为该算法过于重要,给一个Java版本的:
//java版本 public class LRUCache { class LinkedNode { int key; int value; LinkedNode prev; LinkedNode next; } private void addNode(LinkedNode node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } private void removeNode(LinkedNode node){ LinkedNode prev = node.prev; LinkedNode next = node.next; prev.next = next; next.prev = prev; } private void moveToHead(LinkedNode node){ removeNode(node); addNode(node); } private LinkedNode popTail() { LinkedNode res = tail.prev; removeNode(res); return res; } private Hashtable<Integer, LinkedNode> cache = new Hashtable<Integer, LinkedNode>(); private int size; private int capacity; private LinkedNode head, tail; public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; head = new LinkedNode(); tail = new LinkedNode(); head.next = tail; tail.prev = head; } public int get(int key) { LinkedNode node = cache.get(key); if (node == null) return -1; moveToHead(node); return node.value; } public void put(int key, int value) { LinkedNode node = cache.get(key); if(node == null) { LinkedNode newNode = new LinkedNode(); newNode.key = key; newNode.value = value; cache.put(key, newNode); addNode(newNode); ++size; if(size > capacity) { LinkedNode tail = popTail(); cache.remove(tail.key); --size; } } else { node.value = value; moveToHead(node); } } }
第四部分:Redis 近LRU 介绍
上文完成了咱们自己的LRU实现,现在现在聊一聊Redis中的近似LRU。由于真实LRU需要过多的内存(在数据量比较大时),所以Redis是使用一种随机抽样的方式,来实现一个近似LRU的效果。说白了,LRU根本只是一个预测键访问顺序的模型。
在Redis中有一个参数,叫做 “maxmemory-samples”,是干嘛用的呢?
# LRU and minimal TTL algorithms are not precise algorithms but approximated # algorithms (in order to save memory), so you can tune it for speed or # accuracy. For default Redis will check five keys and pick the one that was # used less recently, you can change the sample size using the following # configuration directive. # # The default of 5 produces good enough results. 10 Approximates very closely # true LRU but costs a bit more CPU. 3 is very fast but not very accurate. # maxmemory-samples 5
上面我们说过了,近似LRU是用随机抽样的方式来实现一个近似的LRU效果。这个参数其实就是作者提供了一种方式,可以让我们人为干预样本数大小,将其设的越大,就越接近真实LRU的效果,当然也就意味着越耗内存。(初始值为5是作者默认的最佳)
这个图解释一下,绿色的点是新增加的元素,深灰色的点是没有被删除的元素,浅灰色的是被删除的元素。最下面的这张图,是真实LRU的效果,第二张图是默认该参数为5的效果,可以看到浅灰色部分和真实的契合还是不错的。第一张图是将该参数设置为10的效果,已经基本接近真实LRU的效果了。
由于时间关系本文基本就说到这里。那Redis中的近似LRU是如何实现的呢?请关注下一期的内容~
文章来源:本文由小浩算法授权转载
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
数据源管理 | 主从库动态路由,AOP模式读写分离
本文源码:GitHub·点这里 || GitEE·点这里 一、多数据源应用 1、基础描述 在相对复杂的应用服务中,配置多个数据源是常见现象,例如常见的:配置主从数据库用来写数据,再配置一个从库读数据,这种读写分离模式可以缓解数据库压力,提高系统的并发能力和稳定性,执行效率。 2、核心API 在处理这种常见问题,要学会查询服务基础框架的API,说直白点就是查询Spring框架的API(工作几年,还没用过Spring之外的框架搭建环境),这种常用的业务模式,基本上Spring都提供了API支持。 核心API:AbstractRoutingDataSource 底层维护Map容器,用来保存数据源集合,提供一个抽象方法,实现自定义的路由策略。 @Nullable private Map<Object, DataSource> resolvedDataSources; @Nullable protected abstract Object determineCurrentLookupKey(); 补刀一句:为何框架的原理很难通过一篇文章看明白?因为使用的不多,基本意识没有形成,熟悉框...
- 下一篇
那些年被面试官怼的MySQL索引
之前有过一次面试,关于MySQL索引的原理及使用被面试官怼的体无完肤,立志要总结一番,然后一直没有时间(其实是懒……),准备好了吗? 索引是什么? 数据库索引,是数据库管理系统(DBMS)中一个排序的数据结构,它可以对数据库表中一列或多列的值进行排序,以协助更加快速的访问数据库表中特定的数据。通俗的说,我们可以把数据库索引比做是一本书前面的目录,它能加快数据库的查询速度。 为什么需要索引? 思考:如何在一个图书馆中找到一本书? 设想一下,假如在图书馆中没有其他辅助手段,只能一条道走到黑,一本书一本书的找,经过3个小时的连续查找,终于找到了你需要看的那本书,但此时天都黑了。为了避免这样的事情,每个图书馆才都配备了一套图书馆管理系统,大家要找书籍的话,先在系统上查找到书籍所在的房屋编号、图书架编号还有书在图书架几层的那个方位,然后就可以直接大摇大摆的去取书了,就可以很快速的找到我们所需要的书籍。索引就是这个原理,它可以帮助我们快速的检索数据。 一般的应用系统对数据库的操作,遇到最多、最容易出问题是一些复杂的查询操作,当数据库中数据量很大时,查找数据就会变得很慢,这样就很影响整个应用系统的效...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- MySQL8.0.19开启GTID主从同步CentOS8
- SpringBoot2全家桶,快速入门学习开发网站教程
- CentOS8编译安装MySQL8.0.19
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- CentOS7,CentOS8安装Elasticsearch6.8.6
- Red5直播服务器,属于Java语言的直播服务器
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- CentOS6,CentOS7官方镜像安装Oracle11G
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装