JS 简单实现(FIFO 、LRU、LFU)缓存淘汰算法

更新日期: 2022-02-16阅读: 972标签: 算法

FIFO 、LRU、LFU缓存算法算是比较简单的,它们的区别是当缓存空间满的时候,其对数据淘汰策略不同而已,这里的话我就选择了JavaScript来进行演示FIFO 、LRU、LFU的实现。希望能帮助大家更好的理解。

1. FIFO 算法实现

FIFO (First Input First Output)可以说是最简单的一种缓存算法,通过设置缓存上限,当达到了缓存上限的时候,按照先进先出的策略进行淘汰,再增加进新的 key-value。

实现的可以创建一个map对象来保存键值信息

然后创建keys的数组用来进行淘汰判断

代码示例:

const FIFOCache = function (limit = 10) {
  this.limit = limit
  this.map = {}
  this.keys = []
}

实现get函数其实很简单,通过map返回对应值就行

代码示例:

FIFOCache.prototype.get = function (key) { 
  return this.map[key]
}

在set函数中,先keys长度是否达到限制

没达到限制直接追加

如果达到限制判断key是否已经存在,存在将key删除,否则默认删除keys的第一个数据与对应map中的值

代码示例:

FIFOCache.prototype.set = function (key, value) {
  if (this.keys.length >= this.limit) {
    const i = this.keys.indexOf(key)
    if (i >= 0) { this.keys.splice(i, 1) } else { delete this.map[this.keys.shift()] }
  }
  this.keys.push(key)
  this.map[key] = value
}

2. LRU 算法实现

LRU(Least recently used)算法算是最常见的缓存淘汰算法,根据数据的历史访问记录来进行淘汰数据,其核心思想是如果数据最近被访问过,那么将来被访问的几率也更高

如果你搜索java的LRU实现,很多都是通过LinkedHashMap来实现的。我这里就照着网上搜索的相关原理通过js来实现一下。

这里稍微注意的是淘汰的方向,有的是淘汰数组最前的,有的是淘汰最后的。可最后的效果都差不多,这里的话我就以淘汰首位的数据来举例编写。

开始的代码跟上面的FIFO实现差不多

代码示例:

const LRUCache = function (limit = 2) {
  this.limit = limit
  this.map = {}
  this.keys = []
}

实现get函数一样是通过map返回对应值,不过需要这里多了一个update函数,用来切换key位置,将最新访问的数据置到最后。

代码示例:

LRUCache.prototype.get = function (key) {
  let r = -1
  if (typeof this.map[key] !== 'undefined') {
    r = this.map[key]
    this.update(key)
  }
  return r
}

LRUCache.prototype.update = function (key) {
  const idx = this.keys.indexOf(key)
  if (idx != this.keys.length - 1) {
    // 删除之前位置
    this.keys.splice(idx, 1)
    // 重新插入到最后
    this.keys.push(key)
  }
}

set函数判断map中key是否存在,存在直接修改值并更新key在keys中的位置

如果不存在,判断keys是否已满,满则删除首位数据,然后将最新数据追加到末位

代码示例:

LRUCache.prototype.set = function (key, value) {
  if (typeof key === 'undefined' || typeof value === 'undefined') throw new Error('key or value is undefined')
  if (typeof this.map[key] !== 'undefined') {
    this.update(key)
    this.map[key] = value
  } else {
    // 判断容量是否满
    if (this.keys.length == this.limit) {
      // 淘汰首位
      delete this.map[this.keys[0]]
      this.keys.splice(0, 1)
    }
    // 插入新值
    this.keys.push(key)
    this.map[key] = value
  }
}

以下是通过Map实现代码参考:

const LRUCache = function (capacity) {
  this.cache = new Map()
  this.capacity = capacity
}
LRUCache.prototype.get = function (key) {
  const cache = this.cache
  if (cache.has(key)) {
    const temp = cache.get(key)
    cache.delete(key)
    cache.set(key, temp)
    return temp
  } else {
    return -1
  }
}
LRUCache.prototype.put = function (key, value) {
  const cache = this.cache
  if (cache.has(key)) {
    cache.delete(key)
  } else if (cache.size >= this.capacity) {
    cache.delete(cache.keys().next().value)
  }
  cache.set(key, value)
}

