Vue’s keep-alive algorithm implementation — LRU

What is keep-alive?

concept

When switching between components, components can be wrapped with keep-alive to keep them in state to avoid performance problems caused by repeated rerendering.

<! Basic usage --><keep-alive>
  <component :is="view"></component>
</keep-alive>
Copy the code

Keep-alive is used to cache components and avoid repeated rendering of components.

Basic attributes

<keep-alive :max=10 :include="['a', 'b']">
    <component :is="view"></component>
</keep-alive>
Copy the code

Principle (LRU algorithm)

What is LRU?

LRU: Least Recently Used. It is mainly Used for caching.

• The most recently used or accessed data is placed first;
• Whenever a cache hit (that is, cached data is accessed), the data is moved to the header;
• When the number of caches reaches the maximum, the least recently accessed data is removed.

The key point

• One maximum capacity, two apis;
  • Max: Max in keep-alive;
  • Get: cache data is obtained
  • Put: Adds data to the cache
• Caching is one of the most important principles, fast, so its operation is o(1) time complexity;
• The last accessed element is in the first;

The algorithm implements LRU

Train of thought

// Set the cache capacity Max /* Cache capacity */
LRUCache cache = new LRUCache(2);
// The recently used ones go to the head of the queue, the ones that have not been used for a long time go to the bottom of the queue;
cache.put(key1,value1);
// cache: [(key1,value1)]
cache.put(key2,value2);
// cache: [(key2,value2), (key1,value1)]
cache.get(key1) / / return value1
[(key1,value1), (key2,value2)]
cache.put(key3,value3);
[(key3,value3), (key1,value1)]
cache.get(key2)  // -1 can't get this value
cache.put(key1,value4); 
[(key1,value4), (key3,value3)] [(key1,value4), (key3,value3)
Copy the code

How do you do that?

To achieve fast and orderly search, how to achieve it? The map? Map is unordered and does not meet requirements. You can use:

Two-way linked list + hash list way to achieve

In the code

// Define the node class
class Node {
    constructor(pre, next, value, key){
        this.pre = pre;
        this.next = next;
        this.value = value;
        this.key = key; }}// Define a bidirectional list
class DoubleList {
    constructor(head, tail){
        this.head = head;
        this.tail = tail; }}class LRUCache {
    // Constructor, passing in the cache capacity
    constructor(max){
        this.max = max;
        this.map = new Map(a);let node = new Node(null.null.null.null);
        this.doubleList = new DoubleList(node, node);
    }
    
    /** * returns -1 if no value exists, and moves this object to tail *@param {*} Key the key value * /
    get(key){
        let node = this.map.get(key)
        if(! node){return -1;
        }else{
            this.moveNode2Tail(key, node);
            returnnode.value; }}/** * insert cache * 1. No corresponding key exists, add to tail * 2. There is a corresponding key value, update this key value corresponding to value and mention tail * 3. If the capacity exceeds, remove the header data *@param {*} * the key key values@param {*} value  value
     */
    put(key, value) {
        let node = this.map.get(key);
        if(node){
            if(! node.next){ node.value = value;return;
            }
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        let newNode = new Node(null.null, value, key);
        newNode.pre = this.doubleList.tail;
        this.doubleList.tail.next = newNode;
        this.doubleList.tail = newNode;
        this.map.set(key, newNode);
        if(this.map.size > this.max){
            this.map.delete(this.doubleList.head.next.key);
            this.doubleList.head.next = this.doubleList.head.next.next;
            this.doubleList.head.next.pre = this.doubleList.head; }}// Move the node to the tail
    moveNode2Tail(key,node){   
        if(! node.next){return;
        }
        // Delete a node
        node.pre.next = node.next;
        node.next.pre = node.pre;
        this.map.delete(key)
        // Add a tail node
        let newNode = new Node(null.null, node.value, key);
        newNode.pre = this.doubleList.tail;
        this.doubleList.tail.next = newNode;
        this.doubleList.tail = newNode;
        this.map.set(key, newNode); }}Copy the code