146. LRU Cache
https://leetcode.com/problems/lru-cache/
solution
复合数据结构通常采用 unordered_map 或 map 辅助记录，加速寻址；配上 vector 或 list数据储存，加速连续选址或删除值
1.新数据放到链表的开头
2.数据被访问后，也需要放到链表开头
3.当超过LRU的容量之后，将链表尾部的数据删除
双向链表+哈希
# 一个类似字典item的node, 同时记录其前后的位置
class Node:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {} # key到Node的索引, 对于linked list, tree, graph等通过局部逐渐访问, 建立一个全局的快速访问
self.head = Node() # dummy head and tail
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self.remove_node(node)
self.add_to_head(node)
return node.value
def put(self, key: int, value: int) -> None:
if key in self.cache:
node = self.cache[key]
node.value = value # 记得更新value
self.remove_node(node)
self.add_to_head(node)
else:
node = Node(key, value)
self.cache[key] = node
self.add_to_head(node)
if len(self.cache) > self.capacity:
self.remove_tail()
def remove_node(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def add_to_head(self, node):
self.head.next.prev = node
node.next = self.head.next
self.head.next = node
node.prev = self.head
def remove_tail(self):
del self.cache[self.tail.prev.key]
node = self.tail.prev
self.remove_node(node)时间复杂度：O(1) 空间复杂度：O(1)
# ordered dict: 记录并保持了加入字典的顺序, 可能会不允许使用ordered dict
import collections
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.ordered_dict = collections.OrderedDict()
def get(self, key: int) -> int:
# 1.找到目标数据 2.将目标对象移至list前端
if key in self.ordered_dict:
value = self.ordered_dict[key]
self.ordered_dict.pop(key)
self.ordered_dict[key] = value
return value
else:
return -1
def put(self, key: int, value: int) -> None:
# 1.向list的前端加入对象 2.如果超过capacity，将list尾部的对象删除
if key in self.ordered_dict:
self.ordered_dict.pop(key)
self.ordered_dict[key] = value
if len(self.ordered_dict) > self.capacity:
self.ordered_dict.popitem(last=False)
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)时间复杂度：O() 空间复杂度：O()
follow up
多线程版本LRU
multiprocessing库: cpu-intensive 任务用 processPool, 如果是 io-intensive 任务用 threadPool
# https://zhuanlan.zhihu.com/p/126313561
# https://leetcode.com/problems/lfu-cache/solutions/3111521/o-1-time-full-explanation-hashtable-c-java-python3/
class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.freq = 1
self.prev = None
self.next = None
class DLinkedList:
def __init__(self):
self.dummy = Node(None, None)
self.dummy.next = self.dummy
self.dummy.prev = self.dummy
self.size = 0
def append(self, node: Node):
# 尾插入, 加到双向链表尾部
node.prev = self.dummy.prev
node.next = self.dummy
node.prev.next = node
self.dummy.prev = node
self.size += 1
def pop(self, node: Node = None):
if self.size == 0:
return
# 删除头部
if node is None:
node = self.dummy.next
node.prev.next = node.next
node.next.prev = node.prev
self.size -= 1
return node
class LFUCache:
def __init__(self, capacity: int):
from collections import defaultdict
self.key_to_node = {}
self.freq = defaultdict(DLinkedList)
self.min_freq = 0
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self.key_to_node:
return -1
node = self.key_to_node[key]
node_freq = node.freq
self.freq[node_freq].pop(node)
if self.min_freq == node_freq and self.freq[node_freq].size == 0:
self.min_freq += 1
node.freq += 1
self.freq[node.freq].append(node)
return node.val
def put(self, key: int, value: int) -> None:
if self.capacity == 0: return
if key in self.key_to_node:
node = self.key_to_node[key]
node_freq = node.freq
self.freq[node_freq].pop(node)
if self.min_freq == node_freq and self.freq[node_freq].size == 0:
self.min_freq += 1
node.freq += 1
node.val = value
self.freq[node.freq].append(node)
else:
if len(self.key_to_node) == self.capacity:
node = self.freq[self.min_freq].pop()
self.key_to_node.pop(node.key)
node = Node(key, value)
self.key_to_node[key] = node
self.freq[1].append(node)
self.min_freq = 1ordered_dict
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self._items = collections.defaultdict(int) # key: frequency.
self._freqs = collections.defaultdict(OrderedDict) # frequency: {key: val}
self._minFreq = 0 # Minimum used frequency for the keys in the cache.
def _update_freq(self, key: int, value: int = None) -> int:
"""
Update the _items and the _freqs with the input key, then return the latest value.
"""
f = self._items[key]
v = self._freqs[f].pop(key) # Remove the current key.
if value is not None: # Update with new value if any.
v = value
self._freqs[f + 1][key] = v # Add the key to the new frequency.
self._items[key] += 1 # Update the frequency in the items.
if self._minFreq == f and not self._freqs[f]: # Update minimum freq.
self._minFreq += 1
return v
def get(self, key: int) -> int:
if key not in self._items:
return -1
return self._update_freq(key)
def put(self, key: int, value: int) -> None:
if not self.capacity: # Not able to put anything.
return
if key in self._items:
self._update_freq(key, value)
else:
if len(self._items) == self.capacity: # Cache is full.
# 1. Pop the least frequently used key in _freqs[minimum freq].
# 2. Pop the same key from _items as it does not exist.
self._items.pop(
self._freqs[self._minFreq].popitem(last=False)[0])
# Add the new key.
self._minFreq = 1
self._items[key] = 1
self._freqs[1][key] = value时间复杂度：O() 空间复杂度：O()
Last updated