Nodejs基于LRU算法实现的缓存处理操作示例

本文实例讲述了Nodejs基于LRU算法实现的缓存处理操作。分享给大家供大家参考,具体如下:

LRU是Least Recently Used的缩写,即最近最少使用页面置换算法,是为虚拟页式存储管理服务的,是根据页面调入内存后的使用情况进行决策了。由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似,因此,LRU算法就是将最近最久未使用的页面予以淘汰。

可以用一个特殊的栈来保存当前正在使用的各个页面的页面号。当一个新的进程访问某页面时,便将该页面号压入栈顶,其他的页面号往栈底移,如果内存不够,则将栈底的页面号移除。这样,栈顶始终是最新被访问的页面的编号,而栈底则是最近最久未访问的页面的页面号。

如输入以下序列时:4,7,0,7,1,0,1,2,1,2,6

结果为:

4
4        7
4        7        0
4        0        7
4        0        7        1
4        7        1        0
4        7        0        1
4        7        0        1        2
4        7        0        2        1
4        7        0        1        2
7        0        1        2        6

适用于Node.js的一个LRU缓存,capacity为缓存容量,为0时构造一般缓存。

function CacheLRU(capacity) {
/* 利用Buffer写的一个LRU缓存,capacity为缓存容量,为0时不限容量。
myCache = new CacheLRU(capacity); //构造缓存
myCache.get(key); //读取名为key的缓存值
myCache.put(key, value); //写入名为key的缓存值
myCache.remove(key); //删除名为key的缓存值
myCache.removeAll(); //清空缓存
myCache.info(); //返回myCache缓存信息
LRU原理:对所有缓存数据的key构建hash链表,当对某一数据进行get或put操作时,将其key提到链表前端(最新)。当进行put数据超出容量时,删除链表尾端(最旧)的缓存数据。
hash链表操作可直接定位key,无需历遍整个hash对象,故读写极快。缓存容量不再影响读写速度。
*/
  this.capacity = capacity || Number.MAX_VALUE;
  this.data = {};
  this.hash = {};
  this.linkedList = {
    length: 0,
    head: null,
    end: null
  }
  if (capacity <= 0) this.capacity = Number.MAX_VALUE;
};
CacheLRU.prototype.get = function(key) {
  key = '_' + key;
  var lruEntry = this.hash[key];
  if (!lruEntry) return;
  refresh(this.linkedList, lruEntry);
  return JSON.parse(this.data[key].toString());
};
CacheLRU.prototype.put = function(key, value) {
  key = '_' + key;
  var lruEntry = this.hash[key];
  if (value === undefined) return this;
  if (!lruEntry) {
    this.hash[key] = {key: key};
    this.linkedList.length += 1;
    lruEntry = this.hash[key];
  }
  refresh(this.linkedList, lruEntry);
  this.data[key] = new Buffer(JSON.stringify(value));
  if (this.linkedList.length > this.capacity) this.remove(this.linkedList.end.key.slice(1));
  return this;
};
CacheLRU.prototype.remove = function(key) {
  key = '_' + key;
  var lruEntry = this.hash[key];
  if (!lruEntry) return this;
  if (lruEntry === this.linkedList.head) this.linkedList.head = lruEntry.p;
  if (lruEntry === this.linkedList.end) this.linkedList.end = lruEntry.n;
  link(lruEntry.n, lruEntry.p);
  delete this.hash[key];
  delete this.data[key];
  this.linkedList.length -= 1;
  return this;
};
CacheLRU.prototype.removeAll = function() {
  this.data = {};
  this.hash = {};
  this.linkedList = {
    length: 0,
    head: null,
    end: null
  }
  return this;
};
CacheLRU.prototype.info = function() {
  var size = 0,
    data = this.linkedList.head;
  while (data){
    size += this.data[data.key].length;
    data = data.p;
  }
  return {
    capacity: this.capacity,
    length: this.linkedList.length,
    size: size
  };
};
// 更新链表,把get或put方法操作的key提到链表head,即表示最新
function refresh(linkedList, entry) {
  if (entry != linkedList.head) {
    if (!linkedList.end) {
      linkedList.end = entry;
    } else if (linkedList.end == entry) {
      linkedList.end = entry.n;
    }
    link(entry.n, entry.p);
    link(entry, linkedList.head);
    linkedList.head = entry;
    linkedList.head.n = null;
  }
}
// 对两个链表对象建立链接,形成一条链
function link(nextEntry, prevEntry) {
  if (nextEntry != prevEntry) {
    if (nextEntry) nextEntry.p = prevEntry;
    if (prevEntry) prevEntry.n = nextEntry;
  }
}
module.exports = CacheLRU;
// test:
/*var user = new CacheLRU(5);
user.put('user1', {name:'admin', age: 30});
user.put('user2', {name:'user', age: 31});
user.put('user3', {name:'guest', age: 32});
user.put('user4', {name:'guest', age: 34});
user.put('user5', {name:'guest', age: 35});
console.log(user.get('user1'));
console.log(user.get('user2'));
console.log(user.get('user3'));
user.put('user6', {name:'guest', age: 36});
console.log(user.info());*/

