公众号merlinsea
- 相关内容导航
LRU最近最少使用算法
奔跑的小梁，公众号：梁霖编程工具库golang实现lru缓存
- 题目描述
- LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
- int get(int key) - 如果键 key 存在于缓存中，则获取键的值，否则返回 -1
- void put(int key, int value) - 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键
- 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
- 示例
- 解题思路
- 参考之前求解LRU的算法思路，改动点是当访问了某个key的时候，这个key需要移动到一个“合适”的位置，这里的合适指的是要按照每个key的访问频次来排序，当频次相同的访问时间越近的key优先级越高。
- 代码实现
type Node struct{ Val int Key int // 记录每个节点key出现的次数 Cnt int Pre *Node Next *Node } type LFUCache struct { KeyValueMap map[int]*Node Head *Node Tail *Node Capacity int } func Constructor(capacity int) LFUCache { lfuCache := LFUCache{ KeyValueMap : make(map[int]*Node), Head : new(Node), Tail : new(Node), Capacity: capacity, } lfuCache.Head.Next = lfuCache.Tail lfuCache.Tail.Pre = lfuCache.Head return lfuCache } func (this *LFUCache) Get(key int) int { nodePtr,ok := this.KeyValueMap[key] if !ok { return -1 } nodePtr.Cnt++ // 将nodePtr调整到合适的位置 this.move(nodePtr) return nodePtr.Val } func (this *LFUCache) Put(key int, value int) { nodePtr,ok := this.KeyValueMap[key] if ok { // 说明已经存在了 nodePtr.Val = value nodePtr.Cnt++ this.move(nodePtr) }else{ if len(this.KeyValueMap) == this.Capacity { //定位下待删除的节点 p := this.Tail.Pre // 执行删除 this.Tail.Pre = p.Pre p.Pre.Next = this.Tail delete(this.KeyValueMap,p.Key) } // 构造节点 newNodePtr := &Node{ Key : key, Val : value, Cnt : 1, Pre : this.Tail.Pre, Next : this.Tail, } this.Tail.Pre.Next = newNodePtr this.Tail.Pre = newNodePtr this.KeyValueMap[key] = newNodePtr // 移动 this.move(newNodePtr) } } // 考虑如何快速定位节点需要移动到的位置 func (this *LFUCache) move(nodePtr *Node){ p := nodePtr.Pre nodePtr.Pre.Next = nodePtr.Next nodePtr.Next.Pre = nodePtr.Pre // 移动，这里假定越靠近head节点标识这个节点是最近访问过的，因此这里需要在相等的时候p继续向head移动 for p!=this.Head && nodePtr.Cnt >= p.Cnt { p = p.Pre } // 将nodePtr插入到p的next nodePtr.Next = p.Next p.Next.Pre = nodePtr nodePtr.Pre = p p.Next = nodePtr }
- 代码优化思路
- 可以将双向链表做成优先队列，通过优先队列可以保证每次删除的时间复杂度是logn级别，在本次的代码中，在极端的情况下，比如LFU的容量做的无限大的时候，不断进行put操作，会导致move方法的时间复杂度是On
golang版本永久算法题训练营本年最低价～
奔跑的小梁，公众号：梁霖编程工具库
