LRU 算法分析与简单实现

aristark 发布于2019-08-22 16:46 / 568人阅读

摘要：在上图中，一旦充满所分配的内存块，那么最新出现的将替代最低使用的，访问顺序为。满额时，从链表尾部开始往前删除指定数目的数据，即可解决。

LRU

Discards the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item. General implementations of this technique require keeping "age bits" for cache-lines and track the "Least Recently Used" cache-line based on age-bits. In such an implementation, every time a cache-line is used, the age of all other cache-lines changes.

在上图中，一旦 A B C D 充满所分配的内存块，那么最新出现的 E 将替代最低使用的 A(0)，访问顺序为 A -> B -> C -> D -> E -> D -> F。

原理

这里将会出现一个性能瓶颈，也就是在 Cache 满时，淘汰那些不常用的数据，空出空间存储新的数据。假设每一条数据都有一个最后访问时间，当满额的时候，将要遍历所有元素，才能删除访问时间最小的那个元素，时间复杂度为 $O(1)$，数据量越大,性能越低。

所以选择使用链表，每访问一次数据，把最新的访问数据放至头部，那尾部的数据就是最旧未访问的数据。满额时，从链表尾部开始往前删除指定数目的数据，即可解决。

代码实现

class LruCache {
  constructor(maxsize) {
    this._cache = {}; // 缓存
    this._queue = []; // 队列
    this._maxsize = maxsize; // 最大值

    // 如果最大值输入非法 默认无限大
    if (!this._maxsize || !(typeof this._maxsize === "number") || this._maxsize <= 0) {
      this._maxsize = Infinity;
    }

    // 运行定时器，定时检查过期值
    setInterval(() => {
      this._queue.forEach((el, idx) => {
        const key = el;
        const insertTime = this._cache[key].insertTime;
        const expire = this._cache[key].expire;
        const curTime = +new Date();

        // 如果存在过期时间且超期，移除数据
        if (expire && curTime - insertTime > expire) {
          this._queue.splice(idx--, 1);
          delete this._cache[key];
        }
      });
    }, 1000);
  }

  // 生成唯一索引
  _makeSymbol(key) {
    return Symbol.for(key);
  }

  // 更新队列
  _update(queue, key) {
    // 移除
    queue.forEach((el, idx) => {
      if (el === key) {
        queue.splice(idx, 1);
      }
    });

    // 前置
    queue.unshift(key);
    return queue;
  }

  // 插入数据
  set(key, value, expire) {
    key = this._makeSymbol(key); // 生成唯一索引

    // 如果已经存在该值，则重新赋值
    if (this._cache[key]) {
      this._cache[key] = {
        value,
        expire,
        insertTime: this._cache[key].insertTime
      }
      this._queue = this._update(this._queue, key); // 更新队列
    } else {
      // 如果不存在，则插入
      this._cache[key] = {
        value,
        expire,
        insertTime: +new Date()
      }

      // 索引置前
      this._queue.unshift(key);

      // 超出最大值，截断
      while (this._queue.length > this._maxsize) {
        const item = this._queue.pop(); // 尾截断
        delete this._cache[item]; // 删除
      }
    }
  }

  // 获取数据
  get(key) {
    key = this._makeSymbol(key);

    // 如果存在该值
    if (this._cache[key]) {
      const insertTime = this._cache[key].insertTime; // 插入时间
      const expire = this._cache[key].expire; // 过期时间
      const curTime = +new Date(); // 当前时间

      // 如果不存在过期时间 或 存在过期时间但尚未过期
      if (!expire || (expire && curTime - insertTime < expire)) {
        // 更新队列，前置索引
        this._queue = this._update(this._queue, key);

        return this._cache[key].value;
      } else if (expire && curTime - insertTime > expire) {
        // 已经过期
        this._queue.forEach((el, idx) => {
          if (el === key) {
            this._queue.slice(idx, 1);
            delete this._cache[key];
          }
        })

        return null
      }
    } else {
      return null;
    }
  }
}

同步至我的个人博客：https://blog.trevor.top/item/34

云服务器私有云 lru置换算法c语言 lru用c语言实现算法结构与数据分析数据结构与算法分析

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

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

【Redis源码分析】Redis中的LRU算法实现

摘要：看下边的代码如果配置的是方式，则更新否则按方式更新在的中每次按获取一个值的时候，都会调用函数如果配置使用了模式该函数会更新中的字段为当前秒级别的时间戳方式后文再描述。主要是通过验证的比率，来判断淘汰算法是否有效。作者：张仕华 LRU是什么 LRU(least recently used)是一种缓存置换算法。即在缓存有限的情况下，如果有新的数据需要加载进缓存，则需要将最不可能被继续访问...

Keagan 2019-07-24 16:07 评论0 收藏0
你与解决“缓存污染”只差这篇文章的距离

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

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

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

Tecode 2022-06-28 18:59 评论0 收藏0
Android 内存暴减的秘密？！

摘要：而不同的环境操作路径设备使用习惯等各个因素都有可能导致内存占用的不同。措施主要分析外网用户的使用习惯下，发生的场景。比较容易发现类问题导致瞬间内存占用过多的场景。内存占用在几级别。图片内存主要是用于展示的，也即被持有的部分。作者：杨超，腾讯移动客户端开发工程师商业转载请联系腾讯WeTest获得授权，非商业转载请注明出处。原文链接：http://wetest.qq.com/lab...

tuniutech 2019-06-25 11:52 评论0 收藏0
memcached分布式原理与实现

摘要：哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。平衡性平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。 memcached分布式原理与实现标签（空格分隔）： nosql 0x01 概况 1.1 什么是memcached memcached是一个分布式，开源的数据存储引擎。memcach...

Ververica 2019-08-06 12:27 评论0 收藏0