内存淘汰机制之LRU与LFU
- LRU（Least Recently Used）：淘汰 近期最不会访问的数据
- LFU（Least Frequently Used）：淘汰 最不经常使用（访问次数少）
所谓淘汰就是将内存中指定部分的数据移除，释放空间提供给新来的数据。
LRU
LeetCode入口👉👉👉No.146
存数据，将数据插入链表头部；如果内存满了，需要先将链表尾部数据删除，再插入
取数据，每次将取到的数据重新放到链表头部
LRU一般使用哈希链表（哈希表+双向链表）实现，可以在 \(O(1)\) 复杂度内实现插入、删除。
coding：
#--python
#使用python自带哈希链表（有序字典OrderedDict）实现
from collections import OrderedDict
class LRUCache(OrderedDict):
def __init__(self, capacity: int):
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self:
return -1
self.move_to_end(key)
return self[key]
def put(self, key: int, value: int) -> None:
if key in self:
self.move_to_end(key)
self[key] = value #更新value
if len(self) > self.capacity:
self.popitem(last=False)
自己实现哈希链表
#--python
#哈希表+双向链表
class DLinkNode():
def __init__(self):
self.key = 0
self.value = 0
self.prev = None
self.next = None
class LRUCache():
def __init__(self,capacity):
self.cache = {}
self.size = 0
self.capacity = capacity
self.head,self.tail = DLinkNode(),DLinkNode()
self.head.next = self.tail
self.tail.prev = self.head
def _add_node(self,node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _remove_node(self,node):
prev = node.prev
prev.next = node.next
node.next.prev = prev
def _move_to_head(self,node):
self._remove_node(node)
self._add_node(node)
def _pop_tail(self):
node = self.tail.prev
self._remove_node(node)
return node
def get(self,key):
node = self.cache.get(key,None)
if node is None:
return -1
self._move_to_head(node)
return node.value
def put(self,key,value):
node = self.cache.get(key,None)
if node is None:#添加新node
if self.size >= self.capacity:
tail = self._pop_tail()
del self.cache[tail.key]
self.size -= 1
newNode = DLinkNode()
newNode.key = key
newNode.value = value
self.cache[key] = newNode
self._add_node(newNode)
self.size += 1
else: #更新value
node.value = value
self._move_to_head(node)
LFU
LeetCode入口👉👉👉No.460
- 维护一个访问频次的数据结构，取数据，访问频次加一，根据访问次数排序
- 存数据，当缓存满时，淘汰点访问次数最小的
使用双哈希表 keyMap 和 freqMap
coding：
#--python
#双哈希表
class Node:
def __init__(self, key, val, pre=None, nex=None, freq=0):
self.pre = pre
self.nex = nex
self.freq = freq
self.val = val
self.key = key
def insert(self, nex):
nex.pre = self
nex.nex = self.nex
self.nex.pre = nex
self.nex = nex
def create_linked_list():
head = Node(0, 0)
tail = Node(0, 0)
head.nex = tail
tail.pre = head
return (head, tail)
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.size = 0
self.minFreq = 0
self.freqMap = collections.defaultdict(create_linked_list)
self.keyMap = {}
def delete(self, node):
if node.pre:
node.pre.nex = node.nex
node.nex.pre = node.pre
if node.pre is self.freqMap[node.freq][0] and node.nex is self.freqMap[node.freq][-1]:
self.freqMap.pop(node.freq)
return node.key
def increase(self, node):
node.freq += 1
self.delete(node)
self.freqMap[node.freq][-1].pre.insert(node)
if node.freq == 1:
self.minFreq = 1
elif self.minFreq == node.freq - 1:
head, tail = self.freqMap[node.freq - 1]
if head.nex is tail:
self.minFreq = node.freq
def get(self, key: int) -> int:
if key in self.keyMap:
self.increase(self.keyMap[key])
return self.keyMap[key].val
return -1
def put(self, key: int, value: int) -> None:
if self.capacity != 0:
if key in self.keyMap:
node = self.keyMap[key]
node.val = value
else:
node = Node(key, value)
self.keyMap[key] = node
self.size += 1
if self.size > self.capacity:
self.size -= 1
deleted = self.delete(self.freqMap[self.minFreq][0].nex)
self.keyMap.pop(deleted)
self.increase(node)