vue的keep-alive算法实现——LRU

时间:2020-9-7 作者:admin

keep-alive是什么?

概念

当做组件切换时,可以使用keep-alive将组件包裹起来,可以起到保持这些组件的状态,以避免反复重渲染导致的性能问题。

<!-- 基本使用 -->
<keep-alive>
  <component :is="view"></component>
</keep-alive>

简单一句话: keep-alive是做组件缓存用的,可以避免组件反复渲染。

基本属性

属性名 类型 作用
include 字符串或正则表达式 只有名称匹配的组件会被缓存
exclude 字符串或正则表达式 任何名称匹配的组件都不会被缓存
max 数字 最多可以缓存多少组件实例
<keep-alive :max=10 :include="['a', 'b']">
    <component :is="view"></component>
</keep-alive>

原理(LRU算法)

什么是LRU?

LRU:Least Recently Used,最近最少使用,主要应用场景是缓存。

  • 最近被使用或访问的数据放置在最前面;
  • 每当缓存命中(即缓存数据被访问),则将数据移到头部;
  • 当缓存数量达到最大值时,将最近最少访问的数据剔除;

关键点

  • 一个最大容量,两个api;
    • max: 即keep-alive中的max;
    • get:获取到缓存数据
    • put: 往缓存中添加数据
  • 缓存一个最重要的原则,快,所以其操作要是o(1)的时间复杂度;
  • 上次访问的元素在第一个;

算法实现LRU

思路

//设置缓存容量max/*缓存容量*/
LRUCache cache = new LRUCache(2);
//最近使用的排在队头,很久未使用的排在队尾;
cache.put(key1,value1);
// cache: [(key1,value1)]
cache.put(key2,value2);
// cache: [(key2,value2), (key1,value1)]
cache.get(key1) //返回value1
// 此时cache变为: [(key1,value1), (key2,value2)]
cache.put(key3,value3);
//此时容量已满,将key2移除,cache变为:  [(key3,value3), (key1,value1)]
cache.get(key2)  // -1获取不到这个值了
cache.put(key1,value4); 
// 此时cache变为:  [(key1,value4), (key3,value3)]   //key1已存在,将原始值覆盖,同时提key1键值对到最前面

怎么实现?

要实现查找快并且有序,怎么实现呢? map? map是无序的,并不能满足需求,可以采用:

双向链表 + 散列表 的方式实现

上代码

//定义节点类
class Node {
    constructor(pre, next, value, key){
        this.pre = pre;
        this.next = next;
        this.value = value;
        this.key = key;
    }
}

//定义双向链表
class DoubleList {
    constructor(head, tail){
        this.head = head;
        this.tail = tail;
    }
}


class LRUCache {
    //构造函数,传入缓存容量
    constructor(max){
        this.max = max;
        this.map = new Map();
        let node = new Node(null, null, null, null);
        this.doubleList = new DoubleList(node, node);
    }

    /**
     * 获取缓存值
     * 不存在返回-1,存在返回对应value值,并将此节点移到尾巴
     * @param {*} key  key值
     */
    get(key){
        let node = this.map.get(key)
        if(!node){
            return -1;
        }else{
            this.moveNode2Tail(key, node);
            return node.value;
        }
    }

    /**
     * 插入缓存
     * 1.不存在对应key值,加到尾巴
     * 2.存在对应key值,更新此key值对应value并提到尾巴
     * 3.超出容量的话,去掉头部数据
     * @param {*} key  key值
     * @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;          
        }
    }

    //将节点移到尾巴
    moveNode2Tail(key,node){   
        if(!node.next){
            return;
        }
        //删除节点   
        node.pre.next = node.next;
        node.next.pre = node.pre;
        this.map.delete(key)
        //新增尾巴节点
        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);
    }
}

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。