above

When I was working on LeetCode, I came across a rare algorithm idea that could be directly used in the front end (to be honest, there are really few scenarios where the front end can be used in the algorithm), so I grabbed it and shared it with you. Coincides with the golden three silver four job hunting season, more than a knowledge point, more than a big factory work hope! Come on, workers!

The body of the

Introduction to the

A common example of caching is when a user visits a different site and the browser needs to cache information for that site so that the next visit to the same site can be made faster (because some of the data can be read directly from the cache). The LRU (Least Recently Used) Cache is one of the most important things that should be deleted first. The LRU (Least Recently Used) Cache should be deleted first. ** This rule is also full of human, frequently visited, must be relatively more important.

Demand analysis

Assuming we want to implement a simplified version of this feature, following the CRUD principles of our back-end colleague next door, we first sort out the requirements:

  1. You need to provideputMethod used to write different cached data, assuming that each piece of data is of the form} {' domain ', 'info', e.g.{'https://segmentfault.com': 'some key information '}(If the same site is repeatedly written, overwrite);
  2. Is called when the cache reaches its maximumputDelete before writing to cacheLeast recently used data;
  3. providegetMethod, which is used to read cached data and move the read data toRecent usage data;
  4. Considering the read performance, hopefullygetThe complexity of the operation isO(1)(Read from the cache without iterating through all data.)

Data selection

First of all, it is obviously mentioned in the title that it is necessary to be able to mark the insertion or use sequence of data. Therefore, it is definitely not possible to simply use object, but to use array or ES6 Map and Set implementation (Map and Set data traversal is orderly, traversal sequence is the insertion sequence).

Secondly, the complexity of O(1) needs to be realized, which cannot be realized by using arrays alone, so only Map and Set can be considered. Then finally, considering the problem of data repeatability, we will find that this scenario does not need to be considered in this problem, so we can use Map first.

Since the nature of maps is that the newly inserted data comes last and the old data comes first, we just have to focus on maintaining this logic:

  • If data needs to be deleted, delete it from the front first, because the first data must be the least frequently used data.
  • If a piece of data is read, the data should be placed at the end to ensure that the data becomes the most recently used data.

Simply use a few diagrams to represent the corresponding scenes:

Insert data when the space is full:

Insert data when space is full:

Read data:

Algorithm implementation

The implementation code can then be implemented step by step, starting with the most basic constructor:

// First step code
class LRUCache {
    constructor(n){
        this.size = n; // Initialize the maximum number of cached data items n
        this.data = new Map(a);// Initialize the cache space map}}Copy the code

Next comes the PUT method, which handles three pieces of logic:

  1. If the domain name to be written already exists in memory, the data is updated and moved to the end.
  2. If the current cache number does not reach the upper limit, write new data directly.
  3. If the current cache size reaches the upper limit, delete the least frequently used data before writing data.

Everything else can be done directly, and the move to the end behavior can be broken down to “delete the data, and then insert the data from the end”, which is much easier. So we continue to update the code:

The code is as follows:

// First step code
class LRUCache {
    constructor(n){
        this.size = n; // Initialize the maximum number of cached data items n
        this.data = new Map(a);// Initialize the cache space map
    }
// Step 2 code
    put(domain, info){
        if(this.data.has(domain)){
            this.data.delete(domain); // Remove data
            this.data.set(domain, info)// Reinsert the data at the end
            return;
        }
        if(this.data.size >= this.size) {
        // Delete the least frequently used data
            const firstKey= this.data.keys().next().value; Size = this.data.size = this.data.size = this.data.size = this.data.size = this.data.size = this.data.size = this.data.size = this.data.size = this.data.size = this.data.size = this.data.size = this.data.size = this.data.size = this.size
            this.data.delete(firstKey);
        }
        this.data.set(domain, info) // Write data}}Copy the code

That leaves just the get method, which also handles two types of logic:

  1. According to the givenkeyIf there is no corresponding information, return false;
  2. If the result of the first step exists, the accessed data is moved to the end;
// First step code
class LRUCache {
    constructor(n){
        this.size = n; // Initialize the maximum number of cached data items n
        this.data = new Map(a);// Initialize the cache space map
    }
// Step 2 code
    put(domain, info){
    if(this.data.size >= this.size) {
        // Delete the least frequently used data
        const firstKey= [...this.data.keys()][0];/ / don't have to be careful data is empty, because of this. The size does not normally take 0, meet this. Data. The size > = this. The size, this. The data is no empty.
        this.data.delete(firstKey);
        }
        this.data.set(domain, info) // Write data
    }

// Step 3 code
    get (domain) {
        if(!this.data.has(domain)){
            return false;
        }
        const info = this.data.get(domain); // Get the result
        this.data.delete(domain); // Remove data
        this.data.set(domain, info); // Add the data again
        returninfo; }}Copy the code

A slight note in this step is that we remove data first and then add data, strictly following the maximum number of n.

summary

Actually the code is over here, is a relatively easy one article, estimates that for about ten minutes slightly see also mastered, of course, careful may notice the classmate, have a () on the words in the title, means that there is a (), because the idea of the main characteristics and advantage of using the Map in the es6 to complete, is a bit tricky. The next article will show you how to handle this scenario using only ES5. Rather, a more formal and generic approach will be presented in the next article

conclusion

Recently, the column’s fans have increased rapidly, and some readers’ feedback has been received one after another. I feel very flattered and happy that my writing has been recognized by everyone. I also hope that you can like and favorites your favorite articles, so that you can give me feedback to a certain extent, which articles are better written, which articles are not enough, or for the writing style and content of any comments, you are welcome to private communication.

Last but not least, RingCentral has set up an office in Hangzhou, and can apply for long-term telecommuting to leave 996. If you are interested, you can send a private letter (contact information is available on the homepage), and you can help to promote for free