LRU Cache_leetcode_go实现一个LRU缓存，container/list.Remove()内存释放的坑，指针传递，container/list元素改值
题目：
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
Follow up:
Could you do both operations in O(1) time complexity?
Example:
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
思路：
- 一道设计数据结构的题，不涉及算法，细节多。同时维护哈希表和链表保存数据。哈希实现快速查找，链表记录LRU。每次Put/Get都把节点挪到LRU链表的最后（先删后加）。
- 细节1:可选的面向对象编程，减少形参传递。
- 细节2:自己写双链表，或者用container/list。container/list本身就是双链表实现。root.prev指向尾节点，所以找头尾节点都不需要遍历。list.Front()，list.Back()执行时间均为O(1)。
- 细节3:cap指的是LRU容量，Get不需要修改，Put时超过容量，则踢除最少使用的节点。这也是用双链表的原因。
- 细节4:为什么map的v要用*list.Ellement。
错解（存在无法更新值的问题）：
type LRUCache struct {
lru *list.List
store map[int]*list.Element
cap int
}
type LruKv struct {
lruK int
lruV int
}
func Constructor(capacity int) LRUCache {
return LRUCache{
lru: list.New(),
store: make(map[int]*list.Element, capacity),
cap: capacity,
}
}
func (this *LRUCache) Get(key int) int {
elem, ok := this.store[key]
if !ok {
return -1
}
//更新lru
this.lru.Remove(elem) //map保存指针，方便删除
node := elem.Value.(LruKv)
this.lru.PushBack(LruKv{lruK: node.lruK, lruV: node.lruV,})
return elem.Value.(LruKv).lruV
}
func (this *LRUCache) Put(key int, value int) {
elem, ok := this.store[key]
if ok {
lruKvObj := elem.Value.(LruKv)
lruKvObj.lruV = value //map的v存成指针，方便更新值
this.lru.Remove(elem)
this.lru.PushBack(elem.Value.(LruKv))
} else {
this.lru.PushBack(LruKv{lruK:key,lruV:value})
lruKvObj := this.lru.Back()
this.store[key] = lruKvObj
}
//处理cap
if this.lru.Len() > this.cap {
elem := this.lru.Front()
node := elem.Value.(LruKv)
delete(this.store, node.lruK)
this.lru.Remove(elem)
}
}
解决：要注意container/list中的elem.Value.(type)是值传递，而不是引用传递，无法改值。只重重建节点再插入。解决办法是改list.Element.Value的类型为*LruKv。
错解：（有一个关于container/list修改值的坑）
package main
import (
"container/list"
)
type LRUCache struct {
lru *list.List
store map[int]*list.Element
cap int
}
type LruKv struct {
lruK int
lruV int
}
func Constructor(capacity int) LRUCache {
return LRUCache{
lru: list.New(),
store: make(map[int]*list.Element, capacity),
cap: capacity,
}
}
func (this *LRUCache) Get(key int) int {
elem, ok := this.store[key]
if !ok {
return -1
}
//更新lru
this.lru.Remove(elem) //map保存指针，方便删除
node := elem.Value.(*LruKv)
this.lru.PushBack(&LruKv{lruK: node.lruK, lruV: node.lruV,})
return elem.Value.(*LruKv).lruV
}
func (this *LRUCache) Put(key int, value int) {
elem, ok := this.store[key]
if ok {
lruKvObj := elem.Value.(*LruKv)
lruKvObj.lruV = value //map的v存成指针，方便更新值
this.lru.Remove(elem)
this.lru.PushBack(lruKvObj)
} else {
this.lru.PushBack(&LruKv{lruK:key,lruV:value})
lruKvObj := this.lru.Back()
this.store[key] = lruKvObj
}
//处理cap
if this.lru.Len() > this.cap {
elem := this.lru.Front()
node := elem.Value.(*LruKv)
delete(this.store, node.lruK)
this.lru.Remove(elem)
}
}
问题分析：一个用container/list的坑，this.lru.Remove(e Element)。为避免内存泄露，释放了e的存储空间。实现为利用e的prev next指针进行删除。所以要求Element不仅要有Value，还要附带链表信息。
由于是引用传递，所以会清空map[]中的值。导致出现的问题是map[key]中的*Element仅有Value，没有链表信息。在插入重复元素时删除会失败。产生了冗余元素。
所以矛盾冲突在于list.Remove()方法的形参是引用传递，而本例实现map也是引用传递。在调用list.Remove()时，会析构形参*Element，影响其作为map的value被使用。影响的结果是清空了*Element所属的链表信息。进而导致更新value时，执行失败。元素个数多于预期。进而触发了扩容清理，从而导致逻辑错误。
解决：调用l.Remove()之后，更新map[]的对应值。
package main
import (
"container/list"
"fmt"
)
type LRUCache struct {
lru *list.List
store map[int]*list.Element
cap int
}
type LruKv struct {
lruK int
lruV int
}
func Constructor(capacity int) LRUCache {
return LRUCache{
lru: list.New(),
store: make(map[int]*list.Element, capacity),
cap: capacity,
}
}
func (this *LRUCache) Get(key int) int {
elem, ok := this.store[key]
if !ok {
return -1
}
//更新lru
this.lru.Remove(elem) //map保存指针，方便删除
node := elem.Value.(*LruKv)
this.lru.PushBack(&LruKv{lruK: node.lruK, lruV: node.lruV,})
this.store[key] = this.lru.Back()
return elem.Value.(*LruKv).lruV
}
func (this *LRUCache) Put(key int, value int) {
elem, ok := this.store[key]
if ok {
lruKvObj := elem.Value.(*LruKv)
lruKvObj.lruV = value //map的v存成指针，方便更新值
this.lru.Remove(elem)
this.lru.PushBack(lruKvObj)
//特殊应对l.Remove()
this.store[key] = this.lru.Back()
} else {
this.lru.PushBack(&LruKv{lruK:key,lruV:value})
lruKvObj := this.lru.Back()
this.store[key] = lruKvObj
}
//处理cap
if this.lru.Len() > this.cap {
elem := this.lru.Front()
node := elem.Value.(*LruKv)
delete(this.store, node.lruK)
this.lru.Remove(elem)
}
}
这个题测试输入太长，并且链表的变量跟踪进入的很深。调试了半天，所以mark一下Accepted。还有需要改进的地方。附注*Element存入map是指针，*Element.Value的值也是指针，才能实现改值。要不就要重新构建，并给map赋值。这也带了上述的问题。
Runtime: 176 ms, faster than 75.26% of Go online submissions for LRU Cache.
//TODO 需要做的优化，直接用双链表实现。container/list的Element很难用，编程变量都是一大串。还要做类型判断，简便地不要用.(type)，直接用.(LruKv)一行代码返回对象。
网友评论