LFU 起夜级李姐

时间：2018-07-24 06:53:26

相关推荐

LFU 起夜级李姐

Go代码实现

type Node struct {key, val, freq intpre, next*Node}type DoubleLink struct {head, tail *Nodelengthint}type LFUCache struct {freq_map map[int]*DoubleLinkkey_map map[int]*Nodecapint}func Constructor(capacity int) LFUCache {return LFUCache{freq_map: map[int]*DoubleLink{},key_map: map[int]*Node{},cap:capacity,}}// 初始化双向链表func InitDoubleLink() *DoubleLink {list := &DoubleLink{head: &Node{},tail: &Node{},length: 0,}list.head.next = list.taillist.tail.pre = list.headreturn list}// 插入双向链表头部func InsertHead(list *DoubleLink, node *Node) {node.next = list.head.nextlist.head.next = nodenode.next.pre = nodenode.pre = list.headlist.length++}// 删除尾部节点func RemoveTail(list *DoubleLink) (key int) {node := list.tail.prelist.tail.pre = node.prenode.pre.next = list.taillist.length--return node.key}// 删除节点func RemoveNode(list *DoubleLink, node *Node) {node.pre.next = node.nextnode.next.pre = node.prelist.length--}func (this *LFUCache) Get(key int) int {node, ok := this.key_map[key]if !ok {return -1}list := this.freq_map[node.freq]RemoveNode(list, node)// 频率 +1node.freq += 1// 把这个节点装入新频率的链表头部list2, ok := this.freq_map[node.freq]if !ok {list2 = InitDoubleLink()this.freq_map[node.freq] = list2}InsertHead(list2, node)return node.val}func (this *LFUCache) Put(key int, value int) {if this.cap == 0 {return}node, ok := this.key_map[key]// 覆盖旧的valueif ok {// 原来的频率 +1list := this.freq_map[node.freq]RemoveNode(list, node)node.freq++node.val = value// 把这个节点装入新频率的链表头部list2, ok := this.freq_map[node.freq]if !ok {list2 = InitDoubleLink()this.freq_map[node.freq] = list2}InsertHead(list2, node)} else {// 容量判断触发淘汰if this.cap < len(this.key_map)+1 {// 从频率低到高的找，看是否存在双向链表for i := 1; ; i++ {list, ok := this.freq_map[i]if ok && list.length > 0 {kk := RemoveTail(list)delete(this.key_map, kk)break}}}// 装入keymapnode = &Node{key: key,val: value,freq: 1, // 新增的频率都是1}this.key_map[key] = node// 装入 freq_map 频率=1 的链表头部list, ok := this.freq_map[1]if !ok {list = InitDoubleLink()this.freq_map[1] = list}InsertHead(list, node)}}