3. LFU 算法实现

LFU(Least Frequently Used ) 也是一种常见的缓存算法。当空间满时,通过访问次数,淘汰问次数最小的数据。

如果访问次数全部一样则默认淘汰最初添加的数据

根据需求,定义一个freqMap用来保存访问频率数据

代码示例:

const LFUCache = function (capacity) {
  this.limit = capacity
  this.map = {}
  this.freqMap = {}
}

get函数跟上面的LRU算法的差不多,不过这里this.map里所保存的对象格式为

{
    value:"value", // 存值
    freq:1//<== 频率
}

代码示例:

LFUCache.prototype.get = function (key) {
  let r = -1
  if (typeof this.map[key] !== 'undefined') {
    const o = this.map[key]
    r = o.value
    // 更新频率记录
    this.updateL(key, o)
  }
  return r
}

所以更新频率的时候通过对象保存的freq字段从频率记录this.freqMap中寻找,删除原始记录后重新追加到新的记录

代码示例:

LFUCache.prototype.updateL = function (key, obj) {
  let freq = obj.freq
  const arr = this.freqMap[freq]
  // 删除原频率记录
  this.freqMap[freq].splice(arr.indexOf(key), 1)
  // 清理
  if (this.freqMap[freq].length == 0) delete this.freqMap[freq]
  // 跟新频率
  freq = obj.freq = obj.freq + 1
  if (!this.freqMap[freq]) this.freqMap[freq] = []
  this.freqMap[freq].push(key)
}

set函数判断逻辑跟LRU的差不多,区别在容量满的时候,默认取freqMap中第一个索引对应的keys数组中第一个key,删除key对应的数据

代码示例:

LFUCache.prototype.set = function (key, value) {
  if (this.limit <= 0) return
  if (typeof key === 'undefined' || typeof value === 'undefined') throw new Error('key or value is undefined')
  // 存在则直接更新
  if (typeof this.map[key] === 'undefined') {
    // 获取频率 key
    // 判断容量是否满
    if (Object.keys(this.map).length == this.limit) {
      const fkeys = Object.keys(this.freqMap)
      const freq = fkeys[0]
      // 获取key集合
      const keys = this.freqMap[freq]
      // 淘汰首位
      delete this.map[keys.shift()]
      // delete this.map[keys[0]];
      // keys.splice(0, 1);
      // 清理
      if (this.freqMap[freq].length == 0) delete this.freqMap[freq]
    }
    // 频率记录是否存在
    if (!this.freqMap[1]) this.freqMap[1] = []
    // 插入新值
    this.freqMap[1].push(key)
    this.map[key] = {
      value: value,
      freq: 1 // 默认的频率
    }
  } else {
    this.map[key].value = value
    // 更新频率记录
    this.updateL(key, this.map[key])
  }
}


链接: https://fly63.com/article/detial/11180

js洗牌算法:javascript数组随机打乱顺序的实现方法

有一个数组,我们需要通过js对数组的元素进行随机排序,然后输出,这其实就是洗牌算法,首页需要从元素中随机取一个和第一元进行交换,然后依次类推,直到最后一个元素。

程序员必须知道的10大基础实用算法及其讲解

程序员必须知道的10大算法:快速排序算法、堆排序算法、归并排序、二分查找算法、BFPRT(线性查找算法)、DFS(深度优先搜索)、BFS(广度优先搜索)、Dijkstra算法、动态规划算法、朴素贝叶斯分类算法

js从数组取出 连续的 数字_实现一维数组中连续数字分成几个连续的数字数组

使用原生js将一维数组中,包含连续的数字分成一个二维数组,这篇文章分2种情况介绍如何实现?1、过滤单个数字;2、包含单个数字。

原生Js获取数组中最长的连续数字序列的方法

给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。

Tracking.js_ js人脸识别前端代码/算法框架

racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。

JS常见算法题目

JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题

RSA算法详解

这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述,RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。

PageRank算法的定义与来源、以及PageRank算法原理

PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。

js算法_js判断一个字符串是否是回文字符串

什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a

js之反转整数算法

将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 ;当尾数为0时候需要进行舍去。解法:转字符串 再转数组进行操作,看到有人用四则运算+遍历反转整数。

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!