Nodejs基于LRU算法實(shí)現(xiàn)的緩存處理操作示例
本文實(shí)例講述了Nodejs基于LRU算法實(shí)現(xiàn)的緩存處理操作。分享給大家供大家參考,具體如下:
LRU是Least Recently Used的縮寫,即最近最少使用頁面置換算法,是為虛擬頁式存儲管理服務(wù)的,是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進(jìn)行決策了。由于無法預(yù)測各頁面將來的使用情況,只能利用“最近的過去”作為“最近的將來”的近似,因此,LRU算法就是將最近最久未使用的頁面予以淘汰。
可以用一個特殊的棧來保存當(dāng)前正在使用的各個頁面的頁面號。當(dāng)一個新的進(jìn)程訪問某頁面時,便將該頁面號壓入棧頂,其他的頁面號往棧底移,如果內(nèi)存不夠,則將棧底的頁面號移除。這樣,棧頂始終是最新被訪問的頁面的編號,而棧底則是最近最久未訪問的頁面的頁面號。
如輸入以下序列時:4,7,0,7,1,0,1,2,1,2,6
結(jié)果為:
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時構(gòu)造一般緩存。
function CacheLRU(capacity) { /* 利用Buffer寫的一個LRU緩存,capacity為緩存容量,為0時不限容量。 myCache = new CacheLRU(capacity); //構(gòu)造緩存 myCache.get(key); //讀取名為key的緩存值 myCache.put(key, value); //寫入名為key的緩存值 myCache.remove(key); //刪除名為key的緩存值 myCache.removeAll(); //清空緩存 myCache.info(); //返回myCache緩存信息 LRU原理:對所有緩存數(shù)據(jù)的key構(gòu)建hash鏈表,當(dāng)對某一數(shù)據(jù)進(jìn)行g(shù)et或put操作時,將其key提到鏈表前端(最新)。當(dāng)進(jìn)行put數(shù)據(jù)超出容量時,刪除鏈表尾端(最舊)的緩存數(shù)據(jù)。 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算法也可以用于一些實(shí)際的應(yīng)用中,如你要做一個瀏覽器,或類似于淘寶客戶端的應(yīng)用的就要用到這個原理。大家都知道瀏覽器在瀏覽網(wǎng)頁的時候會把下載的圖片臨時保存在本機(jī)的一個文件夾里,下次再訪問時就會,直接從本機(jī)臨時文件夾里讀取。但保存圖片的臨時文件夾是有一定容量限制的,如果你瀏覽的網(wǎng)頁太多,就會一些你最不常使用的圖像刪除掉,只保留最近最久使用的一些圖片。這時就可以用到LRU算法 了,這時上面算法里的這個特殊的棧就不是保存頁面的序號了,而是每個圖片的序號或大小;所以上面這個棧的元素都用Object類來表示,這樣的話這個棧就可以保存的對像了。
希望本文所述對大家nodejs程序設(shè)計有所幫助。
相關(guān)文章
Nodejs 發(fā)布自己的npm包并制作成命令行工具的實(shí)例講解
今天小編就為大家分享一篇Nodejs 發(fā)布自己的npm包并制作成命令行工具的實(shí)例講解,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2018-05-05使用Node.js創(chuàng)建本地HTTP服務(wù)器并實(shí)現(xiàn)異地遠(yuǎn)程訪問的方法
Node.js 是能夠在服務(wù)器端運(yùn)行 JavaScript 的開放源代碼、跨平臺運(yùn)行環(huán)境,這篇文章主要介紹了如何使用Node.js快速創(chuàng)建本地HTTP服務(wù)器并實(shí)現(xiàn)異地遠(yuǎn)程訪問,需要的朋友可以參考下2024-01-01使用Node.js創(chuàng)建HTTP服務(wù)器并實(shí)現(xiàn)公網(wǎng)訪問本地Server的步驟
Node.js含有一系列內(nèi)置模塊,使得程序可以脫離 Apache HTTP Server 或 IIS,作為獨(dú)立服務(wù)器運(yùn),下面將介紹如何簡單幾步實(shí)現(xiàn)遠(yuǎn)程公共網(wǎng)絡(luò)下訪問windwos node.js的服務(wù)端,感興趣的朋友一起看看吧2023-11-11詳解node.js平臺下Express的session與cookie模塊包的配置
本篇文章主要介紹了詳解node.js平臺下Express的session與cookie模塊包的配置,具有一定的參考價值,有興趣的可以了解一下。2017-04-04Node.js如何對SQLite的async/await封裝詳解
這篇文章主要給大家介紹了關(guān)于Node.js如何對SQLite的async/await進(jìn)行封裝的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-02-02詳解nodejs微信公眾號開發(fā)——1.接入微信公眾號
本篇文章主要介紹了詳解nodejs微信公眾號開發(fā)——1.接入微信公眾號,非常具有實(shí)用價值,需要的朋友可以參考下2017-04-04nodejs不用electron實(shí)現(xiàn)打開文件資源管理器并選擇文件
最近在開發(fā)一些小腳本,用 nodejs 實(shí)現(xiàn),其中很多功能需要選擇一個/多個文件,或者是選擇一個文件夾,這種情況下網(wǎng)上給出的解決方案都是 electron,但是我一個小腳本用 electron 屬實(shí)有點(diǎn)夸張了,后來轉(zhuǎn)念一想可以通過 powershell 來實(shí)現(xiàn)類似的功能,需要的朋友可以參考下2024-01-01