欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

JavaScript雙向鏈表實(shí)現(xiàn)LFU緩存算法

 更新時(shí)間:2022年01月14日 09:46:57   作者:SADON_jung  
本文主要介紹了JavaScript雙向鏈表實(shí)現(xiàn)LFU緩存算法,文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下

什么是LFU

LFU(Least Frequently Used),最近最少使用策略,也就是說(shuō)在一段時(shí)間內(nèi),數(shù)據(jù)被使用頻次最少的,優(yōu)先被淘汰。
它是一種用于管理計(jì)算機(jī)內(nèi)存的緩存算法,采用LFU算法的最簡(jiǎn)單方法是為每個(gè)加載到緩存的塊分配一個(gè)計(jì)數(shù)器。每次引用該塊時(shí),計(jì)數(shù)器將增加一。當(dāng)緩存達(dá)到容量并有一個(gè)新的內(nèi)存塊等待插入時(shí),系統(tǒng)將搜索計(jì)數(shù)器最低的塊并將其從緩存中刪除。

描述

請(qǐng)你為 最不經(jīng)常使用(LFU)緩存算法設(shè)計(jì)并實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)。

實(shí)現(xiàn) LFUCache 類(lèi):

LFUCache(int capacity) - 用數(shù)據(jù)結(jié)構(gòu)的容量 capacity 初始化對(duì)象

int get(int key) - 如果鍵 key 存在于緩存中,則獲取鍵的值,否則返回 -1 。

void put(int key, int value) - 如果鍵 key 已存在,則變更其值;如果鍵不存在,請(qǐng)插入鍵值對(duì)。

當(dāng)緩存達(dá)到其容量 capacity 時(shí),則應(yīng)該在插入新項(xiàng)之前,移除最不經(jīng)常使用的項(xiàng)。

在此問(wèn)題中,當(dāng)存在平局(即兩個(gè)或更多個(gè)鍵具有相同使用頻率)時(shí),應(yīng)該去除 最近最久未使用 的鍵。

為了確定最不常使用的鍵,可以為緩存中的每個(gè)鍵維護(hù)一個(gè) 使用計(jì)數(shù)器 。使用計(jì)數(shù)最小的鍵是最久未使用的鍵。

當(dāng)一個(gè)鍵首次插入到緩存中時(shí),它的使用計(jì)數(shù)器被設(shè)置為 1 (由于 put 操作)。對(duì)緩存中的鍵執(zhí)行 get 或 put 操作,使用計(jì)數(shù)器的值將會(huì)遞增。

函數(shù) get 和 put 必須以 O(1) 的平均時(shí)間復(fù)雜度運(yùn)行。

解題思路

1、構(gòu)造節(jié)點(diǎn)結(jié)構(gòu)體

保存對(duì)應(yīng)的數(shù)據(jù)信息

const LFUNode = function (
? key = "",
? val = "",
? freq = 0,
? pre = null,
? next = null
) {
? this.key = key;
? this.val = val;
? this.freq = freq;
? this.pre = pre;
? this.next = next;
};

2、構(gòu)造雙向鏈表

構(gòu)造帶有頭尾節(jié)點(diǎn)的雙向鏈表,head和tail為哨兵節(jié)點(diǎn),不保存信息,僅用于標(biāo)記頭尾。

const LFULinkLine = function (node) {
? let head = new LFUNode("head");
? let tail = new LFUNode("tail");
? head.next = node;
? tail.pre = node;
? node.pre = head;
? node.next = tail;
? this.head = head;
? this.tail = tail;
};

3、編寫(xiě)鏈表頭添加節(jié)點(diǎn)方法

將節(jié)點(diǎn)插入到鏈表的頭結(jié)點(diǎn)之后,其他節(jié)點(diǎn)往后移。

LFULinkLine.prototype.addNode = function (node) {
? this.head.next.pre = node;
? node.pre = this.head;
? node.next = this.head.next;
? this.head.next = node;
};

4、編寫(xiě)刪除節(jié)點(diǎn)方法

將節(jié)點(diǎn)從鏈表中刪除。

LFULinkLine.prototype.removeNode = function (node) {
? node.pre.next = node.next;
? node.next.pre = node.pre;
};

5、構(gòu)造LRU緩存結(jié)構(gòu)體

構(gòu)造LRU緩存結(jié)構(gòu)體,具體信息如下代碼,capacity用于保存最大緩存數(shù),即該類(lèi)的容量;num保存當(dāng)前存儲(chǔ)的數(shù)據(jù)量,用于判別是否超出最大容量;minFreq保存當(dāng)前存儲(chǔ)的數(shù)據(jù)中的最小頻率,刪除的時(shí)候需要優(yōu)先刪除頻率最小的;kvMap保存節(jié)點(diǎn)詳細(xì)信息,索引為節(jié)點(diǎn)的key值,查詢(xún)可以直接從這里查出信息;freqMap保存對(duì)應(yīng)頻率的鏈表信息,索引為節(jié)點(diǎn)的freq(頻率),刪除的時(shí)候可以快速?gòu)倪@里獲取需要?jiǎng)h除節(jié)點(diǎn)的信息。