LRU算法也可以用于一些实际的应用中,如你要做一个浏览器,或类似于淘宝客户端的应用的就要用到这个原理。大家都知道浏览器在浏览网页的时候会把下载的图片临时保存在本机的一个文件夹里,下次再访问时就会,直接从本机临时文件夹里读取。但保存图片的临时文件夹是有一定容量限制的,如果你浏览的网页太多,就会一些你最不常使用的图像删除掉,只保留最近最久使用的一些图片。这时就可以用到LRU算法 了,这时上面算法里的这个特殊的栈就不是保存页面的序号了,而是每个图片的序号或大小;所以上面这个栈的元素都用Object类来表示,这样的话这个栈就可以保存的对像了。

希望本文所述对大家nodejs程序设计有所帮助。

(0)

相关推荐

  • NodeJS中Buffer模块详解

    一,开篇分析 所谓缓冲区Buffer,就是 "临时存贮区" 的意思,是暂时存放输入输出数据的一段内存. JS语言自身只有字符串数据类型,没有二进制数据类型,因此NodeJS提供了一个与String对等的全局构造函数Buffer来提供对二进制数据的操作.除了可以读取文件得到Buffer的实例外,还能够直接构造,例如: 复制代码 代码如下: var buffer = new Buffer([ 0x68, 0x65, 0x6c, 0x6c, 0x6f ]) ; Buffer与字符串类似,除了

  • Js nodeType 属性全面解析

    定义和用法nodeType 属性返回被选节点的节点类型. 语法:elementNode.nodeType 节点编号: 节点名称: 1 Element 2 Attribute 3 Text 4 CDATA Section 5 Entity Reference 6 Entity 7 Processing Instrucion 8 Comment 9 Document 10 Document Type 11 Document Fragment 12 Notation

  • nodejs文件操作模块FS(File System)常用函数简明总结

    件系统操作相关的函数挺多的.首先可以分为两大类. 一类是异步+回调的. 一类是同步的. 在这里只对异步的进行整理,同步的只需要在函数名称后面加上Sync即可 1. 首先是一类最常规的读写函数,函数名称和形式,应该是起源于C语言的. 复制代码 代码如下: fs.open(文件路径,读写标识,[文件mode值,666],回调函数(err,文件句柄fd));          fs.read(文件句柄fd,被写入的buffer,offset,length,position,回调函数(err, byte

  • nodejs搭建本地http服务器教程

    由于不做php相关的东西,懒得装apache,干脆利用nodejs搭建一个本地的服务器用于测试. nodejs这玩意儿吧,对做前端的介入后端简直就是一把利器.而且目前,nodejs也越来越有商用价值. nodejs其实是非常底层的,从功能上说,它既是apache也是php.像搭建http服务器这种功能,本来是apache已经封装好的,但nodejs需要我们手动来搭建.其实在实际应用中,我们可以使用现成的框架.但这里,我想手动搭建,也加深一下对http服务器的理解. 我们node执行下面这个文件,

  • 用Node.js通过sitemap.xml批量抓取美女图片

    之前看了很多个版本,自己也搞一个. 1. 支持指定保存到哪个目录 2. 按文章进行分目录存放 3. 支持设置并行下载上限 下次有空再搞个整站下载的. package.json { "name": "me2sex-images", "version": "0.0.1", "description": "Batch download images from http://me2-sex.lofter.

  • 基于node.js依赖express解析post请求四种数据格式

    node.js依赖express解析post请求四种数据格式 分别是这四种: www-form-urlencoded form-data application/json text/xml 1.www-form-urlencoded 这是http的post请求默认的数据格式,需要body-parser中间件的支持 服务器端的demo: var express = require('express'); var app = express(); var bodyParser = require('

  • 实例分析nodejs模块xml2js解析xml过程中遇到的坑

    本文实例讲述了nodejs模块xml2js解析xml过程中遇到的坑.分享给大家供大家参考,具体如下: 在一个项目中,用到nodejs模块xml2js解析xml,xml的数据如下: <xml> <MsgId>6197906553041859764</MsgId> </xml> 用xml2js中的xml2js.parseString 方法解析,本来以为是一个json,但总是解析失败,把解析的结果log下后如下: { xml: { MsgId: [ '619790

  • nodejs中全局变量的实例解析

    1.global 类似于客户端javascript运行环境中的window module1.js: module.exports={}; //耻辱的使用了全局变量 global.varA = "abc"; 关于global对象,实际使用中可以省去global. 他是默认的根作用域,相当于web环境中的window对象. global 对象有几个挺有用的属性: console.log(__dirname);//当前路径 console.log(__filename);//当前在执行的js

  • NodeJS学习笔记之Http模块

    一,开篇分析 首先"Http"这个概念大家应该比较熟悉了,它不是基于特定语言的,是一个通用的应用层协议,不同语言有不同的实现细节,但是万变不离其宗,思想是相同的, NodeJS作为一个宿主运行环境,以JavaScript为宿主语言,它也有自己实现的一套标准,这篇文章我们就一起来学习一下 "Http模块" .但是作为前提来说, 希望大家可以先阅读一下官网提供的api,有一个前置了解,这样就方便多了,以下是Http部分的api概览: 复制代码 代码如下: HTTP   

  • NodeJS学习笔记之FS文件模块

    一,开篇分析 文件系统模块是一个简单包装的标准 POSIX 文件 I/O 操作方法集.可以通过调用 require("fs") 来获取该模块.文件系统模块中的所有方法均有异步和同步版本. (1),文件系统模块中的异步方法需要一个完成时的回调函数作为最后一个传入形参. (2),回调函数的构成由调用的异步方法所决定,通常情况下回调函数的第一个形参为返回的错误信息. (3),如果异步操作执行正确并返回,该错误形参则为null或者undefined.如果使用的是同步版本的操作方法,一旦出现错误

  • nodejs实例解析(输出hello world)

    下面将带领大家一步步学习nodejs,知道怎么使用nodejs搭建服务器,响应get/post请求,连接数据库等. 搭建服务器页面输出hello world var http = require('http'); http.createServer(function (request, response) { response.writeHead(200, {'Content-Type': 'text/html; charset=utf-8'}); if(request.url!=="/favi

  • nodejs中模块定义实例详解

    本文实例讲述了nodejs中模块定义方法.分享给大家供大家参考,具体如下: 1.模块定义 nodejs所谓的模块就是一个文件!一个.js文件就是一个nodejs的模块,模块与文件是一一对应的,那么引用模块就是require('文件路径'). 如: var circle = require('./circle.js'); console.log( 'The area of a circle of radius 4 is ' + circle.area(4)); 这个取名为foo.js var PI

随机推荐