preface
Bigsai reprint please place the author and the original (article) link
Hello everyone, I am Bigsai, long time no see, very miss!
Recently, a friend of mine complained to me that he had not met LRU. He said that he knew that LRU had been asked for a long time ago, but he thought that he would not meet LRU, so he did not prepare for it for the time being.
Unfortunately, this is really tested! His mood can be illustrated by a picture:
He said he ended up stumbling on an LRU that wasn’t very efficient, and the interviewers weren’t very happy with it… And then it did.
Prevent later run into the pit, and threw on the pit with everyone, today the problem is I’ve just started itself is relatively ordinary way, but a good way though not very hard but want to really long time to think of, although don’t spend too much time, finally I want to come out, the process to share (only from the perspective of the algorithm, Not from an operating system perspective).
Understand the LRU
To design an LRU, you have to know what an LRU is, right?
LRU, English full name Least Recently Used, translated as the most Recently not Used algorithm, is a commonly Used page replacement algorithm.
Speaking of page replacement algorithm, this is related to the OS, we all know that memory speed is relatively fast, but the memory capacity is very limited, it is impossible to put all pages in memory, so we need a strategy to put commonly used pages in memory.
However, no one knows which memory the process will access next, and it’s not very efficient to know (we don’t have the ability to predict the future at this point), As a result, some page replacement algorithms are idealized but impossible to implement (Optimal, yes), and the most common must-return algorithms are FIFO and LRU(most recently unused).
LRU maintains a container of fixed size. The core operations are get() and PUT ().
Let’s first look at the two operations that LRU will have:
Initialization: LRUCache(int capacity). Capacity is a positive integer to initialize the LRU cache.
Query: get(int key), from the own design of the data structure to find whether there is a value corresponding to the current key, if there is then return the corresponding value and record the key update as recent use, if not return -1.
Insert/update: put(int key,int value), either insert a key-value or update a key-value. If the key-value already exists in the container, only the corresponding value needs to be updated and marked as the latest value. If the container does not have the value, consider whether the container is full and delete the oldest unused pair of key-values first.
I can give you an example of the process here, for example
Capacity size is 2: [ "put", "put", "get", "put","get", "put","get","get","get"] [ [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]Copy the codeThe process is as follows:
Details that people tend to overlook include:
- Put () updates the operation. For example,put(3, 3),put(3,4) updates the operation whose key is 3.
- Get () may not be queried, but it will also update the oldest unused order.
- If the container is not full, put may update or insert, but not delete; If the container is full and put inserts, consider removing the oldest unused key-value.
What should we do with the above rule?
If we just use a List like List, we can store the key-value pairs sequentially, with the one before the List (0 subscript is first) being considered older and the one after the List considered newer. Let’s consider the possible design of various operations:
If get operation:
Check whether there is a key/value pair for the key. If there is a value for the key, return -1.
If we put:
If there is a key-value pair for the key, delete the key-value and insert the key-value pair at the end of the List.
If there is no corresponding key and the List container is already full, delete the key-value in the first position.
A List may require two (one for keys and one for values), or a List for nodes (keys and values are attributes). Consider the time complexity:
Put: O(n), get: O(n) both require enumeration of linear complexity.
Hash initial optimization
From the above analysis, we can write the LRU confidently, but now we need to consider an optimization matter.
If we introduce hash tables into our program, there will be some optimization. If a hash table is used to store key-values, the operation to query whether there is a key-value can be optimized to O(1), but the complexity of deleting or inserting or updating a location may still be O(n). Let’s analyze:
The longest unused sequence must be stored in an ordered sequence, either a sequential list (array) or a linked list, if the ArrayList is an array implementation that stores the longest unused sequence.
If the ArrayList deletes the oldest unused key-value (the first key-value), the new key is hit and becomes the latest used (delete first and insert last) operation is O(n).
Similarly, some operations on LinkedList are mostly O(n), like deleting the first element because of the data structure O(1).
You may find that your room for optimization is very, very small, but you have made progress. However, you are stuck and don’t know how to optimize the operation of double O(1). Here I put this version of the code for your reference (if you are asked in the interview, you can write this).
class LRUCache {
Map<Integer,Integer>map=new HashMap<>();
List<Integer>list=new ArrayList<>();
int maxSize;
public LRUCache(int capacity) {
maxSize=capacity;
}
public int get(int key) {
if(! map.containsKey(key))// There is no return -1
return -1;
int val=map.get(key);
put(key,val);// It is important to update the location to be up to date!
return val;
}
public void put(int key, int value) {
// If the key exists, update it directly
if (map.containsKey(key)) {
list.remove((Integer) key);
list.add(key);
} else {// If there is none, insert the last one, but if the capacity is full, delete the first one.
if(! map.containsKey(key)) {if (list.size() == maxSize) {
map.remove(list.get(0));
list.remove(0); } list.add(key); } } map.put(key, value); }}Copy the codeHash + double linked list
We already know that using hash can directly check whether there is this element, but it is difficult to delete! It’s hard to use a List.
In more detail, Map insertion is efficient because of List deletion.
In this case, we want to be able to delete any element in the List quickly and efficiently. If we use hash, we can only locate the element, but cannot delete it. What to do?
Hash + double linked list!
We store key-val’s data in a Node class, and then each Node knows the left and right nodes and stores them directly in the Map when inserting the linked list, so that the Map can directly return the Node when querying, and the double-linked list knows the right and right nodes and can directly delete the Node from the double-linked list.
Of course, for the sake of efficiency, the implementation of a double-linked list is the head node (the head pointer points to an empty node to prevent exceptions such as deletion) and the tail pointer.
In this case, you need to be able to write linked lists and double-linked lists by hand. The double-linked lists have been added, deleted, and checked clearly.
Singly linked lists: mp.weixin.qq.com/s/Cq98GmXt6…
Double linked list: mp.weixin.qq.com/s/h6s7lXt5G…
You can use HashMap to get nodes in a double-linked list directly, and then delete them based on the relationship between the nodes, including some special cases such as null and tail pointer deletion.
The specific implementation code is:
class LRUCache {
class Node {
int key;
int value;
Node pre;
Node next;
public Node(a) {}public Node( int key,int value) {
this.key = key;
this.value=value; }}class DoubleList{
private Node head;/ / head node
private Node tail;/ / end nodes
private int length;
public DoubleList(a) {
head = new Node(-1, -1);
tail = head;
length = 0;
}
void add(Node teamNode)// The tail node is inserted by default
{
tail.next = teamNode;
teamNode.pre=tail;
tail = teamNode;
length++;
}
void deleteFirst(a){
if(head.next==null)
return;
if(head.next==tail)// If the object to be deleted happens to be tail, notice that the tail pointer is moved before it
tail=head;
head.next=head.next.next;
if(head.next! =null)
head.next.pre=head;
length--;
}
void deleteNode(Node team){
team.pre.next=team.next;
if(team.next! =null)
team.next.pre=team.pre;
if(team==tail)
tail=tail.pre;
team.pre=null;
team.next=null;
length--;
}
public String toString(a) {
Node team = head.next;
String vaString = "len:"+length+"";
while(team ! =null) {
vaString +="key:"+team.key+" val:"+ team.value + "";
team = team.next;
}
return vaString;
}
}
Map<Integer,Node> map=new HashMap<>();
DoubleList doubleList;// Store the sequence
int maxSize;
LinkedList<Integer>list2=new LinkedList<>();
public LRUCache(int capacity) {
doubleList=new DoubleList();
maxSize=capacity;
}
public void print(a){
System.out.print("maplen:"+map.keySet().size()+"");
for(Integer in:map.keySet()){
System.out.print("key:"+in+" val:"+map.get(in).value+"");
}
System.out.print("");
System.out.println("listLen:"+doubleList.length+""+doubleList.toString()+" maxSize:"+maxSize);
}
public int get(int key) {
int val;
if(! map.containsKey(key))return -1;
val=map.get(key).value;
Node team=map.get(key);
doubleList.deleteNode(team);
doubleList.add(team);
return val;
}
public void put(int key, int value) {
if(map.containsKey(key)){// You already have this key. Delete it and update it regardless of its length
Node deleteNode=map.get(key);
doubleList.deleteNode(deleteNode);
}
else if(doubleList.length==maxSize){// Does not contain and the length is less than
Node first=doubleList.head.next;
map.remove(first.key);
doubleList.deleteFirst();
}
Node node=newNode(key,value); doubleList.add(node); map.put(key,node); }}Copy the codeSo, an LRU with O(1) complexity for get and put!
The end of the
After looking at the solution, I found that the LinkedHashMap in Java is similar to this data structure! A few lines, but the interviewer may not agree, will still want you to hand write a double linked list.
class LRUCache extends LinkedHashMap<Integer.Integer>{
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75 F.true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
returnsize() > capacity; }}Copy the codeHash + double linked list although not see the problem solution to come out, but it really took a long time to think of this point, before you really see less efficient handwriting LRU to today is really really fully grasp!
However, in addition to LRU, other page replacement algorithm whether written or interview is also very high frequency ah, we have time to comb oh.
Personal technical public number: Bigsai, regularly share, welcome to punch force buckle, learning and communication!