/**
?* @param {number} capacity
?*/
var LFUCache = function (capacity) {
? this.capacity = capacity;//最大緩存
? this.num = 0;//當(dāng)前數(shù)目
? this.minFreq = 0;//當(dāng)前最小頻率
? this.kvMap = new Map();//保存節(jié)點(diǎn)信息
? this.freqMap = new Map();//保存對(duì)應(yīng)頻率的鏈表信息
};

6、編寫(xiě)get方法

get主要有以下兩種情況:

(1)節(jié)點(diǎn)存在

  • 通過(guò)kvMap獲取到對(duì)應(yīng)節(jié)點(diǎn)
  • 將節(jié)點(diǎn)從freqMap中刪除
  • 判斷是否需要修改minFreq
  • 修改節(jié)點(diǎn)的freq
  • 重新將節(jié)點(diǎn)插入freqMap
  • 返回節(jié)點(diǎn)的value

(2)節(jié)點(diǎn)不存在
容量capacity為0或者kvMap中沒(méi)有該節(jié)點(diǎn)信息,直接返回-1即可。

/**
?* @param {number} key
?* @return {number}
?*/
LFUCache.prototype.get = function (key) {
? if (this.capacity === 0) return -1;
? if (!this.kvMap.has(key)) return -1;
? //通過(guò)kvMap獲取到對(duì)應(yīng)節(jié)點(diǎn)
? let node = this.kvMap.get(key);
? let linkLine = this.freqMap.get(node.freq);
? //將節(jié)點(diǎn)從freqMap中刪除
? linkLine.removeNode(node);
? //判斷是否需要修改minFreq
? //清空了
? if (linkLine.head.next === linkLine.tail) {
? ? this.freqMap.delete(node.freq);
? ? if (this.minFreq == node.freq) this.minFreq++;
? }
? //修改節(jié)點(diǎn)的freq
? node.freq++;
? //重新將節(jié)點(diǎn)插入freqMap
? if (this.freqMap.has(node.freq)) {
? ? linkLine = this.freqMap.get(node.freq);
? ? linkLine.addNode(node);
? } else {
? ? this.freqMap.set(node.freq, new LFULinkLine(node));
? }
? //返回節(jié)點(diǎn)的value
? return node.val;
};

7、編寫(xiě)put方法

put操作主要有以下兩種情況:

(1)更新

  • 通過(guò)kvMap獲取到對(duì)應(yīng)節(jié)點(diǎn)
  • 將節(jié)點(diǎn)從freqMap中刪除
  • 判斷是否需要修改minFreq
  • 更新節(jié)點(diǎn)信息
  • 重新將節(jié)點(diǎn)插入freqMap

(2)存入

存入情況下又有兩種情況:

容量已滿(mǎn)

  • 通過(guò)minFreq找到需要?jiǎng)h除的節(jié)點(diǎn)
  • 將節(jié)點(diǎn)從freqMap中刪除
  • 判斷是否需要修改minFreq
  • 將新節(jié)點(diǎn)插入freqMap
  • 更新minFreq

容量未滿(mǎn)

  • 修改num
  • 將新節(jié)點(diǎn)插入freqMap
  • 更新minFreq
