LRU

LRUCache全名为Least Recently Used，即最近最少使用算法，是操作系统中发生缺页中断时常用的一种页面置换算法。

根据局部性原理，最近使用的数据块很有可能继续被频繁使用，因此当Cache已满的时候，LRUCache算法会把最久未使用的数据块替换出去。

对于LRU算法主要实现两个操作：

• 访问数据块：将访问的数据块更新为最近访问，并返回访问的数据块。
• 添加数据块：如果Cache还有容量，将添加的数据块添加到Cache之后标记为最近访问；如果Cache的容量已满，替换最久未访问的数据块为添加的数据块。

实现#1：使用双端队列和哈希表一起实现，访问和添加数据块的操作时间复杂度都是常数时间

package lru

import (
    "fmt"
)

// 结点
type linkNode struct {
    key   int
    value int
    prev  *linkNode
    next  *linkNode
}

func newLinkNode(k, v int) *linkNode {
    var ln linkNode
    ln.key = k
    ln.value = v
    ln.prev = nil
    ln.next = nil
    return &ln
}

// 双端链表
type doubleLinkList struct {
    capacity int // 容量
    size     int // 当前大小
    head     *linkNode
    tail     *linkNode
}

func newDoubleLinkList(c int) *doubleLinkList {
    var dl doubleLinkList
    dl.capacity = c
    dl.size = 0
    dl.head = nil
    dl.tail = nil
    return &dl
}

func (dl *doubleLinkList) add(ln *linkNode) {
    if dl.size == dl.capacity {
        fmt.Println("the double link has been full.")
        return
    }
    dl.size++
    if dl.head == nil {
        dl.head = ln
        dl.tail = ln
        return
    }
    dl.tail.next = ln
    ln.prev = dl.tail
    ln.next = nil
    dl.tail = ln
}

func (dl *doubleLinkList) del(ln *linkNode) *linkNode {
    if dl.size == 0 {
        fmt.Println("can not delete empty double link.")
    }
    dl.size--
    if ln == dl.head {
        if ln.next != nil {
            ln.next.prev = nil
        }
        dl.head = ln.next
    } else if ln == dl.tail {
        if ln.prev != nil {
            ln.prev.next = nil
        }
        dl.tail = ln.prev
    } else {
        ln.prev.next = ln.next
        ln.next.prev = ln.prev
    }
    return ln
}

// LRU 算法
type LRU struct {
    capacity    int
    cache       *doubleLinkList
    cacheLookUp map[int]*linkNode
}

func NewLRU(c int) *LRU {
    var lru LRU
    lru.capacity = c
    lru.cache = newDoubleLinkList(c)
    lru.cacheLookUp = make(map[int]*linkNode)
    return &lru
}

func (l *LRU) Get(key int) int {
    ln, ok := l.cacheLookUp[key]
    if !ok {
        return -1
    }
    l.cache.del(ln)
    l.cache.add(ln)
    l.traverse()
    return ln.value
}

func (l *LRU) Put(key, val int) {
    ln, ok := l.cacheLookUp[key]
    if ok {
        ln.value = val
        l.cache.del(ln)
        l.cache.add(ln)
    } else {
        if l.capacity == l.cache.size {
            headNode := l.cache.del(l.cache.head)
            delete(l.cacheLookUp, headNode.key)
        }
        newNode := newLinkNode(key, val)
        l.cacheLookUp[key] = newNode
        l.cache.add(newNode)
    }
    l.traverse()
}

func (l *LRU) traverse() {
    node := l.cache.head
    for node != nil {
        fmt.Printf("%d ", node.key)
        node = node.next
    }
    fmt.Println()
}

验证结果

func main() {
    lru := lru.NewLRU(3)
    lru.Put(1, 1)
    lru.Put(2, 2)
    lru.Put(3, 3)
    lru.Get(2)
    lru.Put(4, 4)
}

输出

1
1 2
1 2 3
1 3 2
3 2 4

实现#2：使用Slice和哈希表一起实现，Slice中删除元素的时间复杂度是O(N)

package lru1

import (
    "fmt"
)

type LRU struct {
    size        int
    cache       []int
    cacheLookUp map[int]int
}

func NewLRU(s int) *LRU {
    return &LRU{
        size:        s,
        cache:       []int{},
        cacheLookUp: make(map[int]int),
    }
}

func (l *LRU) Get(key int) int {
    v, ok := l.cacheLookUp[key]
    if !ok {
        return -1
    }
    l.delAppend(v)
    l.traverse()
    return v
}

func (l *LRU) Put(key, value int) {
    v, ok := l.cacheLookUp[key]
    if ok {
        l.cacheLookUp[key] = value
        l.delAppend(v)
    } else {
        if len(l.cache) == l.size {
            delKey := l.cache[0]
            l.cache = l.cache[1:]
            delete(l.cacheLookUp, delKey)
        }
        l.cache = append(l.cache, key)
        l.cacheLookUp[key] = value
    }
    l.traverse()
}

func (l *LRU) delAppend(value int) {
    for i, item := range l.cache {
        if item == value {
            l.cache = append(l.cache[:i], l.cache[i+1:]...)
            l.cache = append(l.cache, value)
            return
        }
    }
}

func (l *LRU) traverse() {
    for _, item := range l.cache {
        fmt.Printf("%d ", item)
    }
    fmt.Println()
}