Vue的缓存算法—LRU算法

elina 发布于2019-08-21 14:30 / 3567人阅读

摘要：最近在看的源码，不得不说的是，的源码十分优雅简洁，下面就来分享下的缓存利用的算法算法。关于算法的具体流程，可以来看下这个，这个可视化过程，模拟了算法进行调度的过程。

最近在看Vue的源码，不得不说的是，Vue的源码十分优雅简洁，下面就来分享下Vue的缓存利用的算法LRU算法。

LRU算法

LRU是Least recently used的简写，主要原理是根据历史访问记录来淘汰数据，说白了就是这个算法认为如果数据被访问过，那么将来被访问的几率也高。其存储结构是一个双链表，最近被访问到的放在双链表的尾部，头部放的就是最早被访问到数据。关于算法的具体流程，可以来看下这个，这个可视化过程，模拟了lru算法进行调度的过程。

缺页数

lru在笔试题中也会经常出现，经常会考到的那就是缺页数，例如页面访问序列为：2,3,2,1,5,2,4,5,3,2,5,2，分配给某个进程3页内存，求其缺页次数。
缺页数可以理解为，内存不满的次数，转到lru来看就是链表中有空节点的次数。下面来走一下整个流程（左为head右为tail）：

2 // 第一次缺页

2 -> 3 // 第二次缺页

3 -> 2 // 第三次缺页

3 -> 2 -> 1

2 -> 1 // 第四次缺页

2 -> 1 -> 5

1 -> 5 -> 2

5 -> 2 // 第五次缺页

5 -> 2 -> 4

2 -> 4 -> 5

4 -> 5 // 第六次缺页

4 -> 5 -> 3

5 -> 3 // 第七次缺页

5 -> 3 -> 2

3 -> 2 -> 5

3 -> 5 -> 2

所以总共有着7次缺页，上面的这个流程也是算法的具体执行流程，可以看出的是当有新的节点进入时，首先会检测内存是否已满，如果满了的话，就先将头给移除，再在尾部添加上这个新节点；假若该节点在链表中存在，那么直接将这个节点拿到头部。下面来看下Vue对这个算法的实现：

vue中的lru

源码时src/cache.js，先来看看其构造函数：

// limit是最大容量
function Cache (limit) {
    this.size = 0;
    this.limit = limit;
    this.head = this.tail = undefined;
    this._keymap = Object.create(null);
}

尤大利用集合_keymap来存储已有的节点，在判断是否存在时，直接读取属性就行，不用在遍历一遍链表，这样降低了在查找过程中的时间复杂度。head代表着头节点，tail代表着尾节点，链表中的节点是这样的：

node {
    value: 键值,
    key: 键名,
    older: 指向前一个节点，head的older指向undefined,
    newer: 指向下一个节点，tail的newer指向undefined
}

来看get方法：

Cache.prototype.get = function (key, returnEntry) {
     var entry = this._keymap[key];
     // 本身没有,则不用调度,直接将新的节点插入到尾部即可
    if (entry === undefined) return;
    // 访问的就是尾部节点,则不需要调度    
    if (entry === this.tail) {
        return returnEntry ? entry : entry.value;
    }
    // 访问的不是尾部节点,需要将被访问节点拿到头部
    if (entry.newer) {
        if (entry === this.head) {
            this.head = entry.newer;
        }
        entry.newer.older = entry.older;
    }
    if (entry.older) {
        entry.older.newer = entry.newer;
    }
    entry.newer = undefined;
    entry.older = this.tail;
    if (this.tail) {
        this.tail.newer = entry;
    }
    this.tail = entry;
    return returnEntry ? entry : entry.value;
 };

get是为了得到链表中是否含有这个节点，假如有这个节点，那么还要对这个节点进行调度，也就是将节点拿到尾部。

// 将链表的头给去除
Cache.prototype.shift = function () {
    var entry = this.head;
    if (entry) {
        this.head = this.head.newer;
        this.head.older = undefined;
        entry.newer = entry.older = undefined;
        this._keymap[entry.key] = undefined;
        this.size--;
    }
    return entry;
};
p.put = function (key, value) {
    var removed;
    var entry = this.get(key, true);
    // 插入的情况,插入到尾部
    if (!entry) {
        // 如果集合已经满了,移除一个,并将其return
        if (this.size === this.limit) {
            removed = this.shift();
        }
        entry = {
            key: key
        };
        this._keymap[key] = entry;
        if (this.tail) {
            this.tail.newer = entry;
            entry.older = this.tail;
        } else {  // 链表中插入第一个节点时，头节点就是尾几点
            this.head = entry;
        }
        this.tail = entry;   // 节点会添加或者拿到尾部
        this.size++;
    }
    // 更新节点的value，假若本身链表中有，get方法中已经调度好，只要更新值就好
    entry.value = value;
    return removed;
};

至此，vue的cache代码已经全部解析完，其具体的作用由于源码刚刚开始读吗，目前还不清楚，不过应该在解析指令等方面有着重大的作用。

最后希望大家关注下算法演示

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/87931.html

web技术分享| LRU 缓存淘汰算法

摘要：双向链表用于管理缓存数据结点的顺序，新增数据和缓存命中最近被访问的数据被放置在结点，尾部的结点根据内存大小进行淘汰。了解 LRU 之前，我们应该了解一下缓存，大家都知道计算机具有缓存内存，可以临时存储最常用的数据，当缓存数据超过一定大小时，系统会进行回收，以便释放出空间来缓存新的数据，但从系统中检索数据的成本...

graf 2021-11-24 09:39 评论0 收藏0
探索vue源码之缓存篇

摘要：中采用算法来实现缓存的高效管理。通过这两个属性，将缓存中的变量连接起来。以上图举例缓存这个对象中保存了三个变量。如果缓存数组为空，则返回将为传入参数的缓存对象标识为最常使用的，即，并调整双向链表，返回改变后的。 vue.js入坑也有了小半年的时间了，圈子里一直流传着其源码优雅、简洁的传说。最近的一次技术分享会，同事分享vue.js源码的缓存部分，鄙人将其整理出来，与大家一起学习一、从...

Forest10 2019-08-20 10:23 评论0 收藏0
你与解决“缓存污染”只差这篇文章的距离

摘要：如果处理不得当，就会造成缓存污染问题。解决缓存污染的算法算法，英文名，字面意思就是最不经常使用的淘汰掉算法，是通过数据被访问的频率来判断一个数据的热点情况。分析降低了缓存污染带来的问题，命中率比要高。微信公众号：IT一刻钟大型现实非严肃主义现场一刻钟与你分享优质技术架构与见闻，做一个有剧情的程序员关注可第一时间了解更多精彩内容，定期有福利相送哟。 showImg(https://s...

shadowbook 2019-08-06 13:41 评论0 收藏0
Redis 缓存淘汰策略

摘要：但是内存空间毕竟有限，随着我们存储数据的不断增长，要缓存的数据量越来越大，当超过了我们的内存大小时，该怎么办呢解决方法有两种增加物理内存搭建集群和缓存数据的淘汰机制。增加物理内存简单粗暴，价格十分昂贵，内存的价格大约是万元左右。redis 使用的时内存空间来存储数据的，避免业务应用从后端数据库中读取数据，可以提升应用的响应速度。但是内存空间毕竟有限，随着我们存储数据的不断增长，要缓存的数据量...

Tecode 2022-06-28 18:59 评论0 收藏0