Lançado · em melhoria
Guia de Cache LRU · 3/6
Por enquanto, este capítulo está disponível apenas em inglês.
This chapter builds the hash map plus doubly linked list design in Python, explains each part, and then writes the same routine in C++, Java and TypeScript. Every version offers get and put in O(1) average time.
class Node:
__slots__ = ("key", "value", "prev", "next")
def __init__(self, key=None, value=None):
self.key, self.value = key, value
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.map = {} # key -> Node
self.head, self.tail = Node(), Node() # sentinels
self.head.next, self.tail.prev = self.tail, self.head
def _unlink(self, node):
node.prev.next, node.next.prev = node.next, node.prev
def _push_front(self, node):
node.prev, node.next = self.head, self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key, default=None):
node = self.map.get(key)
if node is None:
return default
self._unlink(node)
self._push_front(node)
return node.value
def put(self, key, value):
if self.capacity <= 0:
return
node = self.map.get(key)
if node is not None: # update: touch, never evict
node.value = value
self._unlink(node)
self._push_front(node)
return
if len(self.map) >= self.capacity: # full: drop the least recent
lru = self.tail.prev
self._unlink(lru)
del self.map[lru.key]
node = Node(key, value)
self.map[key] = node
self._push_front(node)
cache = LRUCache(2)
cache.put("a", 1); cache.put("b", 2)
cache.get("a")
cache.put("c", 3) # evicts "b"
print(cache.get("b"), cache.get("a"), cache.get("c")) # None 1 3Line by line:
__slots__ makes each node a small fixed record without a per-instance dictionary, which matters with millions of entries.head <-> tail, so the helpers never meet None._unlink and _push_front change a constant number of pointers; moving a node is one call of each.get returns a default instead of -1, so any value, including negative numbers, can be cached. A hit "touches" the node, which is what makes the policy LRU rather than FIFO.put handles three cases in order: capacity 0, an existing key, a new key. del self.map[lru.key] is why nodes store their key.In application code, collections.OrderedDict with move_to_end and popitem(last=False) gives the same behaviour in a few lines, as in the trace of the previous chapter.
std::list is a doubly linked list, and splice moves a node to the front without copying it or invalidating iterators. The map stores list iterators.
#include <list>
#include <optional>
#include <unordered_map>
#include <utility>
class LRUCache {
public:
explicit LRUCache(std::size_t capacity) : capacity_(capacity) {}
std::optional<int> get(int key) {
auto it = index_.find(key);
if (it == index_.end()) return std::nullopt;
order_.splice(order_.begin(), order_, it->second); // touch
return it->second->second;
}
void put(int key, int value) {
if (capacity_ == 0) return;
if (auto it = index_.find(key); it != index_.end()) {
it->second->second = value;
order_.splice(order_.begin(), order_, it->second);
return;
}
if (index_.size() == capacity_) {
index_.erase(order_.back().first); // back = least recent
order_.pop_back();
}
order_.emplace_front(key, value);
index_[key] = order_.begin();
}
private:
std::size_t capacity_;
std::list<std::pair<int, int>> order_; // front = most recent
std::unordered_map<int, std::list<std::pair<int, int>>::iterator> index_;
};The same structure with int keys and values; get returns -1 on a miss. LinkedHashMap with access order does the same job (see the real-world chapter).
import java.util.HashMap;
import java.util.Map;
public class LRUCache {
private static final class Node {
int key, value; Node prev, next;
Node(int key, int value) { this.key = key; this.value = value; }
}
private final int capacity;
private final Map<Integer, Node> map = new HashMap<>();
private final Node head = new Node(0, 0), tail = new Node(0, 0);
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node node = map.get(key);
if (node == null) return -1;
unlink(node);
pushFront(node);
return node.value;
}
public void put(int key, int value) {
if (capacity <= 0) return;
Node node = map.get(key);
if (node != null) {
node.value = value;
unlink(node);
pushFront(node);
return;
}
if (map.size() >= capacity) {
Node lru = tail.prev;
unlink(lru);
map.remove(lru.key);
}
node = new Node(key, value);
map.put(key, node);
pushFront(node);
}
private void unlink(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
private void pushFront(Node n) {
n.prev = head; n.next = head.next;
head.next.prev = n; head.next = n;
}
}A JavaScript Map iterates its keys in insertion order, as the language specification requires. Setting an existing key keeps its old position, but deleting it and setting it again moves it to the end. So the end of the map is the most recent entry and keys().next() yields the least recent one. Engines implement Map as a hash table with an ordered entry list, so these steps are O(1) on average and no hand-written list is needed.
class LRUCache<K, V> {
private readonly map = new Map<K, V>();
constructor(private readonly capacity: number) {}
get(key: K): V | undefined {
if (!this.map.has(key)) return undefined;
const value = this.map.get(key) as V;
this.map.delete(key); // re-insert: the key moves to the end
this.map.set(key, value);
return value;
}
put(key: K, value: V): void {
if (this.capacity <= 0) return;
if (this.map.has(key)) this.map.delete(key);
else if (this.map.size >= this.capacity) {
this.map.delete(this.map.keys().next().value as K); // first key = least recent
}
this.map.set(key, value);
}
}std::list::splice, TypeScript the insertion order of Map, Python can also use OrderedDict.
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.