JavaScript版的TwoQueues緩存模型
本文所指TwoQueues緩存模型，是說數(shù)據(jù)在內(nèi)存中的緩存模型。
無論何種語言，都可能需要把一部分數(shù)據(jù)放在內(nèi)存中，避免重復運算、讀取。最常見的場景就是JQuery選擇器，有些Dom元素的選取是非常耗時的，我們希望能把這些數(shù)據(jù)緩存起來，不必每次調(diào)用都去重新遍歷Dom樹。
存就存吧，但總得有個量吧！總不能把所有的歷史數(shù)據(jù)都放在內(nèi)存中，畢竟目前內(nèi)存的容量還是相當可憐的，就算內(nèi)存夠大，理論上每個線程分配的內(nèi)存也是有限制的。
那么問題來了，如何才能高效的把真正有用的數(shù)據(jù)緩存起來呢？這就涉及到淘汰算法，需要把垃圾數(shù)據(jù)淘汰掉，才能保住有用的數(shù)據(jù)。
比較常用的思路有以下幾種：
FIFO：就是一個先進先出的隊列，最先緩存的數(shù)據(jù)，最早被淘汰，著名的JQuery框架內(nèi)部就是用的這種模型。
LRU：雙鏈表結構，每次有新數(shù)據(jù)存入，直接放在鏈表頭；每次被訪問的數(shù)據(jù)，也轉移到鏈表頭，這樣一來，鏈表尾部的數(shù)據(jù)即是最近沒被使用過的，淘汰之。
TwoQueues：FIFO+ LRU，F(xiàn)IFO主要存放初次存入的數(shù)據(jù)，LRU中存放至少使用過兩次的熱點數(shù)據(jù)，此算法命中率高，適應性強，復雜度低。
其他淘汰算法還有很多很多，但實際用的比較多的也就這兩種。因為他們本身算法不復雜，容易實現(xiàn)，執(zhí)行效率高，緩存的命中率在大多數(shù)場合也還可以接受。畢竟緩存算法也是需要消耗CPU的，如果太過復雜，雖然命中率有所提高，但得不償失。試想一下，如果從緩存中取數(shù)據(jù)，比從原始位置取還消耗時間，要緩存何用？
具體理論就不多說了，網(wǎng)上有的是，我也不怎么懂，今天給大家分享的是JavaScript版的TwoQueues緩存模型。
還是先說說使用方法，很簡單。
基本使用方法如下：
[/code]
var tq = initTwoQueues(10);
tq.set("key", "value");
tq.get("key");
[/code]
初始化的時候，指定一下緩存容量即可。需要注意的是，由于內(nèi)部采用FIFO+LRU實現(xiàn)，所以實際容量是指定容量的兩倍，上例指定的是10個（鍵值對），實際上可以存放20個。
容量大小需要根據(jù)實際應用場景而定，太小命中率低，太大效率低，物極必反，需要自己衡量。
在開發(fā)過程中，為了審查緩存效果如何，可以將緩存池初始化成開發(fā)版：
var tq = initTwoQueues(10, true);
tq.hitRatio();
就是在后邊加一個參數(shù)，直接true就可以了。這樣初始化的緩存池，會自動統(tǒng)計命中率，可以通過hitRatio方法獲取命中率。如果不加這個參數(shù)，hitRatio方法獲取的命中率永遠為0。
統(tǒng)計命中率肯定要消耗資源，所以生產(chǎn)環(huán)境下不建議開啟。
是時候分享代碼了：
(function(exports){
/**
* 繼承用的純凈類
* @constructor
*/
function Fn(){}
Fn.prototype = Elimination.prototype;
/**
* 基于鏈表的緩存淘汰算法父類
* @param maxLength 緩存容量
* @constructor
*/
function Elimination(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){
throw new Error("This method must be override!");
};
Elimination.prototype.set = function(key, value){
throw new Error("This method must be override!");
};
/**
* 創(chuàng)建鏈表中的節(jié)點
* @param data 節(jié)點包含的數(shù)據(jù)，即緩存數(shù)據(jù)值
* @param key 節(jié)點的唯一標示符，即緩存的鍵
* @returns {{}}
*/
Elimination.prototype.buildNode = function(data, key){
var node = {};
node.data = data;
node.key = key;
node.use = 0;
return node;
};
/**
* 從鏈表頭彈出一個節(jié)點
* @returns {*}
*/
Elimination.prototype.shift = function(){
var node = null;
if(!this.linkHead.next.tail){
node = this.linkHead.next;
this.linkHead.next = node.next;
node.next.prev = this.linkHead;
delete this.container[node.key];
this.length--;
}
return node;
};
/**
* 從鏈表頭插入一個節(jié)點
* @param node 節(jié)點對象
* @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++;
return node;
};
/**
* 從鏈表尾插入一個節(jié)點
* @param node 節(jié)點對象
* @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++;
return node;
};
/**
* 從鏈表尾彈出一個節(jié)點
* @returns {*}
*/
Elimination.prototype.pop = function(){
var node = null;
if(!this.linkTail.prev.head){
node = this.linkTail.prev;
node.prev.next = this.linkTail;
this.linkTail.prev = node.prev;
delete this.container[node.key];
this.length--;
}
return node;
};
/**
* 從鏈表中移除指定節(jié)點
* @param node 節(jié)點對象
* @returns {*}
*/
Elimination.prototype.remove = function(node){
node.prev.next = node.next;
node.next.prev = node.prev;
delete this.container[node.key];
this.length--;
return node;
};
/**
* 節(jié)點被訪問需要做的處理，具體是把該節(jié)點移動到鏈表頭
* @param node
*/
Elimination.prototype.use = function(node){
this.remove(node);
this.unshift(node);
};
/**
* LRU緩存淘汰算法實現(xiàn)
* @constructor
*/
function LRU(){
Elimination.apply(this, arguments);
}
LRU.prototype = new Fn();
LRU.prototype.get = function(key){
var node = undefined;
node = this.container[key];
if(node){
this.use(node);
}
return node;
};
LRU.prototype.set = function(key, value){
var node = this.buildNode(value, key);
if(this.length === this.maxLength){
this.pop();
}
this.unshift(node);
};
/**
* FIFO緩存淘汰算法實現(xiàn)
* @constructor
*/
function FIFO(){
Elimination.apply(this, arguments);
}
FIFO.prototype = new Fn();
FIFO.prototype.get = function(key){
var node = undefined;
node = this.container[key];
return node;
};
FIFO.prototype.set = function(key, value){
var node = this.buildNode(value, key);
if(this.length === this.maxLength){
this.shift();
}
this.append(node);
};
/**
* LRU、FIFO算法封裝，成為新的twoqueues緩存淘汰算法
* @param maxLength
* @constructor
*/
function Agent(maxLength){
this.getCount = 0;
this.hitCount = 0;
this.lir = new FIFO(maxLength);
this.hir = new LRU(maxLength);
}
Agent.prototype.get = function(key){
var node = 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);
}
return node;
};
Agent.prototype.getx = function(key){
var node = undefined;
this.getCount++;
node = this.get(key);
if(node){
this.hitCount++;
}
return node;
};
Agent.prototype.set = function(key, value){
var node = 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(){
var ret = this.getCount;
if(ret){
ret = this.hitCount / this.getCount;
}
return ret;
};
/**
* 對外接口
* @param maxLength 緩存容量
* @param dev 是否為開發(fā)環(huán)境，開發(fā)環(huán)境會統(tǒng)計命中率，反之不會
* @returns {{get, set: Function, hitRatio: Function}}
*/
exports.initTwoQueues = function(maxLength, dev){
var api = new Agent(maxLength);
return {
get: (function(){
if(dev){
return function(key){
var ret = api.getx(key);
return ret && ret.data;
};
}else{
return function(key){
var ret = api.get(key);
return ret && ret.data;
};
}
}()),
set: function(){
api.set.apply(api, arguments);
},
hitRatio: function(){
return api.hitRatio.apply(api, arguments);
}
};
};
}(this));
最后，再次提醒，緩存算法需要和實際應用場景相結合，沒有萬能算法，合適的才是最好的！
相關文章
這篇文章主要介紹了javascript數(shù)組去重方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-03-03
我們下面來看一篇關于JavaScript中借用方法的一個詳細介紹，注意：本文假設你已經(jīng)掌握使用 call()、apply()和bind()的相關知識和它們之間的區(qū)別，希望這篇文章能夠讓各位了解到JavaScript中的借用方法吧。2016-08-08
這篇文章主要介紹了Javascript常用正則表達式應用，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-03-03
document.all想必學習javascript的同學們都很了解吧，本文主要是針對一些剛入門的童鞋們做一下有關document.all的相關總結，感興趣的朋友可以了解下，或許本文對你有所幫助2013-01-01
這篇文章主要為大家介紹了，JavaScript運算符詳解，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01
這篇文章主要介紹了js四舍五入數(shù)學函數(shù)round使用實例,需要的朋友可以參考下2014-05-05
這是一個簡單可用的拖拽代碼。用鼠標和鍵盤都可以操作。2010-02-02
下面小編就為大家?guī)硪黄钊肜斫膺壿嫳磉_式的用法 與或非的用法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-06-06
文檔對象模式（Document Object Model DOM）用來描述HTML頁面中那些輸入框、圖片、段落等等元素與最頂級的結構document之間的關系。用適當?shù)姆椒▉磉x取這些元素，我們就可以改變他們。2010-02-02
模塊化是一種將系統(tǒng)分離成獨立功能部分的方法，可將系統(tǒng)分割成獨立的功能部分，嚴格定義模塊接口、模塊間具有透明性2013-09-09