/**
?* @param {number} key
?* @param {number} value
?* @return {void}
?*/
LFUCache.prototype.put = function (key, value) {
? if (this.capacity === 0) return;
? if (this.kvMap.has(key)) {
? ? //更新
? ? //通過(guò)kvMap獲取到對(duì)應(yīng)節(jié)點(diǎn)
? ? let node = this.kvMap.get(key);
? ? //將節(jié)點(diǎn)從freqMap中刪除
? ? let linkLine = this.freqMap.get(node.freq);
? ? linkLine.removeNode(node);
? ? //判斷是否需要修改minFreq
? ? if (linkLine.head.next === linkLine.tail) {
? ? ? if (this.minFreq == node.freq) this.minFreq++;
? ? ? this.freqMap.delete(node.freq);
? ? }
? ? //更新節(jié)點(diǎn)信息
? ? node.val = value;
? ? node.freq++;
? ? //重新將節(jié)點(diǎn)插入freqMap
? ? if (this.freqMap.has(node.freq)) {
? ? ? linkLine = this.freqMap.get(node.freq);
? ? ? linkLine.addNode(node);
? ? } else {
? ? ? linkLine = new LFULinkLine(node);
? ? ? this.freqMap.set(node.freq, linkLine);
? ? }
? } else {//存入
? ? if (this.capacity == this.num) {//存滿(mǎn)
? ? ? //通過(guò)minFreq找到需要?jiǎng)h除的節(jié)點(diǎn)
? ? ? let freq = this.minFreq;
? ? ? let linkLine = this.freqMap.get(freq);
? ? ? let node = linkLine.tail.pre;
? ? ? //將節(jié)點(diǎn)從freqMap中刪除 ?
? ? ? linkLine.removeNode(node);
? ? ? this.kvMap.delete(node.key);
? ? ? //判斷是否需要修改minFreq
? ? ? if (linkLine.head.next === linkLine.tail) {
? ? ? ? this.freqMap.delete(node.freq);
? ? ? }
? ? } else {
? ? ? //修改num
? ? ? this.num++;
? ? }
? ? //將新節(jié)點(diǎn)插入freqMap
? ? let node = new LFUNode(key, value, 0);
? ? this.kvMap.set(key, node);
? ? if (this.freqMap.has(0)) {
? ? ? let linkLine = this.freqMap.get(0);
? ? ? linkLine.addNode(node);
? ? } else {
? ? ? let linkLine = new LFULinkLine(node);
? ? ? this.freqMap.set(0, linkLine);
? ? }
? ? //更新minFreq
? ? this.minFreq = 0;
? }
};

代碼

const LFUNode = function (
? key = "",
? val = "",
? freq = 0,
? pre = null,
? next = null
) {
? this.key = key;
? this.val = val;
? this.freq = freq;
? this.pre = pre;
? this.next = next;
};
const LFULinkLine = function (node) {
? let head = new LFUNode("head");
? let tail = new LFUNode("tail");
? head.next = node;
? tail.pre = node;
? node.pre = head;
? node.next = tail;
? this.head = head;
? this.tail = tail;
};
LFULinkLine.prototype.addNode = function (node) {
? this.head.next.pre = node;
? node.pre = this.head;
? node.next = this.head.next;
? this.head.next = node;
};
LFULinkLine.prototype.removeNode = function (node) {
? node.pre.next = node.next;
? node.next.pre = node.pre;
};

/**
?* @param {number} capacity
?*/
var LFUCache = function (capacity) {
? this.capacity = capacity;
? this.num = 0;
? this.minFreq = 0;
? this.kvMap = new Map();
? this.freqMap = new Map();
};

/**
?* @param {number} key
?* @return {number}
?*/
LFUCache.prototype.get = function (key) {
? if (this.capacity === 0) return -1;
? if (!this.kvMap.has(key)) return -1;
? let node = this.kvMap.get(key);
? let linkLine = this.freqMap.get(node.freq);
? linkLine.removeNode(node);
? //清空了
? if (linkLine.head.next === linkLine.tail) {
? ? this.freqMap.delete(node.freq);
? ? if (this.minFreq == node.freq) this.minFreq++;
? }
? node.freq++;
? if (this.freqMap.has(node.freq)) {
? ? linkLine = this.freqMap.get(node.freq);
? ? linkLine.addNode(node);
? } else {
? ? this.freqMap.set(node.freq, new LFULinkLine(node));
? }
? return node.val;
};

/**
?* @param {number} key
?* @param {number} value
?* @return {void}
?*/
LFUCache.prototype.put = function (key, value) {
? if (this.capacity === 0) return;
? if (this.kvMap.has(key)) {
? ? //更新
? ? let node = this.kvMap.get(key);
? ? node.val = value;
? ? let linkLine = this.freqMap.get(node.freq);
? ? linkLine.removeNode(node);
? ? if (linkLine.head.next === linkLine.tail) {
? ? ? if (this.minFreq == node.freq) this.minFreq++;
? ? ? this.freqMap.delete(node.freq);
? ? }
? ? node.freq++;
? ? if (this.freqMap.has(node.freq)) {
? ? ? linkLine = this.freqMap.get(node.freq);
? ? ? linkLine.addNode(node);
? ? } else {
? ? ? linkLine = new LFULinkLine(node);
? ? ? this.freqMap.set(node.freq, linkLine);
? ? }
? } else {
? ? //存入
? ? if (this.capacity == this.num) {
? ? ? //存滿(mǎn)
? ? ? let freq = this.minFreq;
? ? ? let linkLine = this.freqMap.get(freq);
? ? ? let node = linkLine.tail.pre;
? ? ? linkLine.removeNode(node);
? ? ? this.kvMap.delete(node.key);

? ? ? if (linkLine.head.next === linkLine.tail) {
? ? ? ? this.freqMap.delete(node.freq);
? ? ? }
? ? } else {
? ? ? this.num++;
? ? }
? ? let node = new LFUNode(key, value, 0);
? ? this.kvMap.set(key, node);
? ? if (this.freqMap.has(0)) {
? ? ? let linkLine = this.freqMap.get(0);
? ? ? linkLine.addNode(node);
? ? } else {
? ? ? let linkLine = new LFULinkLine(node);
? ? ? this.freqMap.set(0, linkLine);
? ? }
? ? this.minFreq = 0;
? }
};

