当前位置:网站首页>460. LFU cache bidirectional linked list
460. LFU cache bidirectional linked list
2022-07-02 05:27:00 【Empress Yu】
460. LFU cache
Please help me The least used (LFU) Cache algorithm design and implementation of data structure .
Realization
LFUCache
class :
LFUCache(int capacity)
- With the capacity of the data structurecapacity
Initialize objectint get(int key)
- If keykey
In the cache , Then get the value of the key , Otherwise return to-1
.void put(int key, int value)
- If keykey
Already exists , Then change its value ; If the key doesn't exist , Please insert key value pair . When the cache reaches its capacitycapacity
when , Before inserting a new item , Remove the least frequently used items . In this question , When there is a draw ( That is, two or more keys have the same frequency of use ) when , It should be removed Most recently unused Key .To determine the least frequently used keys , You can maintain one for each key in the cache Use counter . The key with the lowest count is the key that has not been used for the longest time .
When a key is first inserted into the cache , Its usage counter is set to
1
( because put operation ). Execute... On the key in the cacheget
orput
operation , Using the counter will increment the value .function
get
andput
Must beO(1)
The average time complexity of running .Example :
Input : ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]] Output : [null, null, null, 1, null, -1, 3, null, -1, 3, 4] explain : // cnt(x) = key x Use count of // cache=[] The order of last use will be displayed ( The leftmost element is the closest ) LFUCache lfu = new LFUCache(2); lfu.put(1, 1); // cache=[1,_], cnt(1)=1 lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1 lfu.get(1); // return 1 // cache=[1,2], cnt(2)=1, cnt(1)=2 lfu.put(3, 3); // Remove the key 2 , because cnt(2)=1 , Use the minimum count // cache=[3,1], cnt(3)=1, cnt(1)=2 lfu.get(2); // return -1( Not found ) lfu.get(3); // return 3 // cache=[3,1], cnt(3)=2, cnt(1)=2 lfu.put(4, 4); // Remove the key 1 ,1 and 3 Of cnt identical , but 1 Not used for a long time // cache=[4,3], cnt(4)=1, cnt(3)=2 lfu.get(1); // return -1( Not found ) lfu.get(3); // return 3 // cache=[3,4], cnt(4)=1, cnt(3)=3 lfu.get(4); // return 4 // cache=[3,4], cnt(4)=2, cnt(3)=3Tips :
0 <= capacity <= 10^4
0 <= key <= 10^5
0 <= value <= 10^9
- Call at most
2 * 105
Timeget
andput
Methodsource : Power button (LeetCode)
link :https://leetcode.cn/problems/lfu-cache
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
The result of doing the question
success , It's not hard to , Two way linked list question , and LRU almost . I didn't have the courage to do this before , because The least used This awkward concept , It sounds like a headache . In fact, that is The least used ones are eliminated , In order to ensure that the memory consumption will not be too large
Method : Double linked list
WA summary
- 0 Long processing , Note that the capacity can be 0,WA 了
- key Existing situation , No updates value Value
Method : Double linked list
- Use leading and trailing pointers as boundaries
- Each node needs to record ( key , value , The frequency of , Latest time )
- Record key -> node mapping
- Record The frequency of -> The last node of this frequency mapping , In the initial situation, insert the head node , The frequency is 0
- get
- No element returned -1
- Update element frequency ( Let's take the previous frequency time be called Old frequency , time+1 be called New frequency ), Latest time
- Update element location
- Assume that the current element is the last element of the old frequency , Then remove , At the same time, put the previous node into the last element of the frequency of the previous node 【 There is no need to judge whether the frequency is the same , The same will add new nodes , Not the same 】
- If there are new frequency nodes , Then remove the node from its old location , At the same time, add to the next node of the last node before the new frequency 【1(1 Time )->2(2 Time ), increase 1 The interview of , After the update 2(2 Time )->1(2 Time ), because 1 Is the latest , At the same frequency , In the last 】
- If there is no new frequency node , But after removal , There are still old frequency nodes , Then move to the old frequency node , Behind the last node 【1(1 Time )->2(1 Time ), increase 1 The interview of , After the update 2(1 Time )->1(2 Time ),1 Put it after the next higher grade 】
- Other situations with intervals , The relative position has not changed , Do not move nodes 【2(1 Time )->1(2 Time )->5(4 Time ), increase 1 The number of times ,2(1 Time )->1(3 Time )->5(4 Time )】, Constant relative position
- put
- Capacity of 0, Do not add or process
- The capacity reaches the upper limit , Delete the first element , Note that the element at the end of the processing frequency is removed , Remove from the linked list and hash
- Update node value and latest time
- Update element location ( Same as get)
- In fact, the whole process does not need to maintain the latest time , The node has been maintained when it is added
class LFUCache {
Node first,last;// The head and tail nodes of a two-way linked list
int capacity;// size
Map<Integer,Node> map = new HashMap<>();// key -> node
Map<Integer,Node> timeLast = new HashMap<>();// The last element corresponding to frequency
public LFUCache(int capacity) {
first = new Node(-1,0,0);
last = new Node(-1,0,Integer.MAX_VALUE);
first.next = last;
last.prev = first;
this.capacity = capacity;
timeLast.put(0,first);
}
int curr = 0;// Current timestamp , It is defined as adding 1
public int get(int key) {
if(!map.containsKey(key)) return -1;
Node node = map.get(key);
node.last = ++curr;
move(node);
return map.get(key).val;
}
/**
* Add links
* @param prev Previous node
* @param curr Current node
*/
private void addLink(Node prev,Node curr){
Node next = prev.next;
curr.prev = prev;
curr.next = next;
prev.next = curr;
next.prev = curr;
}
/**
* Remove links , Pay attention to the processing of empty before and after the new node
* @param node Current node
*/
private void removeLink(Node node){
if(node.prev == null) return;
Node pre = node.prev;
Node nex = node.next;
node.prev = null;
node.next = null;
pre.next = nex;
nex.prev = pre;
}
public void put(int key, int value) {
//0 Long term situation handling (WA1)
if(capacity==0) return;
// Full capacity removal
if(!map.containsKey(key) && map.size()==capacity){
Node delNode = first.next;
removeTime(delNode);
removeLink(delNode);
map.remove(delNode.key);
}
Node node=map.getOrDefault(key,new Node(key,value,curr));
node.last = ++curr;
node.val = value;// Be careful , If there is no such sentence , The node cannot update the value in the future (WA2)
move(node);
map.put(key,node);
}
private void removeTime(Node node){
if(timeLast.getOrDefault(node.times,first).key==node.key){
timeLast.remove(node.times);
// If the previous node and the removed node are at the same level , Then this operation will take effect ; Otherwise, different levels , This operation does not take effect , No new value added
timeLast.put(node.prev.times,node.prev);
}
}
private void move(Node node){
// Assume that the current node is the last element of the current number , Delete
removeTime(node);
node.times++;
// If there are elements in the new level , Then the new element is placed at the last of the next level
if(timeLast.containsKey(node.times)){
removeLink(node);
Node prev = timeLast.get(node.times);
addLink(prev,node);
// If there are elements in the old level , Put it after the last element of the old level
}else if(timeLast.containsKey(node.times-1)){
removeLink(node);
Node prev = timeLast.get(node.times-1);
addLink(prev,node);
}
// The current element must be the last element of the new frequency , Replace the last element of the next level
timeLast.put(node.times,node);
}
class Node{
Node prev;
Node next;
int key;// key
int val;// value
int times;// frequency
int last;// The last time
public Node(int key,int val,int last){
this.key = key;
this.val = val;
this.last = last;
times = 0;
}
}
}
Time complexity :O(1)
Spatial complexity :O(n), You need to save various information of the node
边栏推荐
- Reflection of the soul of the frame (important knowledge)
- Fabric. JS compact JSON
- The El cascader echo only selects the questions that are not displayed
- LeetCode 1175. Prime number arrangement (prime number judgment + Combinatorial Mathematics)
- Gee data set: export the distribution and installed capacity of hydropower stations in the country to CSV table
- Gee: analyze the change of spatial centroid of remote sensing image [centroid acquisition analysis]
- Installation du tutoriel MySQL 8.0.22 par centos8
- Gee dataset: chirps pentad high resolution global grid rainfall dataset
- Gee: create a new feature and set corresponding attributes
- Fabric. JS iText set italics manually
猜你喜欢
[technical notes-08]
Importation de studio visuel
Gee series: unit 9 generate sampling data in GEE [random sampling]
Fabric. JS activation input box
创新永不止步——nVisual网络可视化平台针对Excel导入的创新历程
Fabric. JS upload local image to canvas background
Pyechats 1.19 generate a web version of Baidu map
Disable access to external entities in XML parsing
Gee: use of common mask functions in remote sensing image processing [updatemask]
指针使用详解
随机推荐
6.网络-基础
Gee dataset: chirps pentad high resolution global grid rainfall dataset
Gee series: unit 7 remote sensing image classification using GEE [random forest classification]
线程池概述
Ubuntu 20.04 installing mysql8
Gee: create a new feature and set corresponding attributes
Nodejs (03) -- custom module
Leetcode 18 problem [sum of four numbers] recursive solution
[technical notes-08]
中小型项目手撸过滤器实现认证与授权
Fabric. JS three methods of changing pictures (including changing pictures in the group and caching)
Gee: use of common mask functions in remote sensing image processing [updatemask]
4. Flask cooperates with a tag to link internal routes
Global and Chinese market of insulin pens 2022-2028: Research Report on technology, participants, trends, market size and share
LeetCode 1175. Prime number arrangement (prime number judgment + Combinatorial Mathematics)
Pyechart1.19 national air quality exhibition
黑馬筆記---Set系列集合
Php/js cookie sharing across domains
Gee series: Unit 5 remote sensing image preprocessing [GEE grid preprocessing]
指针使用详解