LRU-K golang实现 魔改leetcode-LRU题目 微派三面
2022/4/4 23:49:39
本文主要是介绍LRU-K golang实现 魔改leetcode-LRU题目 微派三面,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
微派三面的时候,面试官问了LRU-K,当时没实现出来,受益良多,事后去魔改了下LeetCode146-LRU题目
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类:
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
比起这道题,我多设计了一个History队列~~
敲出来简单实现了下,以后有机会或者认识更加深入之后再重新总结写一篇文章,以下附一下我的思路:
其实history队列相当于LRU_Cache,只是需要维护一个K值。于是我多附加了一个map[int]int,用于记录对应Key被调用了多少次!当时面试官提供了结构体维护的思路,其实都可以,可能map会耗费多点性能?(存疑)
LRU其实就是LRU-1!!!
相比LRU,LRU-K需要多维护一个队列,用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候,才将数据放入缓存。当需要淘汰数据时,LRU-K会淘汰第K次访问时间距当前时间最大的数据。详细实现如下
(1). 数据第一次被访问,加入到访问历史列表;
(2). 如果数据在访问历史列表里后没有达到K次访问,则按照一定规则(FIFO,LRU)淘汰;
(3). 当访问历史队列中的数据访问次数达到K次后,将数据索引从历史队列删除,将数据移到缓存队列中,并缓存此数据,缓存队列重新按照时间排序;
(4). 缓存数据队列中被再次访问后,重新排序;
(5). 需要淘汰数据时,淘汰缓存队列中排在末尾的数据,即:淘汰“倒数第K次访问离现在最久”的数据。
LRU-K具有LRU的优点,同时能够避免LRU的缺点,实际应用中LRU-2是综合各种因素后最优的选择,LRU-3或者更大的K值命中率会高,但适应性差,需要大量的数据访问才能将历史访问记录清除掉。
package main import "fmt" type LRUCache struct { size int capacity int cache map[int]*DLinkNode Head, Tail *DLinkNode his *History_cache } type History_cache struct { k int size int capacity int his_cache map[int]*DLinkNode Head, Tail *DLinkNode exist_nums map[int]int } type DLinkNode struct { key,value int Pre, Next *DLinkNode } func InitDlinkNode(key, value int) *DLinkNode { return &DLinkNode{key,value,nil,nil} } func Constructor_LRU(capacity int, h *History_cache) LRUCache { l := LRUCache{ 0, capacity, map[int]*DLinkNode{}, InitDlinkNode(0, 0), InitDlinkNode(0, 0), h, } l.Head.Next = l.Tail l.Tail.Pre = l.Head return l } func Constructor_His(capacity, k int) History_cache { h := History_cache{ k, 0, capacity, map[int]*DLinkNode{}, InitDlinkNode(0, 0), InitDlinkNode(0, 0), map[int]int{}, } h.Head.Next = h.Tail h.Tail.Pre = h.Head return h } func (lru *LRUCache) Get(key int) int { if _,ok := lru.cache[key];!ok { return -1 } node := lru.cache[key] lru.UpdateToHead(node, lru.Head) return node.value } func (lru *LRUCache) Put(key int, value int) { //判断lru缓存中有无key if _,ok := lru.cache[key];!ok { //如果无key,判断在历史队列中有无 if _, ok2 := lru.his.his_cache[key];!ok2{ //如果无,则新增 node := InitDlinkNode(key, value) lru.his.exist_nums[key]++ if lru.his.size >= lru.his.capacity { lru.DeleteLast(&lru.his.size, lru.his.his_cache, lru.his.Tail) } lru.his.his_cache[key] = node lru.InsertNewHead(&lru.his.size, node, lru.his.Head) }else{ //如果有,则分两种情况 1.<k 2.出历史队列,进入lru缓存 lru.his.exist_nums[key]++ if lru.his.exist_nums[key]>=lru.his.k{ node := lru.his.Head for node.Next!=lru.his.his_cache[key]{ node = node.Next } node.Next = node.Next.Next lru.his.size-- delete(lru.his.his_cache, key) delete(lru.his.exist_nums, key) if lru.size>=lru.capacity{ lru.DeleteLast(&lru.size, lru.cache, lru.Tail) } new_node := InitDlinkNode(key, value) lru.cache[key] = new_node lru.InsertNewHead(&lru.size, new_node, lru.Head) }else{ node := lru.his.his_cache[key] node.value = value lru.UpdateToHead(node, lru.his.Head) } } }else { node := lru.cache[key] node.value = value lru.UpdateToHead(node, lru.Head) } } func (lru *LRUCache) UpdateToHead(node *DLinkNode, linkHead *DLinkNode) { node.Pre.Next = node.Next node.Next.Pre = node.Pre temp := linkHead.Next linkHead.Next = node node.Pre = linkHead node.Next = temp temp.Pre = node } func (lru *LRUCache) DeleteLast(size *int, c map[int]*DLinkNode, linkTial *DLinkNode) { node := linkTial.Pre linkTial.Pre = node.Pre node.Pre.Next = node.Next node.Pre = nil node.Next = nil (*size)-- delete(c, node.key) } func (lru *LRUCache) InsertNewHead(size *int, node, linkHead *DLinkNode) { temp := linkHead.Next linkHead.Next = node node.Pre = linkHead temp.Pre = node node.Next = temp (*size)++ } func main() { his := Constructor_His(2, 2) lru := Constructor_LRU(2, &his) fmt.Println("----未输入数据前----") fmt.Println("历史队列的长度:", lru.his.size) fmt.Println("LRU缓存的长度:", lru.size) fmt.Println() fmt.Println("----第一次PUT(1, 2)----") lru.Put(1, 2) fmt.Println("历史队列的长度:", lru.his.size) fmt.Println("LRU缓存的长度:", lru.size) fmt.Println("第一次GET:", lru.Get(1)) fmt.Println("历史队列对应值出现次数:", lru.his.exist_nums[1]) fmt.Println() fmt.Println("----第二次次PUT(1, 2)----") lru.Put(1, 2) fmt.Println("历史队列的长度:", lru.his.size) fmt.Println("LRU缓存的长度:", lru.size) fmt.Println("第二次GET:", lru.Get(1)) fmt.Println("历史队列对应值出现次数:", lru.his.exist_nums[1]) }
这台电脑windows下没装环境,所以用白板敲了之后,在菜鸟go在线工具下编译的~~~~
这篇关于LRU-K golang实现 魔改leetcode-LRU题目 微派三面的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-20MongoDB教程:从入门到实践详解
- 2024-11-17执行 Google Ads API 查询后返回的是空数组什么原因?-icode9专业技术文章分享
- 2024-11-17google广告数据不同经理账户下的凭证可以获取对方的api数据吗?-icode9专业技术文章分享
- 2024-11-15SendGrid 的 Go 客户端库怎么实现同时向多个邮箱发送邮件?-icode9专业技术文章分享
- 2024-11-15SendGrid 的 Go 客户端库怎么设置header 和 标签tag 呢?-icode9专业技术文章分享
- 2024-11-12Cargo deny安装指路
- 2024-11-02MongoDB项目实战:从入门到初级应用
- 2024-11-01随时随地一键转录,Google Cloud 新模型 Chirp 2 让语音识别更上一层楼
- 2024-10-25Google Cloud动手实验详解:如何在Cloud Run上开发无服务器应用
- 2024-10-24AI ?先驱齐聚 BAAI 2024,发布大规模语言、多模态、具身、生物计算以及 FlagOpen 2.0 等 AI 模型创新成果。