LRU Cache Mechanism (Question 146)
The title
Using your data structures, design and implement an LRU (least recently used) caching mechanism. Implement the LRUCache class:
LRUCache(int capacity)The capacity is a positive integercapacityInitialize the LRU cacheint get(int key)If the keywordkeyExists in the cache, returns the value of the keyword, otherwise returns -1.void put(int key, int value)If the keyword already exists, change its data value. If the keyword does not exist, the keyword – value group is inserted. When the cache reaches its maximum capacity, it should delete the longest unused data values before writing new data to make room for new data values.
Advanced: Can you do both in O(1) time?
Example:
Input [" LRUCache ", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2]. [4, 4], [1], [3], [4]] Output [NULL, null, null, 1, null, -1, null, -1, 3, 4] interpretation LRUCache LRUCache = new LRUCache(2); lRUCache.put(1, 1); // Cache is {1=1} lrucache.put (2, 2); // Cache is {1=1, 2=2} lrucache.get (1); // Return 1 lRUCache. Put (3, 3); // This operation invalidates keyword 2, cache is {1=1, 3=3} lrucache.get (2); // Return -1 (not found) lrucache.put (4, 4); // This operation invalidates keyword 1, cache is {4=4, 3=3} lrucache.get (1); // Return -1 (not found) lrucache.get (3); // Return 3 lRUCache. Get (4); / / return 4Copy the codeTip:
1 <= capacity <= 30000 <= key <= 30000 <= value <= 104- Most call
3 * 104timegetandput
link
Leetcode-cn.com/problems/lr…
explain
That one. That one was unexpected.
As with the previous N questions, the author walked into a logical dead end.
It is important to maintain the order of the LRUCache, and to note the longest unused data in the problem. To determine this, you need to understand what it means to use data.
By use, I don’t just mean reading something, but also changing it, creating it.
So this means that we need to put the current data at the top of the queue when searching, modifying, and creating. If we need to delete a piece of data, we can delete it from the end of the queue.
That is, maintain a first-out queue and update the queue every time you perform an operation.
When writing this problem again, I always want to use the array and the object to operate together, this idea is correct, the point is that the order is wrong.
In order to maintain a common data, the author adopts the method of weight allocation to sort an array, the problem also appeared on the weight, weight distribution is uneven, so sorting always has a problem, then looked at other solutions discovered, originally don’t need the weight, you just need to manually maintain an array, also do not need to sort, Just delete and add to the header each time.
The following answers are written by the author after reading, which may conflict with the original answers.
Your own answer
There is no
Better method (object + array)
As mentioned above, array plus object can solve this problem completely. Arrays are used to maintain order and objects are used to store values.
There is just a strange phenomenon here. With ES5 syntax, the last use case fails over time, but the ES6 class succeeds, even though the performance is the last 5%.
Take a look at the ES5 version of the code 👇 :
var LRUCache = function(capacity) { this.capacity = capacity this.obj = {} this.arr = [] }; LRUCache.prototype.get = function(key) { if (this.arr.findIndex(item => item === key) > -1) { this.arr = this.arr.filter(item => item ! == key) this.arr.push(key) return this.obj[key] } else { return -1 } }; LRUCache.prototype.put = function(key, value) { if (this.arr.findIndex(item => item === key) > -1) { this.arr = this.arr.filter(item => item ! == key) this.arr.push(key) this.obj[key] = value } else { this.obj[key] = value this.arr.push(key) if (this.arr.length > this.capacity) this.arr.shift() } };Copy the codeThe code is relatively simple. When we initialize, we create an array, an object, and we need to remember the maximum length of the array, which is capacity.
The get method is simple. First, it looks for the current element in the array, if so, it is killed, inserted into the end of the array, and then obj returns the corresponding value. If there is no current element, return -1.
The put method is a little more complicated and also distinguishes between the current key presence and non-existence:
-
Current key exists
Again, change the key’s position in the array, put it last. And then you just change the value of obj
-
The current key does not exist
If it doesn’t exist, it’s added, you just add the key to the end of the array, and you also need to change the value in obj.
If the array length exceeds the limit, remove the first element from the array. Use the shift method.
The overall logic is relatively simple, but poor performance caused the last use case to fail, now look at ES6 writing 👇 :
class LRUCache { constructor(capacity) { this.capacity = capacity this.arr = new Array(capacity) this.obj = {} } _hasKey(key) { return this.arr.findIndex(item => item === key) > -1 } _deleteKey(key) { this.arr = this.arr.filter(item => item ! == key) } get(key) { if (this._hasKey(key)) { this._deleteKey(key) this.arr.push(key) return this.obj[key] } else { return - 1 } } put(key, value) { if (this._hasKey(key)) { this._deleteKey(key) this.arr.push(key) this.obj[key] = value } else { this.arr.push(key) this.obj[key] = value if (this.arr.length > this.capacity) this.arr.shift() } } }Copy the codeThe overall logic is similar to ES5, except that some common methods, such as _hasKey and _deleteKey, are extracted, reducing some redundant code.
The change was small, but it still passed the use case, although performance was still in the final 5%.
Better Way (Map)
Why is Map a better approach? Because if you use a Map you don’t need to use an array. Because you can’t customize the order of an object’s keys, you need an array to help ensure order. We don’t need to do this in the Map, because the key of the Map is in order, which is the order in which we inserted it.
Since the order is guaranteed, we only need to add, delete, and check the Map, and Map’s own set, DELETE, HAS, get operations can greatly reduce the amount of code, compared to the object + array is also more convenient.
Without further comment, look directly at the code 👇 :
class LRUCache {
constructor(capacity) {
this.capacity = capacity
this.map = new Map()
}
get(key) {
const value = this.map.get(key)
if (value === undefined) return -1
this.map.delete(key)
this.map.set(key, value)
return value
}
put(key, value) {
if (this.map.has(key)) this.map.delete(key)
this.map.set(key, value)
const keys = this.map.keys()
if (this.map.size > this.capacity) this.map.delete(keys.next().value)
}
}
Copy the codeAs you can see, the amount of code is probably about half of what it used to be, but it has a lot of functionality.
The logic is pretty much the same, there’s not much embellishment here, but there’s a little pit here that you need to pay attention to.
Look at the get method, which takes advantage of the Map’s GET method. Get itself is fine, returns a value if it has a key, returns undefined if it doesn’t. That’s perfectly reasonable, but basically there’s a problem with the value that’s passed in here, what if the value is zero?
Direct use:
if (this.map.has(key)) {
...
}
Copy the codeNo, because 0 will be judged false, and I was puzzled for a long time before I thought it over and figured out why.
So the criterion here can only be value === undefined.
That’s all there is to it. It’s like array plus object.
Better approach (two-way linked list)
This approach is even more powerful and logically unbeatable, but it doesn’t perform as well as Map, and the code is more complex to implement.
Let’s talk about the logic of the whole thing, the idea of a two-way list is not much, it was mentioned in the previous article.
Here, we need to first give a header element and a tail element to ensure the smooth linking of the whole list, and also for the convenience of obtaining the header element and the tail element, because the corresponding insertion and deletion operation is required.
However, a bidirectional list is not enough, because the search is not done in the complexity of O(1), so we need another object or Map to directly get the node we need. In the following code, we use the object for convenience, and it is better to use the Map.
Now that you have objects and two-way lists, it’s easy, just like the logic above. Delete the current node and insert it at the top of the list. The same logic applies to modifications: delete + add; To add a new node, insert the new node after the head node and remove the node before the tail node.
Take a look at the code 👇 :
class DoubleLinkedNode { constructor(key, value) { this.key = key this.value = value this.prv = null this.next = null } } class LRUCache { constructor(capacity) { this.capacity = capacity this.hashMap = {} this.headNode = new DoubleLinkedNode(null, null) this.tailNode = new DoubleLinkedNode(null, null) this.headNode.next = this.tailNode this.tailNode.prv = this.headNode } _isFull() { return Object.keys(this.hashMap).length >= this.capacity } _removeNode(node) { node.prv.next = node.next node.next.prv = node.prv delete this.hashMap[node.key] return node } _addHeadNode(node) { node.next = this.headNode.next node.prv = this.headNode this.headNode.next.prv = node this.headNode.next = node this.hashMap[node.key] = node } get(key) { const node = this.hashMap[key] if (node) { this._addHeadNode(this._removeNode(node)) return node.value } else { return -1 } } put(key, value) { const node = this.hashMap[key] if (node) { this._addHeadNode({ ... this._removeNode(node), value }) } else { if (this._isFull()) this._removeNode(this.tailNode.prv) this._addHeadNode(new DoubleLinkedNode(key, value)) } } }Copy the codeWe have a DoubleLinkedNode class to help us generate new nodes.
To avoid redundancy, the _isFull, _removeNode and _addHeadNode methods are extracted for get and PUT to call.
Without going into the details, this is the overall logic, which is similar to Map, but uses a different data format.
PS: To view past articles and titles, click on the link below:
Here’s 👇 by date
Front Brush path – Directory (Date classification)
After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇
Front brush problem path – Catalogue (Question type classification)
Those who are interested can also check out my personal homepage 👇
Here is RZ