LRU算法详解

玖柒的小窝

修改于 2021-11-16 17:22:32

6820

修改于 2021-11-16 17:22:32

什么是LRU算法

就是?种缓存淘汰策略。计算机的缓存容量有限，如果缓存满了就要删除?些内容，给新内容腾位置。但问题是，删除哪些内容呢？我们肯定希望删掉哪些没什么?的缓存，?把有?的数据继续留在缓存?，?便之后继续使?。LRU 缓存淘汰算法就是?种常?策略。LRU 的全称是 Least Recently Used，也就是淘汰掉最近最久未使用的缓存。

算法思路

?先要接收?个 capacity 参数作为缓存的最?容量，然后实现两个 API，?个是 put(key, val) ?法存?键值对，另?个是 get(key) ?法获取 key 对应的 val，如果 key 不存在则返回-1。注意哦，get 和 put ?法必须都是 O(1) 的时间复杂度，我们举个具体例?，来看看 LRU 算法怎么?作。

/* 缓存容量为 2 */
const cache = new LRUCache(2);

cache.put(1, 1);
// cache = [{1: 1}]
cache.put(2, 2);
// cache = [{2: 2}, {1: 1}]
cache.get(1); // 返回 1
// cache = [{1: 1}, {2: 2}]
// 解释：因为最近访问了键 1，所以提前?队头
// 返回键 1 对应的值 1
cache.put(3, 3);
// cache = [{3: 3}, {1: 1}]
// 解释：缓存容量已满，需要删除内容空出位置，优先删除久未使?的数据，也就是队尾的数据，然后把新的数据插?队头
cache.get(2); // 返回 -1 (未找到)
// cache = [{3: 3}, {1: 1}]
cache.put(1, 4);
// cache = [{1: 4}, {3: 3}]
// 解释：键 1 已存在，把原始值 1 覆盖为 4
// 不要忘了也要将键值对提前到队头
复制代码

算法设计

分析上?的操作过程，要让 put 和 get ?法的时间复杂度为 O(1)，我们可以总结出 cache 这个数据结构必要的条件：查找快，插?快，删除快，有顺序之分。所以我们不能使用数组去保存缓存，因为数组的查需要O(n)，这里我们选择Map，为什么选择 Map结构，我们来分析一下：可以通过map.keys().next().value来获取第一个的键值，map.set()操作类似数组的push操作，将值保存在最前面的位置，而且删除缓存也可以直接使用delete(key)方法，满足O(1)

代码实现

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
  }
  get(key) {
    let val = this.map.get(key);
    if (typeof val === '?developer/article/1902060/undefined') { return -1 }
    // 重新计算位置
    this.map.delete(key);
    this.map.set(key, val);
    return val
  }
  put(key, val) {
    // 如果已经有这个key值，则更新
    if(this.map.has(key)) {
      this.map.delete(key);
    }
    this.map.set(key, val);
    // 删除超出的key
    let keys = this.map.keys()
    while (this.map.size > this.capacity) { 
      this.map.delete(keys.next().value)
    }
  }
}
复制代码

通过get方法获取缓存的时候，如果命中了，就需要把命中的缓存放到第一个位置。在 put 方法里面，如果缓存超出了容量，通过map.keys.next().value获取到最久未使用的缓存的key，进行删除。

实际运用

在Vue的keep-alive组件中就用了这个算法，我们可以来分析一下keep-alive的原理

export default {
  name: "keep-alive",
  // 抽象组件属性 ,它在组件实例建立父子关系的时候会被忽略,发生在 initLifecycle 的过程中
  abstract: true, 
  props: {
    // 被缓存组件
    include: patternTypes, 
    // 不被缓存组件
    exclude: patternTypes,
    // 指定缓存大小
    max: [String, Number] 
  },
  created() {
    // 初始化用于存储缓存的 cache 对象
    this.cache = Object.create(null);
    // 初始化用于存储VNode key值的 keys 数组
    this.keys = []; 
  },
  destroyed() {
    for (const key in this.cache) {
      // 删除所有缓存
      pruneCacheEntry(this.cache, key, this.keys);
    }
  },
  mounted() {
    // 监听缓存（include）/不缓存（exclude）组件的变化
    // 在变化时，重新调整 cache
    // pruneCache：遍历 cache，如果缓存的节点名称与传入的规则没有匹配上的话，就把这个节点从缓存中移除
    this.$watch("include", val => {
      pruneCache(this, name => matches(val, name));
    });
    this.$watch("exclude", val => {
      pruneCache(this, name => !matches(val, name));
    });
  },
  render() {
    // 获取第一个子元素的 vnode
    const slot = this.$slots.default;
    const vnode: VNode = getFirstComponentChild(slot);
    const componentOptions: ?VNodeComponentOptions =
      vnode && vnode.componentOptions;
    if (componentOptions) {
      // name 不在 inlcude 中或者在 exlude 中则直接返回 vnode，否则继续进行下一步
      // check pattern
      const name: ?string = getComponentName(componentOptions);
      const { include, exclude } = this;
      if (
        // not included
        (include && (!name || !matches(include, name))) ||
        // excluded
        (exclude && name && matches(exclude, name))
      ) {
        return vnode;
      }
      
      const { cache, keys } = this;
      // 获取键，优先获取组件的 name 字段，否则是组件的 tag
      const key: ?string =
        vnode.key == null
          ? // same constructor may get registered as different local components
            // so cid alone is not enough (#3269)
            componentOptions.Ctor.cid +
            (componentOptions.tag ? `::${componentOptions.tag}` : "")
          : vnode.key;
        
      // --------------------------------------------------
      // 下面就是 LRU 算法了，
      // 如果在缓存里有则调整，
      // 没有则放入（长度超过 max，则淘汰最近没有访问的）
      // --------------------------------------------------
      // 如果命中缓存，则从缓存中获取 vnode 的组件实例，并且调整 key 的顺序放入 keys 数组的末尾
      if (cache[key]) {
        vnode.componentInstance = cache[key].componentInstance;
        // make current key freshest
        remove(keys, key);
        keys.push(key);
      }
      // 如果没有命中缓存,就把 vnode 放进缓存
      else {
        cache[key] = vnode;
        keys.push(key);
        // prune oldest entry
        // 如果配置了 max 并且缓存的长度超过了 this.max，还要从缓存中删除第一个
        if (this.max && keys.length > parseInt(this.max)) {
          pruneCacheEntry(cache, keys[0], keys, this._vnode);
        }
      }
      
      // keepAlive标记位
      vnode.data.keepAlive = true;
    }
    return vnode || (slot && slot[0]);
  }
};

// 移除 key 缓存
function pruneCacheEntry (
  cache: VNodeCache,
  key: string,
  keys: Array<string>,
  current?: VNode
) {
  const cached = cache[key]
  if (cached && (!current || cached.tag !== current.tag)) {
    cached.componentInstance.$destroy()
  }
  cache[key] = null
  remove(keys, key)
}

// remove 方法（shared/util.js）
/**
 * Remove an item from an array.
 */
export function remove (arr: Array<any>, item: any): Array<any> | void {
  if (arr.length) {
    const index = arr.indexOf(item)
    if (index > -1) {
      return arr.splice(index, 1)
    }
  }
}

复制代码

在 keep-alive 缓存超过最大时，使用的缓存淘汰算法就是 LRU 算法，它在实现的过程中用到了 cache 对象用于保存缓存的组件实例及 key 值，keys 数组用于保存缓存组件的 key ，当 keep-alive 中渲染一个需要缓存的实例时：