資訊專欄INFORMATION COLUMN
摘要：首先要做到是，能想到的數據結構只有兩三種，一個是，一個是，是，還有一個，是。不太可能，因為長度要而且不可變，題目也沒說長度固定?？梢宰龅胶投际恰Ｒ驗檫€有函數，要可以，所以還需要一個數據結構來記錄順序，自然想到。
LRU Cache
題目鏈接：https://leetcode.com/problems...
這個題要求O(1)的復雜度。首先要做到get(key)是O(1)，能想到的數據結構只有兩三種，一個是HashMap
public class LRUCache {
class ListNode {
ListNode prev;
ListNode next;
int val = 0;
int key = 0;
ListNode() {}
ListNode(int key, int val) {
this.key = key;
this.val = val;
}
}
// new node(most recently) add to the tail part
public void append(ListNode node) {
node.prev = tail.prev;
tail.prev.next = node;
node.next = tail;
tail.prev = node;
}
// least recently node need to be remove from head
public void remove() {
remove(head.next);
}
// remove the certain node
public void remove(ListNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
ListNode head, tail;
Map map;
int remain;
public LRUCache(int capacity) {
remain = capacity;
// map for get
map = new HashMap();
// list for put
head = new ListNode();
tail = new ListNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if(map.containsKey(key)) {
// remove the key node to the tail
int value = map.get(key).val;
put(key, value);
return value;
}
else return -1;
}
public void put(int key, int value) {
if(map.containsKey(key)) {
ListNode node = map.get(key);
node.val = value;
remove(node);
append(node);
}
else {
// not contain, check if count > capacity
// remove the least recent node in list & map
if(remain == 0) {
map.remove(head.next.key);
remove();
remain++;
}
ListNode node = new ListNode(key, value);
append(node);
map.put(key, node);
remain--;
}
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
LFU Cache
題目鏈接：https://leetcode.com/problems...
上一題是只考慮出現的時間，這題加了frequency。那么再加一個map存freq應該是可行的?，F在node除了要保存順序還得保存freq，感覺上像是個二維的，先按freq排序再考慮出現順序。每次得保存下這個freq出現最早的值，再出現的時候，要從這freq里刪了，移到下一個freq的tail上。想了下感覺還是不太好做，看了網上的答案。
參考這個博客：
http://bookshadow.com/weblog/...
first -> point to the freqNode with freq = 1
Map
relation between freqNode:
first(freq 0) <-> freq 1 <-> freq 2 <-> ......
Map
get(key):
case 1: return -1
case 2: exist =>
find keyNode and remove from freqNode, if cur freqNode has no element, remove freqNode
find freqNode through freqMap,
find next freqNode(freq + 1) through freqNode,
add keyNode to the tail of next freqNode
put(key, value)
case 1: not exist in keyMap => add to the tail of freqNode with freq = 1
case 2: exist =>
find keyNode, set value and remove from freqNode, if cur freqNode has no element, remove freqNode
find freqNode through freqMap,
find next freqNode(freq + 1) through freqNode,
add keyNode to the tail of next freqNode
其中，keyNode和keyMap和上一題一樣都是可以用LinkedHashMap來實現的。那么這里可以稍微改一下，把keyMap里面直接放
public class LFUCache {
class freqNode {
int freq = 0;
freqNode prev, next;
// store keys
LinkedHashSet keyNodes = new LinkedHashSet();
freqNode() {}
freqNode(int freq) { this.freq = freq; }
public int delete() {
// if(keyNodes.isEmpty()) return;
int key = keyNodes.iterator().next();
keyNodes.remove(key);
return key;
}
public void delete(int key) {
// if(!keyNodes.contains(key)) return;
keyNodes.remove(key);
}
public void append(int key) {
keyNodes.add(key);
}
}
int remain;
// key, freqNode pair
Map freqMap;
// key, value pair
Map keyMap;
freqNode first;
freqNode last;
public LFUCache(int capacity) {
this.remain = capacity;
freqMap = new HashMap();
keyMap = new HashMap();
first = new freqNode();
last = new freqNode();
first.next = last;
last.next = first;
}
public int get(int key) {
if(!keyMap.containsKey(key)) return -1;
else {
updateFreq(key);
return keyMap.get(key);
}
}
public void put(int key, int value) {
if(!keyMap.containsKey(key)) {
if(remain == 0) {
if(first.next.freq == 0) return;
// remove the least frequent
int del = first.next.delete();
keyMap.remove(del);
freqMap.remove(del);
remain++;
}
// update map and add node
keyMap.put(key, value);
update(first, key);
remain--;
}
else {
updateFreq(key);
keyMap.put(key, value);
}
}
private void updateFreq(int key) {
freqNode node = freqMap.get(key);
update(node, key);
// remove current node if has no keyNodes
node.delete(key);
if(node.keyNodes.size() == 0) {
removeNode(node);
}
}
private void update(freqNode node, int key) {
// append to the next freq
addAfterNode(node);
node.next.append(key);
// update freqMap key with next freqNode
freqMap.put(key, node.next);
}
private void addAfterNode(freqNode node) {
if(node.next.freq != node.freq + 1) {
freqNode newNode = new freqNode(node.freq + 1);
freqNode temp = node.next;
node.next = newNode;
newNode.prev = node;
temp.prev = newNode;
newNode.next = temp;
node = null;
}
}
private void removeNode(freqNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
}
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache obj = new LFUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/66567.html
摘要：在靜態的頻率分布下，性能也落后于因為其不再為不在緩存中的數據維護任何頻率數據?？梢栽斠姷臏嗜胩蕴呗允切略鲆粋€新的元素時，判斷使用該元素替換一個舊元素，是否可以提升緩存命中率。 1. Introduction LFU的局限： LFU實現需要維護大而復雜的元數據（頻次統計數據等） 大多數實際工作負載中，訪問頻率隨著時間的推移而發生根本變化（這是外賣業務不適合樸素LFU的根本原因） 針...
摘要：在靜態的頻率分布下，性能也落后于因為其不再為不在緩存中的數據維護任何頻率數據?？梢栽斠姷臏嗜胩蕴呗允切略鲆粋€新的元素時，判斷使用該元素替換一個舊元素，是否可以提升緩存命中率。 1. Introduction LFU的局限： LFU實現需要維護大而復雜的元數據（頻次統計數據等） 大多數實際工作負載中，訪問頻率隨著時間的推移而發生根本變化（這是外賣業務不適合樸素LFU的根本原因） 針...
摘要：緩存算法我是，我會統計每一個緩存數據的使用頻率，我會把使用最少的緩存替換出緩存區。瀏覽器就是使用了我作為緩存算法。在緩存系統中找出最少最近的對象是需要較高的時空成本。再來一次機會的緩存算法，是對的優化。直到新的緩存對象被放入。 緩存 什么是緩存？ showImg(https://segmentfault.com/img/bVusZg); 存貯數據（使用頻繁的數據）的臨時地方，因為取原始...
閱讀 3264·2023-04-25 22:47
閱讀 3776·2021-10-11 10:59
閱讀 2310·2021-09-07 10:12
閱讀 4259·2021-08-11 11:15
閱讀 3439·2019-08-30 13:15
閱讀 1757·2019-08-30 13:00
閱讀 975·2019-08-29 14:02
閱讀 1690·2019-08-26 13:57
