DIV CSS 佈局教程網

JavaScript 版的 TwoQueues 緩存模型
編輯:JavaScript基礎知識     

本文所說的 TwoQueues 緩存模型,指的是資料在記憶體中的緩存模型。

無論何種語言,都可能需要把一部分資料放在記憶體中,以避免重複運算與讀取。最常見的場景莫過於 jQuery 選擇器——有些 DOM 元素的選取非常耗時,我們希望能把這些資料緩存起來,不必每次呼叫都重新遍歷 DOM 樹。

可是要緩存就得有個上限,總不能把所有的歷史資料都塞進記憶體。畢竟記憶體容量有限,即便足夠大,理論上每個線程分配的記憶體也是有上限的。

那麼問題來了:如何才能高效地把真正有用的資料緩存起來呢?這就涉及淘汰算法——需要把垃圾資料淘汰掉,才能保住有用的資料。

比較常用的思路有以下幾種:

· FIFO:就是一個先進先出的隊列,最先緩存的資料最早被淘汰,著名的 jQuery 框架內部採用的就是這種模型。

· LRU:採用雙向鏈表結構,每次有新資料存入直接放在鏈表頭;每次被存取的資料也轉移到鏈表頭。如此一來,鏈表尾部的資料便是最近沒被使用過的,淘汰即可。

· TwoQueues:FIFO + LRU,FIFO 主要存放初次存入的資料,LRU 中存放至少使用過兩次的熱點資料。此算法命中率高、適應性強、複雜度低。

其他淘汰算法還有很多,但實際用得比較多的也就這兩種。因為它們本身算法不複雜、容易實現、執行效率高,緩存命中率在大多數場合也還可以接受。畢竟緩存算法本身也需要消耗 CPU,若過於複雜,雖然命中率有所提高,卻得不償失。試想一下,如果從緩存中取資料比從原始位置取還耗時,那要緩存何用?

具體理論這裡就不多贅述了,網上資料豐富。今天要和大家分享的是 JavaScript 版的 TwoQueues 緩存模型。

使用方法

基本使用方法非常簡單:

 var tq = initTwoQueues(10); tq.set("key", "value"); tq.get("key");

初始化時,指定一下緩存容量即可。需要注意的是,由於內部採用 FIFO + LRU 實現,所以實際容量是指定容量的兩倍——上例指定的是 10 個(鍵值對),實際上可以存放 20 個。

容量大小需根據實際應用場景而定:太小命中率低,太大效率低,物極必反,需要自己權衡。

在開發過程中,為了審查緩存效果,可以將緩存池初始化為開發版:

 var tq = initTwoQueues(10, true); tq.hitRatio();

就是在後面加一個參數 true 即可。這樣初始化的緩存池會自動統計命中率,可以透過 hitRatio 方法獲取。如果不加這個參數,hitRatio 方法獲得的命中率永遠為 0。統計命中率勢必要消耗資源,因此生產環境下不建議開啟。

源碼

 (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!"); }; /** * 創建鏈表中的節點 */ Elimination.prototype.buildNode = function(data, key){ var node = {}; node.data = data; node.key = key; node.use = 0; return node; }; /** * 從鏈表頭彈出一個節點 */ 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; }; /** * 從鏈表頭插入一個節點 */ 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; }; /** * 從鏈表尾插入一個節點 */ 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; }; /** * 從鏈表尾彈出一個節點 */ 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; }; /** * 從鏈表中移除指定節點 */ Elimination.prototype.remove = function(node){ node.prev.next = node.next; node.next.prev = node.prev; delete this.container[node.key]; this.length--; return node; }; /** * 節點被訪問需要做的處理,即把該節點移動到鏈表頭 */ Elimination.prototype.use = function(node){ this.remove(node); this.unshift(node); }; /** * LRU緩存淘汰算法實現 * @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緩存淘汰算法實現 * @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 緩存淘汰算法 * @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); } }; /** * 獲取命中率 */ Agent.prototype.hitRatio = function(){ var ret = this.getCount; if(ret){ ret = this.hitCount / this.getCount; } return ret; }; /** * 對外接口 * @param maxLength 緩存容量 * @param dev 是否為開發環境 */ 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));

最後,再次提醒:緩存算法需要與實際應用場景相結合,沒有萬能的算法,合適的才是最好的!

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved