JavaScript版的TwoQueues缓存模型
本文所指TwoQueues缓存模型,是说数据在内存中的缓存模型。
无论何种语言,都可能需要把一部分数据放在内存中,避免重复运算、读取。最常见的场景就是JQuery选择器,有些Dom元素的选取是非常耗时的,我们希望能把这些数据缓存起来,不必每次调用都去重新遍历Dom树。
存就存吧,但总得有个量吧!总不能把所有的历史数据都放在内存中,毕竟目前内存的容量还是相当可怜的,就算内存够大,理论上每个线程分配的内存也是有限制的。
那么问题来了,如何才能高效的把真正有用的数据缓存起来呢?这就涉及到淘汰算法,需要把垃圾数据淘汰掉,才能保住有用的数据。
比较常用的思路有以下几种:
FIFO:就是一个先进先出的队列,最先缓存的数据,最早被淘汰,著名的JQuery框架内部就是用的这种模型。
LRU:双链表结构,每次有新数据存入,直接放在链表头;每次被访问的数据,也转移到链表头,这样一来,链表尾部的数据即是最近没被使用过的,淘汰之。
TwoQueues:FIFO+LRU,FIFO主要存放初次存入的数据,LRU中存放至少使用过两次的热点数据,此算法命中率高,适应性强,复杂度低。
其他淘汰算法还有很多很多,但实际用的比较多的也就这两种。因为他们本身算法不复杂,容易实现,执行效率高,缓存的命中率在大多数场合也还可以接受。毕竟缓存算法也是需要消耗CPU的,如果太过复杂,虽然命中率有所提高,但得不偿失。试想一下,如果从缓存中取数据,比从原始位置取还消耗时间,要缓存何用?
具体理论就不多说了,网上有的是,我也不怎么懂,今天给大家分享的是JavaScript版的TwoQueues缓存模型。
还是先说说使用方法,很简单。
基本使用方法如下:
[/code]
vartq=initTwoQueues(10);
tq.set("key","value");
tq.get("key");
[/code]
初始化的时候,指定一下缓存容量即可。需要注意的是,由于内部采用FIFO+LRU实现,所以实际容量是指定容量的两倍,上例指定的是10个(键值对),实际上可以存放20个。
容量大小需要根据实际应用场景而定,太小命中率低,太大效率低,物极必反,需要自己衡量。
在开发过程中,为了审查缓存效果如何,可以将缓存池初始化成开发版:
vartq=initTwoQueues(10,true);
tq.hitRatio();
就是在后边加一个参数,直接true就可以了。这样初始化的缓存池,会自动统计命中率,可以通过hitRatio方法获取命中率。如果不加这个参数,hitRatio方法获取的命中率永远为0。
统计命中率肯定要消耗资源,所以生产环境下不建议开启。
是时候分享代码了:
(function(exports){
/**
*继承用的纯净类
*@constructor
*/
functionFn(){}
Fn.prototype=Elimination.prototype;
/**
*基于链表的缓存淘汰算法父类
*@parammaxLength缓存容量
*@constructor
*/
functionElimination(maxLength){
this.container={};
this.length=0;
this.maxLength=maxLength||30;
this.linkHead=this.buildNode("","");
this.linkHead.head=true;
this.linkTail=this.buildNode("","");
this.linkTail.tail=true;
this.linkHead.next=this.linkTail;
this.linkTail.prev=this.linkHead;
}
Elimination.prototype.get=function(key){
thrownewError("Thismethodmustbeoverride!");
};
Elimination.prototype.set=function(key,value){
thrownewError("Thismethodmustbeoverride!");
};
/**
*创建链表中的节点
*@paramdata节点包含的数据,即缓存数据值
*@paramkey节点的唯一标示符,即缓存的键
*@returns{{}}
*/
Elimination.prototype.buildNode=function(data,key){
varnode={};
node.data=data;
node.key=key;
node.use=0;
returnnode;
};
/**
*从链表头弹出一个节点
*@returns{*}
*/
Elimination.prototype.shift=function(){
varnode=null;
if(!this.linkHead.next.tail){
node=this.linkHead.next;
this.linkHead.next=node.next;
node.next.prev=this.linkHead;
deletethis.container[node.key];
this.length--;
}
returnnode;
};
/**
*从链表头插入一个节点
*@paramnode节点对象
*@returns{*}
*/
Elimination.prototype.unshift=function(node){
node.next=this.linkHead.next;
this.linkHead.next.prev=node;
this.linkHead.next=node;
node.prev=this.linkHead;
this.container[node.key]=node;
this.length++;
returnnode;
};
/**
*从链表尾插入一个节点
*@paramnode节点对象
*@returns{*}
*/
Elimination.prototype.append=function(node){
this.linkTail.prev.next=node;
node.prev=this.linkTail.prev;
node.next=this.linkTail;
this.linkTail.prev=node;
this.container[node.key]=node;
this.length++;
returnnode;
};
/**
*从链表尾弹出一个节点
*@returns{*}
*/
Elimination.prototype.pop=function(){
varnode=null;
if(!this.linkTail.prev.head){
node=this.linkTail.prev;
node.prev.next=this.linkTail;
this.linkTail.prev=node.prev;
deletethis.container[node.key];
this.length--;
}
returnnode;
};
/**
*从链表中移除指定节点
*@paramnode节点对象
*@returns{*}
*/
Elimination.prototype.remove=function(node){
node.prev.next=node.next;
node.next.prev=node.prev;
deletethis.container[node.key];
this.length--;
returnnode;
};
/**
*节点被访问需要做的处理,具体是把该节点移动到链表头
*@paramnode
*/
Elimination.prototype.use=function(node){
this.remove(node);
this.unshift(node);
};
/**
*LRU缓存淘汰算法实现
*@constructor
*/
functionLRU(){
Elimination.apply(this,arguments);
}
LRU.prototype=newFn();
LRU.prototype.get=function(key){
varnode=undefined;
node=this.container[key];
if(node){
this.use(node);
}
returnnode;
};
LRU.prototype.set=function(key,value){
varnode=this.buildNode(value,key);
if(this.length===this.maxLength){
this.pop();
}
this.unshift(node);
};
/**
*FIFO缓存淘汰算法实现
*@constructor
*/
functionFIFO(){
Elimination.apply(this,arguments);
}
FIFO.prototype=newFn();
FIFO.prototype.get=function(key){
varnode=undefined;
node=this.container[key];
returnnode;
};
FIFO.prototype.set=function(key,value){
varnode=this.buildNode(value,key);
if(this.length===this.maxLength){
this.shift();
}
this.append(node);
};
/**
*LRU、FIFO算法封装,成为新的twoqueues缓存淘汰算法
*@parammaxLength
*@constructor
*/
functionAgent(maxLength){
this.getCount=0;
this.hitCount=0;
this.lir=newFIFO(maxLength);
this.hir=newLRU(maxLength);
}
Agent.prototype.get=function(key){
varnode=undefined;
node=this.lir.get(key);
if(node){
node.use++;
if(node.use>=2){
this.lir.remove(node);
this.hir.set(node.key,node.data);
}
}else{
node=this.hir.get(key);
}
returnnode;
};
Agent.prototype.getx=function(key){
varnode=undefined;
this.getCount++;
node=this.get(key);
if(node){
this.hitCount++;
}
returnnode;
};
Agent.prototype.set=function(key,value){
varnode=null;
node=this.lir.container[key]||this.hir.container[key];
if(node){
node.data=value;
}else{
this.lir.set(key,value);
}
};
/**
*获取命中率
*@returns{*}
*/
Agent.prototype.hitRatio=function(){
varret=this.getCount;
if(ret){
ret=this.hitCount/this.getCount;
}
returnret;
};
/**
*对外接口
*@parammaxLength缓存容量
*@paramdev是否为开发环境,开发环境会统计命中率,反之不会
*@returns{{get,set:Function,hitRatio:Function}}
*/
exports.initTwoQueues=function(maxLength,dev){
varapi=newAgent(maxLength);
return{
get:(function(){
if(dev){
returnfunction(key){
varret=api.getx(key);
returnret&&ret.data;
};
}else{
returnfunction(key){
varret=api.get(key);
returnret&&ret.data;
};
}
}()),
set:function(){
api.set.apply(api,arguments);
},
hitRatio:function(){
returnapi.hitRatio.apply(api,arguments);
}
};
};
}(this));
最后,再次提醒,缓存算法需要和实际应用场景相结合,没有万能算法,合适的才是最好的!
相关文章
- self hosted private support chat software use JavaScript remove HTML tags
- 实现千元分隔符javascript代码详解编程语言
- 实例:用JavaScript来操作字符串(一些字符串函数)
- JavaScript验证浏览器是否支持javascript的方法小结
- JAVASCRIPT实现普通日期转换多少小时前、多少分钟前、多少秒
- javascript实现面向对象类的功能书写技巧
- javascript各浏览器中option元素的表现差异
- javascript中全局对象的parseInt()方法使用介绍
- javascript中全局对象的isNaN()方法使用介绍
- JavaScript中伪协议javascript:使用探讨
- javascript引用赋值(地址传值)用法实例