Blog

leetcode146LRU缓存机制

leetcode146 LRU Cache

Posted by BY on January 2, 2020

前言

2020年了。

正文

问题来源

本问题来自leetcode上的146题。

问题描述

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

示例 1:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

分析：

用一个map来记录key与list.Element节点地址的映射关系。查找时先查询对应key是否有，若有则返回该值，并将该节点移到队列最后，若无返回-1；存储时先看缓存中是否有对应的key，若有则先更新，若没有则判断是否超过达到了预定的缓冲长度，若没有则直接插入，若已到达则删除第一个节点并删除key-value映射。

type LRUCache struct {
	cap int
	m map[int]*list.Element
	list *list.List
}

type LRUNode struct {
	key int
	value int
}

func Constructor(capacity int) LRUCache {
	return LRUCache {
		capacity,
		make(map[int]*list.Element),
		list.New(),
	}
}


func (this *LRUCache) Get(key int) int {
	v, ok := this.m[key]
	if  !ok {
		return -1
	}
	this.list.MoveToBack(v)
	return v.Value.(*LRUNode).value
}


func (this *LRUCache) Put(key int, value int)  {
	v, ok := this.m[key]
	if ok {
		v.Value.(*LRUNode).value = value
		this.list.MoveToBack(v)
		return
	}
	if this.list.Len() < this.cap {
		this.m[key] = this.list.PushBack(&LRUNode{key, value})
		return
	}
	delete(this.m, this.list.Front().Value.(*LRUNode).key)
	this.list.Remove(this.list.Front())
	this.m[key] = this.list.PushBack(&LRUNode{key, value})
}

golang反射会占用一些时间，若需要更加高效的实现，需要自身来实现list。
如下：

type Node struct {
	Key  int
	Val  int
	Next *Node
	Prev *Node
}

func (this *LRUCache) insert(node *Node) {
	tail := this.Tail
	node.Prev = tail.Prev
	tail.Prev.Next = node
	node.Next = tail
	tail.Prev = node
}

func (this *LRUCache) remove(node *Node) {
	node.Prev.Next = node.Next
	node.Next.Prev = node.Prev
}

type LRUCache struct {
	limit int
	hash  map[int]*Node
	Head  *Node
	Tail  *Node
}

func Constructor(capacity int) LRUCache {
	head, tail := new(Node), new(Node)
	head.Next, tail.Prev = tail, head
	return LRUCache{
		limit: capacity,
		hash:  make(map[int]*Node, capacity),
		Head:  head,
		Tail:  tail,
	}
}

func (this *LRUCache) Get(key int) int {
	if v, ok := this.hash[key]; ok {
		this.remove(v)
		this.insert(v)
		return v.Val
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if v, ok := this.hash[key]; ok {
		this.remove(v)
		this.insert(v)
		v.Val = value
		return
	}
	if len(this.hash) >= this.limit {
		h := this.Head.Next
		this.remove(h)
		delete(this.hash, h.Key)
	}
	node := &Node{Key: key, Val: value}
	this.hash[key] = node
	this.insert(node)
}

总结：

勤思考。

结语

不管怎么样好好加油。

CATALOG
    FEATURED TAGS
    Blog