LRU缓存是非常经典的数据结构设计,本文重点在于设计出get、put方法时间复杂度都为O(1)的LRU缓存
LRU缓存特征是当超出容量时会将最近最少使用的元素逐出
第一次的失败尝试——记录有效区间
记录有效区间的方法是通过计数器counter为每一个最近使用的元素记录最新计数,在每次访问的时候更新有效区间
比如对于容量为2的lru而已,先put(1,1),然后put(2,2),那么1的counter就会是0,2的counter是1,此时有效区间是[0,1]。那么当2再次被访问的时候,2的counter便会变为2,此时有效区间是[0,2],所以访问的1、2都是有效
当再次put(3,3)的时候,3的counter便为3,有效区间的右边界变为3;但因为已经超出容量此时有效区间就会在原来基础上缩小范围,所以最终的有效区间变成[1,3],那么1已经被排除有效区间之外了
然而这种做法的问题是一旦有效元素被多次访问,且put新元素的时候,就难以搞清楚有效区间在哪里,这需要更高的时间复杂度才可能做到文章来源:https://www.toymoban.com/news/detail-555303.html
通过测试用例的尝试——双向链表+hash表
从第一次失败的尝试我找到的瓶颈是无法在O(1)复杂度将最近使用的元素从任意逐出顺序中置为最后,而能做到这点的只有双向链表。然而双向链表找到元素复杂度确是O(1),那么便只能用上hash表从而使得时间复杂度优化到O(1)文章来源地址https://www.toymoban.com/news/detail-555303.html
type quickLinkedTable struct {
head, tail *qlt
cap int
m map[int]*qlt
}
func newQLT(cap int) *quickLinkedTable {
return &quickLinkedTable{
cap: cap,
m: make(map[int]*qlt, cap),
}
}
func (t *quickLinkedTable) push(key, value int) {
// 若当前key存在,则更新,并置于头部
if q, ok := t.m[key]; ok {
q.value = value
t.moveToHead(q)
return
}
// 创建新链表元素,使head指向该元素,并更新hash表
q := newQlt(key, value)
if t.head != nil {
t.head.next = q
}
q.pre = t.head
t.head = q
t.m[key] = q
if t.tail == nil {
t.tail = q
}
// 当超出容量时,删除尾部
if len(t.m) > t.cap {
tail := t.tail
t.tail = t.tail.next
t.tail.pre = nil
delete(t.m, tail.key)
}
}
func (t *quickLinkedTable) get(key int) int {
if q, ok := t.m[key]; ok {
t.moveToHead(q)
return q.value
}
return -1
}
func (t *quickLinkedTable) moveToHead(q *qlt) {
// q本身是head就直接返回(仅有head next为nil)
if q.next == nil {
return
}
// 若q是tail,则更新q next为新tail
// 若q不是tail,则将q移出去,使q前后元素相连
if q.pre == nil {
t.tail = q.next
t.tail.pre = nil
} else {
q.pre.next = q.next
}
q.next.pre = q.pre
// 使原head next指向q,并更新q为head,
q.pre = t.head
t.head.next = q
q.next = nil
t.head = q
}
type qlt struct {
key int
pre, next *qlt
value int
}
func newQlt(key, value int) *qlt {
return &qlt{key: key, value: value}
}
type LRUCache struct {
t *quickLinkedTable
}
func Constructor(capacity int) LRUCache {
return LRUCache{
t: newQLT(capacity),
}
}
func (this *LRUCache) Get(key int) int {
return this.t.get(key)
}
func (this *LRUCache) Put(key int, value int) {
this.t.push(key, value)
}
Ref
- https://leetcode.cn/problems/lru-cache/description/
到了这里,关于LRU数据结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!