• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

地铁5分钟理解LRU算法

大数据 wangting 1年前 (2018-08-01) 404次浏览

LRU(Least recently used,最近最少使用)算法作为内存管理的一种有效算法,其含义是在内存有限的情况下,当内存容量不足时,为了保证程序的运行,这时就不得不淘汰内存中的一些对象,释放这些对象占用的空间,那么选择淘汰哪些对象呢?

LRU算法就提供了一种策略,告诉我们选择最近一段时间内,最久未使用的对象将其淘汰,至于为什么要选择最久未使用的,因为其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

地铁5分钟理解LRU算法

1、最开始时,内存空间是空的,因此依次进入A、B、C是没有问题的。

2、当加入D时,就出现了问题,内存空间不够了,因此根据LRU算法,内存空间中A待的时间最为久远,选择A,将其淘汰。

3、当再次引用B时,内存空间中的B又处于活跃状态,而C则变成了内存空间中,近段时间最久未使用的。

4、当再次向内存空间加入E时,这时内存空间又不足了,选择在内存空间中待的最久的C将其淘汰出内存,这时的内存空间存放的对象就是E->B->D。

LRU算法的整体思路就是这样的,其实非常简单,就是当年我们学习的数据结构中,队列的基本模型。代码就不贴了,每次面试都会问到。


喜欢 (0)