设计：
- get 如何在缓存中，返回关键字的值 O(1) 的时间复杂度，这里我们比较容易想得到是用map 去存储
- put 如果key 已经存在，则变更数据，不存在则写入数据
- 如果插入关键字数量超过 capacity,则逐出最久未使用的关键字
总结下操作：
-
获取数据比较简单直接从map中判断存在，如果存在获取对应的值，如果不存在返回-1
-
put 数据 分步骤进行分析
-
判断数据元素是否存在，如果存在，则将元素删除，插入到头尾
-
判断元素数量是否超出限制，如果超出限制，则将尾部元素移除，将元素插入到头部
-
将元素插入到头部
因为要对元素进行O(1)时间复杂度的删除这个时候使用双向链表比较合适
1 2 3
2 1 []
head
tail
[]
head
tail
3
1 2 3
3 2 1
type LRUCache struct {
Cap int
M map[int]*DoubleLinkedList
Head *DoubleLinkedList
Tail *DoubleLinkedList
Size int
}
type DoubleLinkedList struct {
Value int
Pre *DoubleLinkedList
Next *DoubleLinkedList
}
func Constructor(capacity int) LRUCache {
return LRUCache {
Cap:capacity,
M:make(map[int]*DoubleLinkedList, capacity),
Head: &DoubleLinkedList{},
Tail: &DoubleLinkedList{},
Size:0,
}
}
func (this *LRUCache) Get(key int) int {
if _,ok := this.M[key];!ok {
return -1;
}
return this.M[key].Value;
}
func (this *LRUCache) Put(key int, value int) {
if n,ok := this.M[key];ok {
node := this.removeNode(n)
this.insertHead(node)
return
}
if this.Size >= this.Cap {
this.removeLast();
}
node := &DoubleLinkedList{
Value:value,
Pre:nil,
Next:nil,
}
this.insertHead(node)
this.M[key] = node
}
func (this *LRUCache)removeNode(node *DoubleLinkedList) *DoubleLinkedList {
node.Pre.Next = node.Next
node.Next.Pre = node.Pre
return node
}
func (this *LRUCache)insertHead(node *DoubleLinkedList) {
node.Next = this.Head
this.Head.Pre = node
this.Head = node
}
func (this *LRUCache) removeLast() {
this.Tail.Pre.Pre.Next = this.Tail
this.Tail.Pre = this.Pre.Pre
}
/**
* Your LRUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/
对比了之前参考写的，整体思路是正确的，不过对双向链表的定义不是很熟，还有不一样的之前写的是从尾部写入元素，从头部移除元素
type LRUCache struct {
mapCache map[int]*Node
cache *DoubleList
cap int
}
type Node struct {
key,val int
next,prev *Node
}
func NewNode(k,v int)*Node {
return &Node{key:k,val:v,next:&Node{},prev:&Node{},}
}
type DoubleList struct {
head,tail *Node
size int
}
func NewDoubleList() *DoubleList {
head := NewNode(0,0)
tail := NewNode(0,0)
head.next,tail.prev = tail,head
return &DoubleList{
head,
tail,
0,
}
}
func (this *DoubleList) AddLast(x *Node) {
fmt.Println(x)
fmt.Println(this.tail)
x.prev = this.tail.prev
x.next = this.tail
this.tail.prev.next = x
this.tail.prev = x
this.size++
}
func (this *DoubleList)Remove(x *Node) {
x.prev.next = x.next
x.next.prev = x.prev
this.size--
}
func (this *DoubleList)RemoveFirst() *Node{
if this.head.next == this.tail {
return nil
}
first := this.head.next
this.Remove(first)
return first
}
func (this *DoubleList)Size() int {
return this.size
}
func Constructor(capacity int) LRUCache {
return LRUCache {
cap:capacity,
mapCache: make(map[int]*Node),
cache: NewDoubleList(),
}
}
func (this *LRUCache)makeRecently(key int){
x := this.mapCache[key]
this.cache.Remove(x)
this.cache.AddLast(x)
}
func (this *LRUCache)addRecently(key int,val int) {
x := NewNode(key,val)
this.cache.AddLast(x)
this.mapCache[key] = x
}
func (this *LRUCache)deleteKey(key int) {
x := this.mapCache[key]
this.cache.Remove(x)
delete(this.mapCache,key)
}
func (this *LRUCache)removeLeastRecently() {
deltedNode := this.cache.RemoveFirst()
deletedKey := deltedNode.key
delete(this.mapCache,deletedKey)
}
func (this *LRUCache) Get(key int) int {
if _,ok := this.mapCache[key];!ok {
return -1
}
this.makeRecently(key)
return this.mapCache[key].val
}
func (this *LRUCache) Put(key int, value int) {
if _,ok := this.mapCache[key];ok {
this.deleteKey(key)
this.addRecently(key,value)
return
}
if this.cap == this.cache.size {
this.removeLeastRecently()
}
this.addRecently(key,value)
}
/**
* Your LRUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/
思路是知道的，不过整体写下来还是发现对双向链表的操作和整体代码结构的设计不是很清晰，这个还是需要多加练习，所以理解代码是第一步，真正动手实现和解决问题才是考验能力的地方
mysql Innodb Buffer Pool 的lru cache:
分为 young区域和old 区域，防止冷数据的读取导致buffer pool 里面很多热数据过期。
redis的lru cache:
如果有大量数据访问，很多链表移动操作，会降低redis 缓存性能，redis 对lru算法做了简化，redis默认会记录每个数据的最近一次访问时间戳，然后决定淘汰数据的时候，第一次会随机选N个数据，作为后续集合。将lru字段值最小的数据淘汰出去，后续需要在淘汰数据的时候，选择小雨后续集合中最小的lru值加入集合，如果达到 maxmeory-samples,然后将lru值最小的数据淘汰。
生活
最近可能是前段时间篮球比赛还有自己打篮球比较多了，肩膀得了肌滑炎，医生建议不要打羽毛球了，篮球还是可以打的，运动要注意点。
本周在家看了下电影 画江湖之天罡，整体节奏和效果感觉还是很好看的，人物塑造也比较好，也有意识的引导自己去多看电影、读书、而不是去看短视频。
技术
2024年技术和代码，之前很多心思都在业务上，24年希望自己把Java 多熟悉一点，比如掌握单元测试保证程序的正确性、南大操作系统课程学习完、业务上更加熟悉，深入的去了解业务，扎下去，希望自己不要再慌慌忙忙，踏实的做一些东西。