LRU/LFU - Githubissues

面试中 LRU / LFU 的青铜与王者这篇文章非常对应试技巧非常有帮助。

LRU

LRU的数据结构大部分人都知道，即字典+链表。但有一些细节需要特别注意

链表必须是双向链表，这样在移动时才能做的O(1)。有的语言标准库里没有双向链表，实现的时候需要小心
链表的值是KV对，这样才能在溢出时，通过队尾快速找到字典的Key，并删除Key
字典的值是链表节点，这样才能在访问时，快速将节点移动队头

这里操作最复杂的还是双向链表，最好选标准库自带双向链表的语言，可以省不少力。

LFU

LFU遇到的比较少，不能继续使用LRU的数据结构了。上面是用一个双向链表，现在是用字典包存多个双向链表。字典的Key是频率，Value是相同频率的列表。另外再保存最少使用频率的Key。

只保存一个最少频率Key，而不用对频率排序，是这道题的精髓。LFU淘汰策略是上一个使用最少的Key，只有在新加Key的时候才可能会触发淘汰，而最可能被淘汰的就是新加的Key，所以用一个变量保存就可以了

LRU算法实现

双向链表实现LRU算法的主要数据结构。链表操作不多，主要有2个：1. 删除某个节点；2. 将节点插入到表头。

标准库链表

import "container/list"

type LRUCache struct {
    Keys map[int]*list.Element
    List *list.List
    Cap  int
}

type pair struct {
    K, V int
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        Keys: make(map[int]*list.Element),
        List: list.New(),
        Cap:  capacity,
    }
}

func (this *LRUCache) Get(key int) int {
    if e, ok := this.Keys[key]; ok {
        this.List.MoveToFront(e)
        return e.Value.(pair).V
    }
    return -1
}

func (this *LRUCache) Put(key int, value int) {
    if e, ok := this.Keys[key]; ok {
        this.List.MoveToFront(e)
    } else {
        e := this.List.PushFront(pair{key, value})
        this.Keys[key] = e
    }
    if this.List.Len() > this.Cap {
        e := this.List.Back()
        this.List.Remove(e)
        delete(this.Keys, e.Value.(pair).K)
    }
}

自定义链表

链表有删除操作，所以定义虚拟头、尾节点很有必要。使用虚拟节点后，在删除时不用担心头或尾会出现空节点的情况

有的实现只定义head，使用head.prev指向结尾。可以节省一个节点的内存，但是不便于理解

type LinkList struct {
    prev, next *LinkList
    value int
    key int
}

type LRUCache struct {
    cap int
    dict map[int]*LinkList
    head, tail *LinkList
}

func Constructor(capacity int) LRUCache {
    lru := LRUCache{
        cap: capacity,
        dict: make(map[int]*LinkList),
        head: new(LinkList),
        tail: new(LinkList),
    }
   // 初始化空链表，头尾互相指向
    lru.head.next = lru.tail
    lru.tail.prev = lru.head
    return lru
}

func (lru *LRUCache) Get(key int) int {
    if node, ok := lru.dict[key]; ok {
        lru.removeNode(node)
        lru.moveToHead(node)
        return node.value
    } else {
        return -1
    }
}

func (lru *LRUCache) Put(key int, value int)  {
    if node, ok := lru.dict[key]; ok {
        lru.removeNode(node)
        lru.moveToHead(node)
        node.value = value
    } else {
        node := &LinkList{key: key, value: value}
        lru.moveToHead(node)
        lru.dict[key] = node
    }
    if len(lru.dict) > lru.cap {
        last := lru.tail.prev
        delete(lru.dict, last.key)
        lru.removeNode(last)
    }
}

func (lru *LRUCache) removeNode(node *LinkList) {
    p, n := node.prev, node.next
    p.next = n
    n.prev = p
}

func (lru *LRUCache) moveToHead(node *LinkList) {
    next := lru.head.next
    lru.head.next = node
    node.prev = lru.head
    node.next = next
    next.prev = node
}

annidy / notes

LRU/LFU #332

LRU

LFU

LRU算法实现

标准库链表

自定义链表