fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
算法就像搭乐高：带你手撸 LFU 算法 :: labuladong的算法小抄
这个是否可以 定义后面的 freq2Key的 数据结构 为 HashMap<Integer,int[]> 这样拿到 minFreq 也能迅速定位吧 不成熟的小想法
看了东哥的LRU想着LFU也能手写出来，没想到花了一个多小时哈哈。 下面是我的代码，和东哥的思路不一样。
class LFUCache {
LinedList list;
public LFUCache(int capacity) {
list = new LinedList(capacity);
}
public int get(int key) {
return list.get(key);
}
public void put(int key, int value) {
list.add(key, value);
}
}
class LinedList {
Map<Integer, Node> map = new HashMap<>();
TreeMap<Integer, Node> fluentMap = new TreeMap<>();
Node head;
Node tail;//越靠近tail频率越高，如果频率一样的话，那么最近被访问的会更靠近
int capacity;
int size;
public LinedList(int c) {
head = new Node();
tail = new Node();
head.next = tail;
head.fluent = 0;
tail.prev = head;
tail.fluent = Integer.MAX_VALUE;
capacity = c;
size = 0;
// fluentMap.put(0, head);
}
public int get(int k) {
if (!map.containsKey(k)) {
return -1;
}
Node node = map.get(k);
fluentAdjust(node);
return node.value;
}
private void fluentAdjust(Node node) {
//更新我以前的频率或者删除已经不在存在的频率
if (node.next.fluent != node.fluent && node.prev.fluent != node.fluent) {//我是唯一一个这个频率的，现在我要走了，删除
fluentMap.remove(node.fluent);
} else if (node.next.fluent != node.fluent && node.prev.fluent == node.fluent) {//我是最后一个这个频率的
fluentMap.put(node.fluent, node.prev);
}
node.fluent++;
Node pre=head;
Map.Entry<Integer, Node> nodeEntry = fluentMap.floorEntry(node.fluent);
if(nodeEntry!=null){
pre=nodeEntry.getValue();
}
//把以前的接上来
remove(node);
Node next = pre.next;
pre.next=node;
node.prev=pre;
next.prev=node;
node.next=next;
fluentMap.put(node.fluent,node);
// Node cur=node,pre=node.prev;
// while(node.fluent<=cur.next.fluent){
// pre=cur;
// cur=cur.next;
// }
//删除node
// node.prev.next = node.next;
// node.next.prev = node.prev;
//链接node到正确的位置
// node.prev = pre;
// node.next = cur;
// pre.next = node;
// cur.prev = node;
}
public void remove(Node node){
Node pre = node.prev;
Node next = node.next;
pre.next=next;
next.prev=pre;
}
public void add(int k, int v) {
if(capacity==0){
return;
}
if (map.containsKey(k)) {
//更新节点
Node node = map.get(k);
node.value = v;
fluentAdjust(node);
} else {
if (size >= capacity) {
//移出最前面的
if (head.next != tail) {
int key = head.next.key;
// map.remove(key);
Node node = map.remove(key);
if (node.fluent != node.next.fluent) {
fluentMap.remove(node.fluent);
}
head.next.next.prev = head;
head.next = head.next.next;
}
}
Node node = new Node(k, v);
Node cur = fluentMap.get(1);
if(cur==null){
cur=head;
}
Node next=cur.next;
cur.next=node;
node.prev=cur;
node.next=next;
next.prev=node;
//因为新加入的频率是1
// Node cur = head.next;
// Node pre = head;
// while (cur.fluent <= 1) {
// pre = cur;
// cur = cur.next;
// }
// pre.next = node;
// node.prev = pre;
// cur.prev = node;
// node.next = cur;
fluentMap.put(1,node);
map.put(k,node);
size++;
}
}
}
class Node {
int key;
int value;
int fluent;
Node next;
Node prev;
public Node() {
}
public Node(int k, int v) {
key = k;
value = v;
fluent = 1;
}
}
贴一个C++版本，用了两个哈希链表，感觉比较容易理解和记住
struct Node {
int key;
int val;
int freq;
Node(int _key, int _val, int _freq): key(_key), val(_val), freq(_freq) {}
};
class LFUCache {
unordered_map<int, list<Node>::iterator> key_table; // 每个键key保存着对应的链表节点的地址，注意这里必须保存地址，否则对链表节点的修改需要手动更新哈希表
unordered_map<int, list<Node>> freq_table; // 每个freq对应一个链表，表头是最新的元素，表尾是最旧的元素
int capacity;
int min_freq = 0;
public:
LFUCache(int capacity) {
this->capacity = capacity;
key_table.clear();
freq_table.clear();
}
// 用于超出容量时，删除最小使用频率的最不常用的节点，也就是其链表的尾节点
void removeLast(int freq) {
Node last = freq_table[freq].back(); // 找到这个freq对应的链表list_node中的表尾元素
key_table.erase(last.key); // 将其从key_table中删除
freq_table[freq].pop_back(); // 将其从list_node删除
if (freq_table[freq].size() == 0) { // 如果这条链表为空了，则直接删除这个键表对，并更新min_freq
freq_table.erase(freq);
if (min_freq == freq) min_freq++;
}
}
// 用于当调用get或put当键存在时，将其从freq的链表中删除然后放到freq + 1的链表表头, 此函数中除了freq对应的链表节点全部被删除的情况外，min_freq不需要更新，因为freq只增加不减少
void moveToHead(int key) {
// 首先将节点从freq的链表中删除
list<Node>::iterator iter = key_table[key];
int val = iter->val;
int freq = iter->freq;
freq_table[freq].erase(iter);
if (freq_table[freq].size() == 0) { // 如果这条链表为空了，则直接删除这个键表对，并更新min_freq
freq_table.erase(freq);
if (min_freq == freq) min_freq++;
}
// 然后将该节点加入到freq + 1的链表头部
// 由于freq_table[freq].erase(iter)会直接将iter指针从链表中删除，需要创建一个新的节点放到freq+1链表表头，并更新key_table中的key对应的节点地址
freq_table[freq + 1].push_front(Node(key, val, freq + 1));
key_table[key] = freq_table[freq + 1].begin();
}
int get(int key) {
if (!key_table.count(key) || capacity == 0) return -1;
moveToHead(key);
return key_table[key]->val;
}
void put(int key, int value) {
if (capacity == 0) return;
// 如果这个键值对存在，则直接修改并更新freq
if (key_table.count(key)) {
auto iter = key_table[key];
iter->val = value;
moveToHead(key);
return;
}
// 如果键不存在
if (key_table.size() == capacity) {
removeLast(min_freq);
}
freq_table[1].push_front(Node(key, value, 1));
key_table[key] = freq_table[1].begin();
min_freq = 1;
}
};
照着写了个Python版本，用OrderedDict替代LinkedHashSet
from collections import OrderedDict
class LFUCache:
def __init__(self, capacity):
self.key2val = {} # key 到 val 的映射，我们后文称为 KV 表
self.key2freq = {} # key 到 freq 的映射，我们后文称为 KF 表
self.freq2key = {} # freq 到 key 列表的映射，我们后文称为 FK 表
self.min_freq = 0 # 记录最小的频次
self.capacity = capacity # 记录 LFU 缓存的最大容量
def get(self, key: int) -> int:
if key not in self.key2val.keys():
return -1
# 增加 key 对应的 freq
self.increase_freq(key)
return self.key2val[key]
def put(self, key: int, val: int):
if self.capacity <= 0:
return
# 若 key 已存在，修改对应的 val 即可
if key in self.key2val.keys():
self.key2val[key] = val
self.increase_freq(key)
return
# key不存在，需要插入,容量已满的话需要淘汰一个freq最小的key
if self.capacity <= self.key2val.__len__():
self.remove_minfreqkey(key)
# 插入 key 和 val，对应的 freq 为 1
self.key2val[key] = val
self.key2freq[key] = 1
if 1 not in self.freq2key.keys():
self.freq2key[1] = OrderedDict()
self.freq2key[1][key] = None
# 插入新 key 后最小的 freq 肯定是 1
self.min_freq = 1
def increase_freq(self, key):
freq = self.key2freq[key]
self.key2freq[key] += 1
# 将 key 从 freq 对应的列表中删除
self.freq2key[freq].pop(key)
# 如果 freq 对应的列表空了，移除这个 freq
if freq + 1 not in self.freq2key.keys():
self.freq2key[freq + 1] = OrderedDict()
self.freq2key[freq + 1][key] = None
# 如果 freq 对应的列表空了，移除这个 freq
if len(self.freq2key[freq]) == 0:
self.freq2key.pop(freq)
# 如果这个 freq 恰好是 minFreq，更新 minFreq
if self.min_freq == freq:
self.min_freq += 1
def remove_minfreqkey(self, key):
# req 最小的 key 列表
key_dict = self.freq2key[self.min_freq]
# 其中最先被插入的那个 key 就是该被淘汰的 key
delete_key, _ = key_dict.popitem(last=False) # last=True:LIFO;last=False:FIFO
if len(key_dict) == 0:
self.freq2key.pop(self.min_freq)
# 问：这里需要更新 minFreq 的值吗？
self.key2val.pop(delete_key)
self.key2freq.pop(delete_key)
C++ copy ，通过 map 、list 和迭代器实现哈希链表：
class LFUCache {
public:
unordered_map<int, int> keyToVal; // 存储 key-value
unordered_map<int, int> keyToFreq; // 存储 key-freq(计数值)
unordered_map<int, list<int>> freqToKeys; // 存储 freq-keys(list) 一对多的关系，一个计数值对应多个 key
unordered_map<int, list<int>::iterator> keyToFKNode; // 存储 key - key 在 FK 中的位置，keys(list) 的迭代器，表示 FK[key] 这条链表上的一个节点位置
int cap;
int minFreq;
LFUCache(int capacity) : cap(capacity), minFreq(0) { }
int get(int key) {
if(!keyToVal.count(key)) {
return -1;
}
increaseFreq(key);
return keyToVal[key];
}
void put(int key, int value) {
if(cap <= 0) return;
if(keyToVal.count(key)) {
keyToVal[key] = value;
increaseFreq(key);
return;
}
if(cap <= keyToVal.size()) {
removeMinFreqKey();
}
keyToVal[key] = value;
keyToFreq[key] = 1;
if(!freqToKeys.count(1)) {
freqToKeys[1] = list<int>();
}
freqToKeys[1].push_back(key);
keyToFKNode[key] = --freqToKeys[1].end();
minFreq = 1;
}
void removeMinFreqKey() {
int OldestKeyOfMinFreq = freqToKeys[minFreq].front();
freqToKeys[minFreq].pop_front();
keyToFKNode.erase(OldestKeyOfMinFreq);
if(freqToKeys[minFreq].empty()) {
freqToKeys.erase(minFreq);
}
keyToVal.erase(OldestKeyOfMinFreq);
keyToFreq.erase(OldestKeyOfMinFreq);
}
void increaseFreq(int key) {
// 获取 key 对应的 freq
int freq = keyToFreq[key];
// 更新 KF
keyToFreq[key] = freq + 1;
// 更新 FKS，删除旧的 freq
freqToKeys[freq].erase(keyToFKNode[key]);
if(freqToKeys[freq].empty()) {
freqToKeys.erase(freq);
// freq 对应的 keys 空了
if(freq == minFreq) {
minFreq++; // 如果 minFreq == freq，增加 minFreq （不用担心增加后的 minFreq 不存在，因为它至少会有一个当前这个 key 对应）
}
}
// 更新 FKS，添加新的 freq
if(!freqToKeys.count(freq + 1)) {
freqToKeys[freq + 1] = list<int>();
}
freqToKeys[freq + 1].push_back(key);
keyToFKNode[key] = --freqToKeys[freq + 1].end();
}
};