/**
?* Your LFUCache object will be instantiated and called as such:
?* var obj = new LFUCache(capacity)
?* var param_1 = obj.get(key)
?* obj.put(key,value)
?*/

到此這篇關(guān)于JavaScript雙向鏈表實(shí)現(xiàn)LFU緩存算法的文章就介紹到這了,更多相關(guān)JavaScript LFU緩存算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 如何判斷Javascript對(duì)象是否存在的簡(jiǎn)單實(shí)例

    如何判斷Javascript對(duì)象是否存在的簡(jiǎn)單實(shí)例

    下面小編就為大家?guī)?lái)一篇如何判斷Javascript對(duì)象是否存在的簡(jiǎn)單實(shí)例。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2016-05-05
  • 詳解javascript腳本何時(shí)會(huì)被執(zhí)行

    詳解javascript腳本何時(shí)會(huì)被執(zhí)行

    這篇文章主要介紹了詳解javascript腳本何時(shí)會(huì)被執(zhí)行,幫助大家更好的理解和使用JavaScript,感興趣的朋友可以了解下
    2021-02-02
  • JS隨機(jī)打亂數(shù)組的方法小結(jié)

    JS隨機(jī)打亂數(shù)組的方法小結(jié)

    這篇文章主要介紹了JS隨機(jī)打亂數(shù)組的方法,結(jié)合實(shí)例總結(jié)分析了幾種常用的數(shù)組打亂順序并重新進(jìn)行排序的技巧,非常簡(jiǎn)單實(shí)用,需要的朋友可以參考下
    2016-06-06
  • JSON.stringify()方法講解

    JSON.stringify()方法講解

    今天小編就為大家分享一篇關(guān)于JSON.stringify()方法講解,小編覺(jué)得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧
    2019-01-01
  • 如何使用JavaScript實(shí)現(xiàn)棧與隊(duì)列

    如何使用JavaScript實(shí)現(xiàn)棧與隊(duì)列

    這篇文章主要介紹了如何使用JavaScript實(shí)現(xiàn)棧與隊(duì)列。棧和隊(duì)列是web開(kāi)發(fā)中最常用的兩種數(shù)據(jù)結(jié)構(gòu)。絕大多數(shù)用戶(hù),甚至包括web開(kāi)發(fā)人員,都不知道這個(gè)驚人的事實(shí)。,需要的朋友可以參考下
    2019-06-06
  • JavaScript實(shí)現(xiàn)彩虹文字效果的方法

    JavaScript實(shí)現(xiàn)彩虹文字效果的方法

    這篇文章主要介紹了JavaScript實(shí)現(xiàn)彩虹文字效果的方法,涉及javascript操作文字樣式的技巧,非常具有實(shí)用價(jià)值,需要的朋友可以參考下
    2015-04-04
  • 利用CSS、JavaScript及Ajax實(shí)現(xiàn)圖片預(yù)加載的三大方法

    利用CSS、JavaScript及Ajax實(shí)現(xiàn)圖片預(yù)加載的三大方法

    本文主要介紹了利用CSS、JavaScript及Ajax實(shí)現(xiàn)圖片預(yù)加載的三大方法。具有很好的參考價(jià)值,下面跟著小編一起來(lái)看下吧
    2017-01-01
  • JS中Attr的用法詳解

    JS中Attr的用法詳解

    本文通過(guò)實(shí)例代碼給大家介紹了js中的attr的用法,非常不錯(cuò),具有參考借鑒價(jià)值,需要的朋友參考下吧
    2017-10-10
  • Bootstrap的圖片輪播示例代碼

    Bootstrap的圖片輪播示例代碼

    Bootstrap 是一個(gè)用于快速開(kāi)發(fā) Web 應(yīng)用程序和網(wǎng)站的前端框架。Bootstrap 是基于 HTML、CSS、JAVASCRIPT 的。本文給大家分享Bootstrap的圖片輪播示例代碼,小伙伴們快來(lái)圍觀吧。
    2015-08-08
  • 微信小程序?qū)崿F(xiàn)拍照功能

    微信小程序?qū)崿F(xiàn)拍照功能

    這篇文章主要為大家詳細(xì)介紹了微信小程序?qū)崿F(xiàn)拍照功能,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-04-04

最新評(píng)論