Go LRU缓存算法

发表评论

其实我本来不打算写这篇文章的，直到提交完代码后发现…在所有 Go 提交中击败了99.42%的用户…这就有点意思了，所以还是写一篇吧刚好总结一下。

前言

古人云，搬砖5分钟，修bug两小时。还真是。

本以为LRU能半个小时征服，结果不停出bug。不知道是下午太困了还是怎么回事，双向链表做交换时愣是把头节点和头节点后边的节点做了个交叉..晚饭后出去散步回来，怎么看感觉怎么不对劲，稍微一改就可以了…补这个窟窿下午花了两个多钟还愣是没看到..

这也得出了一个总结：能把重复操作单独封装成一个函数的，就单独封装起来，这样一出问题故障会明显很多（因为你只要调用这里就都有问题），而不至于像我最开始的写法，节点交换都是独立的，以至于出问题就很不容易看出来。

什么是LRU

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

LRU – 百度百科

思路

哈希表 + 双向链表

为什么要用哈希表

如果你用数组的话，当你需要从中查找某个元素的话，那么这个查找性能可能会是个问题。那哈希表有什么优势呢，哈希表通过一个key和自定义的散列函数（这个看哈希表起初如何设计，个人觉得这个哈希表的设计和维护也要看场景来选择）来直接计算内存访问地址，就相当于人家还在遍历查找它想要的东西在哪里，哈希表已经直接通过key把地址给算出来了（暂且先不考虑冲突），那么这个速度差距可想而知。

晚点再单独写一遍纯手工哈希表的，到时候再详细说哈希表，本篇先不提及太多。

为什么要用双向链表

正如上边所说，哈希表的查找速度非常快，无冲突的情况下压根就不用查找直接就能得到key对应的value。那么问题来了，只有哈希表的情况下，我们如何实现缓存的前移？这个时候或许会有数组这个选项出现，但是有一个问题，缓存可能存在于数组的中间，位置几乎是不定的，那么即便我们能很快得到它的位置，但是如果要移动到头部，几乎要动整个数组，这个开销觉得并不划算，不如链表来的实在。

由于牵扯到缓存过期问题，因此会有一个操作是清除尾部（即多余的）的缓存（如果你不清就成内存泄漏了），这个时候需要来回在头部和尾部进行操作，这个场景下，双向链表最为合适。

代码

package main

import "fmt"

/*
LRU大结构体
 */
type LRUCache struct {
    cacheMap map[int]*Instance
    Header *Instance // 变量名称为Header，实际是来回变的
    Length int // 哈希表的大小
    Size int // 已存入的缓存的数量
}

/*
每个KV的实体（双向链表）
 */
type Instance struct {
    Last *Instance
    key int
    value int
    Next *Instance
}

/*
LRU初始化函数
 */
func Constructor(capacity int) LRUCache {
    c := LRUCache{}
    c.cacheMap = make(map[int]*Instance, capacity)
    c.Length = capacity
    return c
}

/*
Get元素方法
此操作会将元素（若有）移到链表顶端
 */
func (this *LRUCache) Get(key int) int {
    // 先从哈希表中找到位置
    cache, ok := this.cacheMap[key]
    if ok == false {
        return -1
    }

    // 在链表头部，不需要操作
    if cache.Last == nil {
        return cache.value
    }

    // 在链表尾部，需要放到开始
    if cache.Next == nil {
        // 清理倒数第二个Next
        cache.Last.Next = nil

        // 放到前边
        this.transToHeader(cache)

        return cache.value
    }

    // 不在两边的
    // 链接前后两个节点
    cache.Last.Next = cache.Next
    cache.Next.Last = cache.Last

    // 移到前边
    this.transToHeader(cache)

    return cache.value
}

/*
Put函数
当覆盖写入时会隐式执行一次Get（前移使用）
当插入时会放在链表前端
 */
func (this *LRUCache) Put(key int, value int)  {
    cache, ok := this.cacheMap[key]
    if ok {
        cache.value = value
        _ = this.Get(key)
        return
    }

    // 当链表还是空的时候
    if this.Header == nil {
        this.Header = &Instance{
            Last:  nil,
            key:   key,
            value: value,
            Next:  nil,
        }
        this.cacheMap[key] = this.Header
        this.Size++
        return
    }

    // 当链表已经满了的时候
    if this.Size == this.Length {
        // 如果只有一个元素
        if this.Length == 1 {
            delete(this.cacheMap, this.Header.key)
            this.Header = &Instance{
                key:   key,
                value: value,
            }
            this.cacheMap[key] = this.Header
            return
        }

        // 移除末尾的
        // 把指针移到尾部
        this.goFooter()

        needDelete := this.Header
        this.Header = this.Header.Last
        this.Header.Next = nil
        delete(this.cacheMap, needDelete.key)

        // 新增到前边的
        ins := &Instance{
            key:  key,
            value: value,
        }
        this.transToHeader(ins)
        this.cacheMap[key] = ins

        return
    } else
    // 当链表还没满但是已经有头的时候，增加到前边
    {
        ins := &Instance{
            key:   key,
            value: value,
        }
        this.transToHeader(ins)
        this.cacheMap[key] = ins
        this.Size++
        return
    }
}

func (this *LRUCache) goHeader()  {
    for {
        if this.Header.Last == nil {
            break
        }
        this.Header = this.Header.Last
    }
}

func (this *LRUCache) goFooter()  {
    for {
        if this.Header.Next == nil {
            break
        }
        this.Header = this.Header.Next
    }
}

func (this *LRUCache) transToHeader(needTrans *Instance) {
    this.goHeader()
    oldHeader := this.Header
    this.Header = needTrans
    this.Header.Last = nil
    this.Header.Next = oldHeader
    oldHeader.Last = this.Header
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

func main() {
    var g int
    lru := Constructor(2)
    g = lru.Get(2)
    lru.Put(2, 6)
    g = lru.Get(1)
    lru.Put(1, 5)
    lru.Put(1, 2)
    g = lru.Get(1)
    g = lru.Get(2)
    fmt.Println(g)
}

特别需要留意的是，删除缓存和新增缓存时一定要更新哈希表…不然会比较尴尬

结果

可以看到，执行用时慢到爆表了..我大概感觉有的地方还是能优化的，只不过现在太晚了而且后边还有其他东西要学，暂且先挖个坑在这里把，等晚点有空再回来填

不过内存消耗还是挺满意的，也只能说，这个代码的空间复杂度挺不错的（至少我这么觉得），时间复杂度还是太高，晚点有空再来填坑吧

发表回复