在JavaScript中实现简单的LRU缓存

作者 : IT 大叔 本文共3098个字,预计阅读时间需要8分钟 发布时间: 2020-10-15

在担任软件工程师的旅途中,您可能会遇到各种可能的数据结构都有机会发光的实例。特别是其中一种并没有获得其他人那么多的关注,但在某些情况下可能同样有用(如果不是更多的话)。该数据结构是LRU缓存


什么是LRU缓存?

一个LRU缓存,或最近最少使用的高速缓存,是一个数据结构,在顺序存储信息,它最近已经被添加或访问。

一个流行的类比是壁橱中的衣架:当衣服穿起来并挂在后面时,它们就放在衣架的右侧。随着时间的流逝,通过查看机架的左侧,很容易就能判断出较长时间未穿哪些衣服。

我为什么要使用一个?

与其他数据结构相比,使用LRU缓存存储信息的主要优势在于功能的增加。

一个缓存在计算机科学方面可以被认为是存储在内存中的快速访问的位置最近使用的数据,导致当同样的数据被反复拉升更快的性能块。

如果我们考虑使用LRU缓存,则在用户通过数据库搜索信息的应用程序中它可能很有用。通常,每次用户查找内容时,应用程序都会使用请求ping它的数据库,这会花费宝贵的时间。但是,如果我们将最近(或最常见)搜索到的项目存储在LRU缓存中,我们可以快速检查一下搜索到的项目是否存在于缓存中,如果这样,我们可以用更少的时间来检索它。时间!超级有用。

听起来不错,我们如何建立一个?

我很高兴你问!传统上,LRU缓存是通过将哈希映射与双链表组合在一起来构建的,以便维持对项目的快速查找并在恒定的O(1)时间内检索最近使用和最少使用的项目。

但是,如果您感兴趣的是在小型项目中快速地从头开始实现LRU缓存,则仅使用JavaScript类和Map()对象就可以构建一个LRU缓存,而这需要花费运行时的代价。

最少/最近使用过的功能将保持不变,这实际上是数据结构的关键方面。如果您有兴趣学习如何创建此版本的LRU缓存,请继续阅读!


1.建立类和构造函数

我们将使用JavaScript ES6类构建LRU缓存,如下所示:

class LRUCache {

}

在此类中,我们将设置一个构造函数,以便LRU Cache的每个实例都保持相同的结构。我们的缓存将以容量作为参数,这将设置缓存可以增长到的最大大小,然后再从存储中删除最近最少使用的项目,以节省空间并保持结构的有序性。

我们还将使用此构造函数来通过JavaScript Map对象建立缓存本身:

class LRUCache {
  constructor(capacity) {
    this.cache = new Map();
    this.capacity = capacity;
  } 

}

我们在这里使用Map对象的原因是JavaScript Map保持插入键和值的顺序。这为我们完成了大部分工作!

2.构建缓存的Get和Put方法

现在,我们将在该类中实现我们的两个重要功能:GetPut,它们将检索一个值并将键/值对分别插入到缓存中。

让我们从Get开始:

class LRUCache {
  constructor(capacity) {
    this.cache = new Map();
    this.capacity = capacity;
  }

  // Implementing Get method
  get(key) {
    if (!this.cache.has(key)) return undefined;

    let val = this.cache.get(key);

    this.cache.delete(key);
    this.cache.set(key, val);

    return val;
  }

}

让我们分解一下上面所做的事情。

  1. 我们检查密钥是否存在于我们的地图中。如果不是,则返回“ undefined”(这可以是表示检索失败的任何返回值,例如-1或错误消息。)
  2. 接下来,我们声明一个变量“ val”,获取与该键关联的值,并将其分配给该变量。
  3. 我们从缓存中删除该键/值对,然后再次进行设置。由于我们的地图保持了插入顺序,因此将检索到的键/值对放回最前面(最近使用)。
  4. 无论在何处调用此方法,我们都会返回要在程序中使用的值。

这就是Get方法的全部!

现在,我们将实现Put方法:

class LRUCache {
  constructor(capacity) {
    this.cache = new Map();
    this.capacity = capacity;
  }

  get(key) {
    if (!this.cache.has(key)) return -1;

    let val = this.cache.get(key);

    this.cache.delete(key);
    this.cache.set(key, val);

    return val;
  }

  // Implementing Put method
  put(key, value) {
    this.cache.delete(key);

    if (this.cache.size === this.capacity) {
      this.cache.delete(this.cache.keys().next().value);
      this.cache.set(key, value);
    } else {
      this.cache.set(key, value);
    }
  }

}

让我们将其分解为以下步骤:

  1. 第一行检查密钥是否已经存在于地图中,如果存在则将其删除。调用.delete()要么删除键/值对(如果存在),要么返回undefined,否则继续。
  2. 如果我们的缓存当前处于最大容量( cache.size === this.capacity ),则通过使用迭代器对象this.cache.keys().next().value 获取Map的第一个键并将其作为参数传递给,来 删除最近最少使用的键/值对 。然后,我们使用传递给Put方法的参数在缓存中设置新的键/值对。this.cache.delete()
  3. 如果当前我们没有达到最大容量,我们可以像往常一样简单地添加新的键/值对。

还有我们的Set方法!

3.实现getLeastRecent和getMostRecent方法

至此,我们已经创建了LRU缓存的基本功能,但是要拥有完整的数据结构,还需要走一步。我们可能想检索最近最少使用(LRU)或最近最少使用(MRU)的值!

为此,我们将Map转换为数组,然后分别检索数组的第一个(LRU)和最后一个(MRU)值:

class LRUCache {
  constructor(capacity) {
    this.cache = new Map();
    this.capacity = capacity;
  }

  get(key) {
    if (!this.cache.has(key)) return -1;

    let val = this.cache.get(key);

    this.cache.delete(key);
    this.cache.set(key, val);

    return val;
  }

  put(key, value) {
    this.cache.delete(key);

    if (this.cache.size === this.capacity) {
      this.cache.delete(this.cache.keys().next().value);
      this.cache.set(key, value);
    } else {
      this.cache.set(key, value);
    }
  }

  // Implement LRU/MRU retrieval methods
  getLeastRecent() {
    return Array.from(this.cache)[0];
  }

  getMostRecent() {
    return Array.from(this.cache)[this.cache.size - 1];
  }

}

然后我们去了!如果需要,可以使用相同的“从地图排列”概念来查找最近使用次数最少,最近使用次数第三的等等。

那就是我们的LRU缓存!

免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 在JavaScript中实现简单的LRU缓存

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论