LFU Cache
update Aug 24, 2017 23:14
Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.
Follow up: Could you do both operations in O(1) time complexity?
Example:
LFUCache cache = new LFUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.get(3); // returns 3.
cache.put(4, 4); // evicts key 1.
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
Basic Idea:
这里 有一个非常不错的分析文章。
在我的实现中，整个数据结构示意图： 
基本思想就是：
- 外层： 维护FreqNode系统，保证O(1)时间找到任何freq的fnode（利用FreqMap），同时要做到产生新的freq时候要增加fnode，内部 dnode 为空时候要删除 fnode；
- 内层： 在每个 fnode 下面维护 DataNode 的链表。当某 dnode 的 freq 提升时（该key被set或者get），要将其移动到 freq+1 的 fnode 下。同时在每个 fnode 内部的链表中保持 LRU 原则，即从tail插入，从head删除；
- 另外，当cache满，需要删除现有dnode时候，选择最左边 fnode 下的 dnode 进行删除。
Java Code:
public class LFUCache {
private class FreqNode {
int freq;
FreqNode prev = null;
FreqNode next = null;
DataNode head = null;
DataNode tail = null;
public FreqNode(int freq) {
this.freq = freq;
head = new DataNode(-1, -1);
tail = new DataNode(-1, -1);
head.next = tail;
tail.prev = head;
}
}
private class DataNode {
int key;
int val;
int freq = 1;
DataNode prev = null;
DataNode next = null;
public DataNode(int key, int val) {
this.key = key;
this.val = val;
}
}
private Map<Integer, FreqNode> FreqMap;
private Map<Integer, DataNode> DataMap;
private FreqNode head;
private FreqNode tail;
private int capacity;
public LFUCache(int capacity) {
this.capacity = capacity;
FreqMap = new HashMap<>();
DataMap = new HashMap<>();
head = new FreqNode(0);
tail = new FreqNode(0);
head.next = tail;
tail.prev = head;
}
public void put(int key, int value) {
if (capacity == 0) return;
if (DataMap.containsKey(key)) {
DataNode dnode = DataMap.get(key);
dnode.val = value;
updateFreq(dnode);
} else {
// 若cache已满, 删除head.next freqnode中的第一个datanode（最老的）
// 如果移去之后，当前freqnode为空，则删去
if (DataMap.size() == capacity) {
FreqNode fnode = head.next;
DataNode dnode = fnode.head.next;
DataMap.remove(dnode.key);
removeDataNode(dnode);
if (fnode.head.next == fnode.tail) {
FreqMap.remove(fnode.freq);
removeFreqNode(fnode);
}
}
// 新建新的datanode，插入freq为1的freqnode的tail前(如果没有freq=1，则要新建)
ensureFirstFreqNode();
FreqNode fnode = FreqMap.get(1);
DataNode dnode = new DataNode(key, value);
DataMap.put(key, dnode);
insertDataNode(dnode, fnode);
}
}
public int get(int key) {
if (! DataMap.containsKey(key)) return -1;
DataNode dnode = DataMap.get(key);
updateFreq(dnode);
return dnode.val;
}
// 确保当前结构中有freq=1的fnode
private void ensureFirstFreqNode() {
if (FreqMap.containsKey(1)) return;
FreqNode fnode = new FreqNode(1);
fnode.next = head.next;
fnode.prev = head;
fnode.next.prev = fnode;
head.next = fnode;
FreqMap.put(1, fnode);
}
// 令当前datanode的freq+=1，完成相关所有操作
private void updateFreq(DataNode dnode) {
// 先看freq+1是否存在，若不存在，则新建之后插入
int new_freq = dnode.freq + 1;
FreqNode new_fnode = null;
FreqNode prev_fnode = FreqMap.get(dnode.freq);
if (! FreqMap.containsKey(new_freq)) {
new_fnode = new FreqNode(new_freq);
FreqMap.put(new_freq, new_fnode);
new_fnode.prev = prev_fnode;
new_fnode.next = prev_fnode.next;
prev_fnode.next = new_fnode;
new_fnode.next.prev = new_fnode;
}
// 在原fnode中删去dnode，如果之后原fnode为空，则删去fnode
removeDataNode(dnode);
if (prev_fnode.head.next == prev_fnode.tail) {
removeFreqNode(prev_fnode);
FreqMap.remove(prev_fnode.freq);
}
// 更新dnode的freq，并插入新freq对应的fnode
dnode.freq++;
new_fnode = FreqMap.get(dnode.freq);
insertDataNode(dnode, new_fnode);
}
// 把datanode插入当前freqnode的tail前
private void insertDataNode(DataNode dnode, FreqNode fnode) {
dnode.prev = fnode.tail.prev;
dnode.next = fnode.tail;
fnode.tail.prev = dnode;
dnode.prev.next = dnode;
}
private void removeFreqNode(FreqNode fnode) {
fnode.prev.next = fnode.next;
fnode.next.prev = fnode.prev;
}
private void removeDataNode(DataNode dnode) {
dnode.prev.next = dnode.next;
dnode.next.prev = dnode.prev;
}
}
Python Code
class FreqNode(object):
def __init__(self, freq):
self.freq = freq
self.prev = None
self.next = None
self.head = DataNode(-1, -1)
self.tail = DataNode(-1, -1)
self.head.next = self.tail
self.tail.prev = self.head
class DataNode(object):
def __init__(self, key, value):
self.key = key
self.val = value
self.freq = 1
self.prev = None
self.next = None
class LFUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.capacity = capacity
self.head = FreqNode(0)
self.tail = FreqNode(0)
self.head.next = self.tail
self.tail.prev = self.head
self.FreqMap = {}
self.DataMap = {}
def get(self, key):
"""
:type key: int
:rtype: int
"""
if key not in self.DataMap:
return -1
dnode = self.DataMap[key]
self.updateFreq(dnode)
return dnode.val
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
if self.capacity == 0:
return
if key in self.DataMap:
dnode = self.DataMap[key]
dnode.val = value
self.updateFreq(dnode)
else:
# 若已满，则移除freq最小的fnode中靠近head的dnode
if len(self.DataMap) == self.capacity:
fnode = self.head.next
dnode = fnode.head.next
del self.DataMap[dnode.key]
self.removeDataNode(dnode)
if self.isEmpty(fnode):
del self.FreqMap[fnode.freq]
self.removeFreqNode(fnode)
self.ensureFirstFreq()
fnode = self.FreqMap[1]
dnode = DataNode(key, value)
self.DataMap[key] = dnode
self.insertDataNode(dnode, fnode)
def isEmpty(self, fnode):
return fnode.head.next == fnode.tail
def ensureFirstFreq(self):
if self.head.next.freq == 1:
return
fnode = FreqNode(1)
self.FreqMap[1] = fnode
fnode.next = self.head.next
fnode.prev = self.head
self.head.next = fnode
fnode.next.prev = fnode
def insertDataNode(self, dnode, fnode):
# 把dnode插入到fnode中的tail之前
dnode.next = fnode.tail
dnode.prev = fnode.tail.prev
dnode.next.prev = dnode
dnode.prev.next = dnode
def removeFreqNode(self, fnode):
fnode.prev.next = fnode.next
fnode.next.prev = fnode.prev
def removeDataNode(self, dnode):
dnode.prev.next = dnode.next
dnode.next.prev = dnode.prev
def updateFreq(self, dnode):
prev_fnode = self.FreqMap[dnode.freq]
# 检查freq+1是否存在，若存在，则移动，否则先建freq+1的node
if dnode.freq + 1 not in self.FreqMap:
new_fnode = FreqNode(dnode.freq + 1)
new_fnode.prev = prev_fnode
new_fnode.next = prev_fnode.next
new_fnode.prev.next = new_fnode;
new_fnode.next.prev = new_fnode;
self.FreqMap[dnode.freq + 1] = new_fnode
new_fnode = self.FreqMap[dnode.freq + 1]
self.removeDataNode(dnode)
self.insertDataNode(dnode, new_fnode)
if self.isEmpty(prev_fnode):
del self.FreqMap[dnode.freq]
self.removeFreqNode(prev_fnode)
dnode.freq += 1