Ltd的算法大抄·Cache

package main

import "container/list"

type LRUCache struct {
	cap      int                   // 最大容量
	list     *list.List            // 双向链表便于删除操作
	cacheMap map[int]*list.Element // map结构便于在O(1)时间操作缓存
}

type Node struct {
	key, value int
}

func Constructor1(capacity int) LRUCache {
	return LRUCache{
		cap:      capacity,
		list:     list.New(),
		cacheMap: make(map[int]*list.Element),
	}
}

func (l *LRUCache) Get(key int) int {
	//若存在就先把这个放到链表头，再返回这个对应的值
	if element, exist := l.cacheMap[key]; exist {
		l.list.MoveToFront(element)
		return element.Value.(*Node).value
	}
	return -1
}

func (l *LRUCache) Put(key, value int) {
	//若这个key已经存在了，需要更新值
	if element, exist := l.cacheMap[key]; exist {
		l.list.MoveToFront(element)
		element.Value.(*Node).value = value
		return
	}

	//若此时链表长度已经大于cap了，就删除尾部节点(过程淘汰)
	if l.list.Len() >= l.cap {
		tail := l.list.Back()
		k := tail.Value.(*Node).key
		l.list.Remove(tail)
		delete(l.cacheMap, k)
	}
	//将这个k-v放到链表头
	element := l.list.PushFront(&Node{key, value})
	l.cacheMap[key] = element
}

// list.element包含list字段，这个字段包含了根节点和长度用于判断是否是这个list中的节点

type LFUCache struct {
   capacity int
   //保存使用频率的最小值
   minFreq int
   // 映射key到节点
   cache map[int]*list.Element
   // 映射freq到双向链表的map
   freqMap map[int]*list.List
}

// 每个双向链表节点的类型
type listElement struct {
   key  int
   val  int
   freq int
}

package main

import "container/list"

//执行耗时:460 ms,击败了67.11% 的Go用户
//内存消耗:72.6 MB,击败了94.22% 的Go用户

type LFUCache struct {
	capacity int
	//保存使用频率的最小值
	minFreq int
	// 映射key到节点
	cache map[int]*list.Element
	// 映射freq到双向链表的map
	freqMap map[int]*list.List
}

// 每个双向链表节点的类型
type listElement struct {
	key  int
	val  int
	freq int
}

func Constructor(capacity int) LFUCache {
	return LFUCache{
		cache:    make(map[int]*list.Element),
		freqMap:  make(map[int]*list.List),
		capacity: capacity,
		minFreq:  0}
}

// Get 获取元素 需要从旧的双向链表中删除，并对freq+1，然后移动到新的双向链表的头部，最后返回这个值
func (l *LFUCache) Get(key int) int {
	if l.capacity == 0 {
		return -1
	}
	//获取这个节点元素
	element, exist := l.cache[key]
	if !exist {
		return -1
	}
	listNode := element.Value.(*listElement)
	//将这个元素从双向链表中删除
	l.freqMap[listNode.freq].Remove(element)
	//当旧的freq双向链表中没有节点了
	if l.freqMap[listNode.freq].Len() == 0 {
		//删除这个双向链表
		//delete(l.freqMap, listNode.freq)
		//如果那个freq正好是minFreq，那么就把minFreq改为新的freq
		if l.minFreq == listNode.freq {
			l.minFreq++
		}
	}

	//freq加一
	listNode.freq++

	//判断freq对应的双向链表是否存在
	newList, exist := l.freqMap[listNode.freq]
	if !exist {
		//不存在的话newList是nil，需要新建一个
		newList = list.New()
		//并让新的freq指向这个双向链表
		l.freqMap[listNode.freq] = newList
	}
	//移动到新的双向链表头部
	l.cache[key] = newList.PushFront(listNode)

	return listNode.val
}

/*
Put操作的基本思路
存入元素，需要判断是否是新的key
	- 若是旧的就修改这个值，从旧的双向链表中删除，并加入到freq+1的双向链表中，结束
	- 若新的需要创建一个新节点，同时判断当前是否已经满了
		- 若满了需要删除最少最不常用那个
			- 删除minFreq对应双向链表的尾节点
		- 若没满就加入这个值
			- 判断freq=1对应的双向链表是否存在
				- 若不存在先创建
				- 再将这个节点加入到freq=1的双向链表头部
*/

func (l *LFUCache) Put(key int, value int) {
	if l.capacity == 0 {
		return
	}
	val, exist := l.cache[key]
	//若key存在
	if exist {
		element := val.Value.(*listElement)
		//从旧的双向链表里面删除
		l.freqMap[element.freq].Remove(val)
		if l.freqMap[element.freq].Len() == 0 {
			//delete(l.freqMap, element.freq)
			if l.minFreq == element.freq {
				l.minFreq++
			}
		}
		//修改值
		element.val = value
		element.freq++
		//将这个放到新的并重新赋值
		newList, exist := l.freqMap[element.freq]
		if !exist {
			newList = list.New()
			l.freqMap[element.freq] = newList
		}
		l.cache[key] = newList.PushFront(element)
		return
	}
	//创建新的节点
	newElement := &listElement{key, value, 1}
	//如果满了就需要先删除再进行下面的操作
	if l.capacity == len(l.cache) {
		deletedNode := l.freqMap[l.minFreq].Back()
		//删除最后面的
		l.freqMap[l.minFreq].Remove(deletedNode)
		//if l.freqMap[l.minFreq].Len() == 0 {
		//	delete(l.freqMap, l.minFreq)
		//}
		//在cache表中也删除
		delete(l.cache, deletedNode.Value.(*listElement).key)
	}
	//如果没有满
	l.minFreq = 1
	//判断是否存在
	newList, exist := l.freqMap[l.minFreq]
	if !exist {
		newList = list.New()
		//将这个freq指向这个双向链表
		l.freqMap[l.minFreq] = newList
	}
	//将新的元素放进双向链表的头
	l.cache[key] = newList.PushFront(newElement)
}