LRU
Posted on
最近最少使用( Least Recently Used
)也就是 LRU
算法是内存页面置换算法的一种,使用该算法可以在有限的资源内提高内存访问的速度,它利用了著名的局部性原理,更具体的说是时间局部性,也就是说如果一个信息项正在被访问,那么在近期它很可能还会被再次访问。
例如我们有3个物理块,访问序列为 7,0,1,2,0,3,0
- 访问7时,LRU缺失,此时LRU未满,放入7,此时淘汰顺序为7
- 访问0时,LRU缺失,此时LRU未满,放入0,此时淘汰顺序为7,0
- 访问1时,LRU缺失,此时LRU未满,放入1,此时淘汰顺序为7,0 ,1
- 访问2时,LRU缺失,此时LRU已满,驱逐7,放入2,此时淘汰顺序为0,1,2
- 访问0时,LRU命中,更新淘汰顺序,此时淘汰循序为1,2,0
- 访问3时,LRU缺失,此时LRU已满,驱逐1,放入3,此时淘汰顺序为2,0,3
- 访问0时,LRU命中,更新淘汰顺序,此时淘汰顺序为0,3,2
![LRU](https://i.ytimg.com/vi/4wVp97-uqr0/maxresdefault.jpg)
我们利用链表( *list.List
)维护其淘汰顺序,利用 map
作为其存储引擎(作为物质基础)。
1 2
| <---------------------------------------------------------> newest oldest
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| type Key interface
type entry struct { key Key value interface{} }
type Cache struct { MaxEntries int OnEvicted func(key Key, value interface{}) ll *list.List cache map[interface{}]*list.Element }
func New(maxEntries int) *Cache { return &Cache{ MaxEntries: maxEntries, ll: list.New(), cache: make(map[interface{}]*list.Element), } }
|
因为我们经常需要判断当前的 LRU
缓存是否存满,所以我们构造一个helper function
来获取当前缓存的容量。
1 2 3 4 5 6
| func (c *Cache) Len() int { if c.cache == nil { return 0 } return c.ll.Len() }
|
淘汰顺序在两种情况下会更新,一是新增元素时,如果元素在 LRU
缓存中不存在,则将它放在链表的头部( PushFront
),如果存在,则直接将其移到链表的头部( MoveToFront
)。二是在获取元素时,如果元素存在,则直接将其移到链表的头部( MoveToFront
)。这样一来我们就能确保最新的东西在链表头,最老的东西在链表尾。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| func (c *Cache) Add(key Key, value interfacfe{}) { if c.cache == nil { c.cache = make(map[interface{}*list.Element]) c.ll = list.New() } if ee, ok := c.cache[key]; ok { c.ll.MoveToFront(ee) ee.Value.(*entry).value = value return } ele := c.ll.PushFront(&entry{key, value}) c.cache[key] = ele if c.MaxEntries != 0 && c.ll.Len() > c.MaxEntries { c.RemoveOldest() } }
func (c *Cache) Get(key Key) (value interface{}, ok bool) { if c.cache == nil { return } if ele, hit := c.cache[key]; hit { c.ll.MoveToFront(ele) return ele.Value.(*entry).value, true } return }
|
RemoveOldest
将最老的元素淘汰,也就是说将链表中最后一项移除,并将map
中对应的元素删除。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| func (c *Cache) RemoveOldest() { if c.cache == nil { return } ele := c.ll.Back() if ele != nil { c.removeElement(ele) } }
func (c *Cache) removeElement(e *list.Element) { c.ll.Remove(e) kv := e.Value.(*entry) delete(c.cache, kv.key) if c.OnEvicted != nil { c.OnEvicted(kv.key, kv.value) } }
|
清除 LRU
缓存只需要将链表和 map
设为 nil
就可以了。
1 2 3 4 5 6 7 8 9 10
| func (c *Cache) Clear() { if c.OnEvicted != nil { for _, e := range c.cache { kv := e.Value.(*entry) c.OnEvicted(kv.key, kv.value) } } c.ll = nil c.cache = nil }
|