00:00
好,各位同学,我们继续,那么通过我们前面的打怪练习,终于已经接近到了我们本次分享的最后一个题目,那就是red l ru算法的介绍。那么这个呢,由于大家呢,都已经有过工作经验,我默认了啊。这个Li ru算法的话呢,应该是基本上有所了解,那么它来自于哪呢?我们刚才呢,前面的上一章的题目也跟大家说过,这是不是有种叫LRU,也就是red的缓存过期淘汰策略。那么接下来实际的比面试过程当中的话呢,他肯定不会问你啊什么是IRU了,当然你要知道对吧,关键是。考过这个题目,你能不能手写的L算法来体现出这样的一种思想?好,那么下面我们来搂一眼。首先,什么是IRU?来。是这个的recently used的缩写,最近最少使用,是一种常用的页面置换算法啊,待会会说这个什么叫页面啊,选择最近最久未使用的数据予以淘汰,因为缓存毕竟是有限的,你别占着卫生间不便便,对吧?
01:14
你如果要用,你留下来,你如果不用了,请你腾开这个坑位,让更需要的数据去使用,保证我们的程序的健壮和高效。那么接下来啊,我们以一个我们的手机case来说话。首先我们这是一种。I。现在呢,它是一种思想,对吧,最近最常使用这个就不打了,那么现在也用它,他干的是一个什么。缓存,那么我们这个缓存我们大家都清楚。它主要是什么,是不是有读加写两个。操作最关心的是不是命中OK。可问题是。缓存是有。
02:00
空间限制的,也就是说它的大小。会有一定峰值和上限的,对吧,那比如说以我们的手机为例啊,同学们。比如说我们在手机上啊,呃,最最经典的啊,假设以我们的苹果,那么大家都清楚。这儿只有一个触发键,那么我点一下这个,它是不是会罗列出后台有很多的页面窗口,告诉我我现在点开过哪些程序?苹果的手机大家都知道,不管苹果还是华为,那么有点类似于这样啊,假设我先点开的第一个应用就是抖音。那么。他在后台就会起这么一个程序。那么这个时候就像是一个功能卡一样,你点苹果手机在这儿就会看到,然后我又点开了一个,比方说这个是新浪的微博,那么再来一个啊,假设这个是微信好抖音,我只点开过一次以后,那么它是不是就像是一个队列排队一样的,它一直就是第一个进入队列的,然后完了以后就一直在这儿,那么现在啊。
03:07
假设我们的这一个内存,那么我们的大小,或者是直白点叫称位,那么只有三个,OK,我又点开了第四个应用的时候,那么同学们不好意思啊,你们三个。要么?报错。要么你们三个必须走一个,腾出一个新的坑位来,让我最新的这个过来,因为这是我最先点开利用,越没有使用的是不是就越压在箱底,或者在对尾也好,或者另外队列的另外一边,那么保证假设我们现在这个业务啊。右边是头,左边是尾,当然啊,你也可以认为左边是头,右边是尾,看你的业务和你的诉求,两边都可以,那么我们经常使用的我们就放在右边,不经常使用的我们放在左边,那最近最少使用,直到有一天坑位满了,不好意思啊,走一个,那么我们就把最不常用的给它剃掉。
04:07
OK,好,那么这个呢,就是它的思想和他的语法要求,那么接下来我们来看看这道题目它考什么,如果考这么简单的,那就好说了,基本上。人人进大厂,这个只是说题的一个意思,我相信大家讲到这儿都应该能够都用过手机,都会有一个感性的认识,那么接下来就是这道题,它考的是什么呢?这道算法来源是哪来?又是我们的利号LRU开始ru缓存。那么直接打出这个网址。我呢也给大家抓图了,又是他立刻你看字节啊,大成他考的这些题目啊,都会来这儿呢,来进行一些处理,然后需要大家简单的做一下应付,那么来。难度是什么鬼?中等好。大致的意思,设计和实现一个IRU最近最常使用的缓存机制啊,应该支持以下操作,Put和get是不是读写那么。
05:06
获取数据get如果关键字的key存在于缓存中,则获取关键字的值。总是正锁,否则好像回复找不到嘛,对吧,写的话巴拉巴拉我就不读了,那么他要求的一个。问题是这样的,那么他也给你说了案例,比方说这个缓存的坑位只有两个啊。那么他要求你按照他的构造方法。构造方法,这个可以定义一个。变量直接住进去,住进去对吧,然后告诉你坑位是多少个,然后一二,比方说现在get就能返回一。然后现在呢,又只有三三,那么这个时候你懂的一和二。那么这个操作将会是关键词二作废,因为因为它现在坑位只有两个,第三个字呢,是不是要干嘛拿掉一个呀哈,比方说现在这个是一和二,就跟我们这样的,这个是。
06:03
一跟二,那么假设现在不好意思,某种算法或者他自己做的案例二,三进来把二挤走了,你现在GET2得不到。未找到返回复一件,那么。四又进来了新的,又把什么之前的那个一那个坑位给替换,因为随着时间的推移,对吧,越来越老的数据被替换新的来保证,那么最后GET1也没找到,那么它呢,就给你做了一个实例,我相信这个呢,也就很简单,好意思听懂了以后它的难点是什么?你是否可以在OE时间复杂度内完成这两种操作,要命的是这句话。也就是一次就要拿下,那么同学们,那么接下来我们介绍完了这个以后,那么。下面我们就来说说它的设计思想。
我来说两句