What is LRU?

Caching is everywhere on computer networks. For example, when we first visit a web page, it opens slowly, but when we open it again, it opens quickly.

This involves an application cached on the browser: the browser cache. When we open a web page, it will check the browser cache to see if there is a file to request before making an actual web request. If there is, the browser will intercept the request, return the cached file, and terminate the request without going to the server to download it again. If it does not exist, the request will be made to the server.

In fact, the browser cache is a local copy of resources, its size is limited, when we request too many, the cache space will be used up, at this point, continue to make network requests need to determine which data in the cache to be retained and which data to be removed, this is the browser cache elimination strategy. The most common elimination strategies are FIFO (first-in, first-out), LFU (least used), and LRU (least recently used).

LRU stands for Least Recently Used. It is a common page replacement algorithm that selects the pages that have not been Used for the most recent time to eliminate the page.

The title

Using your knowledge of data structures, design and implement an LRU (least recently used) caching mechanism. Implement the LRUCache class:

  • LRUCache(int capacity) The LRU cache is initialized using a positive integer as capacity
  • Int get(int key) Returns the value of the key if it exists in the cache, otherwise -1 is returned.
  • Void put(int key, int value) If the keyword already exists, change its data value. If the keyword does not exist, the set of keyword – values is inserted. When the cache reaches its maximum capacity, it should delete the oldest unused data values before writing new data to make room for new data values.

Advanced: Can you do both in O(1) time?

The sample

  1. 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]]

  1. Output: [NULL, NULL, NULL, 1, NULL, -1, NULL, -1, 3, 4]

explain

  • 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); / / returns 1
  • lRUCache.put(3, 3); {1=1, 3=3}
  • lRUCache.get(2); // return -1 (not found)
  • lRUCache.put(4, 4); {4=4, 3=3}
  • lRUCache.get(1); // return -1 (not found)
  • lRUCache.get(3); / / return 3
  • lRUCache.get(4); / / return 4

AC code

  1. Array + object implementation
var LRUCache = function(capacity) {
    this.keys = []
    this.cache = Object.create(null)
    this.capacity = capacity
};

LRUCache.prototype.get = function(key) {
    if(this.cache[key]) {
        // Adjust the position
        remove(this.keys, key)
        this.keys.push(key)
        return this.cache[key]
    }
    return -1
};

LRUCache.prototype.put = function(key, value) {
    if(this.cache[key]) {
        // Existing is updated
        this.cache[key] = value
        remove(this.keys, key)
        this.keys.push(key)
    } else {
        // Join if it does not exist
        this.keys.push(key)
        this.cache[key] = value
        // Determine whether the cache has exceeded the maximum value
        if(this.keys.length > this.capacity) {
            removeCache(this.cache, this.keys, this.keys[0])}}};/ / remove the key
function remove(arr, key) {
    if (arr.length) {
        const index = arr.indexOf(key)
        if (index > -1) {
            return arr.splice(index, 1)}}}// Remove the key from the cache
function removeCache(cache, keys, key) {
    cache[key] = null
    remove(keys, key)
}

Copy the code
  1. Map: Using Map, you can save key-value pairs and remember the original insertion order of keys
/ * * *@param {number} capacity* /
var LRUCache = function(capacity) {
    this.cache = new Map(a)this.capacity = capacity
};

/ * * *@param {number} key
 * @return {number}* /
LRUCache.prototype.get = function(key) {
    if (this.cache.has(key)) {
        // Existing is updated
        let temp = this.cache.get(key)
        this.cache.delete(key)
        this.cache.set(key, temp)
        return temp
    }
    return -1
};

/ * * *@param {number} key 
 * @param {number} value
 * @return {void}* /
LRUCache.prototype.put = function(key, value) {
     if (this.cache.has(key)) {
        // Update as existing (delete after added)
        this.cache.delete(key)
     } else if (this.cache.size >= this.capacity) {
        // Join if it does not exist
        // If the cache exceeds the maximum value, remove the recently unused cache
        this.cache.delete(this.cache.keys().next().value)
     }
    this.cache.set(key, value)
};
Copy the code

146. LRU caching mechanism

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to view the details of the campaign: juejin.cn/post/693314…