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

JavaScript實(shí)現(xiàn)LRU算法的示例詳解

 更新時(shí)間:2023年04月26日 10:18:54   作者:虎妞先生  
不知道屏幕前的朋友們,有沒有和我一樣,覺得LRU算法原理很容易理解,實(shí)現(xiàn)起來卻很復(fù)雜。所以本文就為大家整理了一下實(shí)現(xiàn)的示例代碼,需要的可以參考一下

不知道屏幕前的朋友們,有沒有和我一樣,覺得LRU算法原理很容易理解,實(shí)現(xiàn)起來卻很復(fù)雜。

明明一個(gè)map就能解決,標(biāo)準(zhǔn)答案卻總要使用雙向鏈表。

實(shí)現(xiàn)思路很很容易理解,但是下筆寫代碼總是磕磕絆絆。

但是這個(gè)算法在前端使用場(chǎng)景很多,面試經(jīng)常問,正巧我遇到了這個(gè)問題,因此抓住機(jī)會(huì)和大家記錄分享一下

LRU簡介

least Recently Used 最近最少使用,用于操作系統(tǒng)內(nèi)存管理,在前端開發(fā)中常用于優(yōu)化頁面性能和資源利用率。

直接翻譯就是“最不經(jīng)常使用的數(shù)據(jù),重要性是最低的,應(yīng)該優(yōu)先刪除”

以下是在前端中使用LRU算法的幾個(gè)應(yīng)用場(chǎng)景:

前端路由:在單頁應(yīng)用(SPA)中,通過將路由信息保存在緩存中,可以避免每次訪問頁面時(shí)都需要重新加載數(shù)據(jù),從而提高頁面響應(yīng)速度和用戶體驗(yàn)。

圖片懶加載:對(duì)于大型圖片庫,可以使用LRU算法對(duì)已加載的圖片進(jìn)行緩存,當(dāng)一個(gè)新圖片需要被加載時(shí),可以先檢查該圖片是否已經(jīng)在緩存中存在,如果存在則直接從緩存中獲取,否則從服務(wù)器加載。

數(shù)據(jù)緩存:對(duì)于需要頻繁讀取的數(shù)據(jù)或者需要復(fù)雜計(jì)算才能得出結(jié)果的數(shù)據(jù),可以使用LRU算法對(duì)其進(jìn)行緩存,以減少重復(fù)計(jì)算的時(shí)間。

字體應(yīng)用:對(duì)于網(wǎng)站上使用的字體文件,可以使用LRU算法將最常用的字體文件存儲(chǔ)在緩存中,從而加快頁面渲染速度和節(jié)省網(wǎng)絡(luò)流量。

總之,LRU算法可用于提升前端應(yīng)用的性能和用戶體驗(yàn),但需要根據(jù)具體的應(yīng)用場(chǎng)景選擇合適的算法并進(jìn)行合理的配置。

如何實(shí)現(xiàn)

那么如何實(shí)現(xiàn)一個(gè)LRU 算法呢?我們一起看看leetcode 146這道題目

設(shè)計(jì)一個(gè)LRU類,實(shí)現(xiàn)get put 方法

題目簡單描述:

請(qǐng)你設(shè)計(jì)并實(shí)現(xiàn)一個(gè)滿足 LRU (最近最少使用) 緩存 約束的數(shù)據(jù)結(jié)構(gòu)。

實(shí)現(xiàn) LRUCache 類:

  • LRUCache(int capacity) 以 正整數(shù) 作為容量 capacity 初始化 LRU 緩存
  • int get(int key) 如果關(guān)鍵字 key 存在于緩存中,則返回關(guān)鍵字的值,否則返回 -1 。
  • void put(int key, int value) 如果關(guān)鍵字 key 已經(jīng)存在,則變更其數(shù)據(jù)值 value ;如果不存在,則向緩存中插入該組 key-value 。如果插入操作導(dǎo)致關(guān)鍵字?jǐn)?shù)量超過 capacity ,則應(yīng)該 逐出 最久未使用的關(guān)鍵字。

實(shí)現(xiàn)思路

我們使用一個(gè)map 來緩存數(shù)據(jù)。

當(dāng)獲取數(shù)據(jù)key 時(shí),優(yōu)先判斷是否存在于map,如果在我們先拿到這個(gè)值存為temp,然后從map中刪除,重新set進(jìn)map中

當(dāng)插入數(shù)據(jù)時(shí),優(yōu)先判斷是否存在于map,如果不存在,直接set,如果存在,刪除后哦嗎,重新set

這樣我們保證最近使用的都在map 的最下層,當(dāng)內(nèi)存超出時(shí),直接刪除map 頂層元素即可

this.map.delete(this.map.keys().next().value)

var LRUCache = function(capacity) {
	this.capacity = capacity
  this.map = new Map()
}

LRUCache.prototype.get = function(key) {
  if(this.map.has(key)) {
    let temp = this.map.get(key)
    this.map.delete(key)
    this.map.set(key,temp)
    return temp
  } else {
    return -1
  }

}
LRUCache.prototype.put = function(key, value) {
	if(this.map.has(key)) {
    this.map.delete(key)
  }
  this.map.set(key,value)
  if(this.map.size > this.capacity) {
    this.map.delete(this.map.keys().next().value)
  }
}

缺陷

雖然該實(shí)現(xiàn)使用了 Map 對(duì)象,但是在最壞情況下,如果哈希函數(shù)分布不均勻,可能會(huì)導(dǎo)致哈希沖突,使得某些操作的時(shí)間復(fù)雜度變?yōu)?O(n)。因此,在實(shí)際應(yīng)用中,如果需要高效地處理大規(guī)模數(shù)據(jù),建議使用雙向鏈表或其他更高效的數(shù)據(jù)結(jié)構(gòu)。

假設(shè)有一個(gè)哈希表,大小為 5,使用的哈希函數(shù)為 key % 5?,F(xiàn)在插入以下 6 個(gè)鍵值對(duì):

{key: 1, value: 'a'}
{key: 2, value: 'b'}
{key: 3, value: 'c'}
{key: 4, value: 'd'}
{key: 6, value: 'e'}
{key: 11, value: 'f'}

根據(jù)給定的哈希函數(shù) key % 5,可以將每個(gè)鍵映射到哈希表中的一個(gè)桶。具體來說,將鍵除以 5 并取余數(shù),以得到它應(yīng)該插入的桶的索引。

使用這個(gè)哈希函數(shù),將上述六個(gè)鍵值對(duì)插入哈希表中,得到以下結(jié)果:

在索引 1 的桶中插入 {key: 1, value: 'a'}

在索引 2 的桶中插入 {key: 2, value: 'b'}

'在索引 3 的桶中插入 {key: 3, value: 'c'}

在索引 4 的桶中插入 {key: 4, value: 'd'}

在索引 1 的桶中插入 {key: 6, value: 'e'}

在索引 1 的桶中插入 {key: 11, value: 'f'}

注意,在將鍵為 6 和 11 的鍵值對(duì)插入哈希表時(shí),它們都被映射到索引 1 的桶中。這是因?yàn)樗鼈兎謩e與 1 余數(shù)相同。

當(dāng)出現(xiàn)哈希沖突時(shí),即多個(gè)鍵被映射到同一桶時(shí)

這種情況下,在操作時(shí)需要遍歷整個(gè)桶來查找指定的鍵值對(duì),因此操作的時(shí)間復(fù)雜度變?yōu)?O(n)。

雙向鏈表+哈希表

那么如何達(dá)到O(1)的時(shí)間復(fù)雜度呢?

那肯定選用 map 查詢。修改,刪除也要盡量 O(1) 完成。搜尋常見的數(shù)據(jù)結(jié)構(gòu),鏈表,棧,隊(duì)列,樹,圖。樹和圖排除,棧和隊(duì)列無法任意查詢中間的元素,也排除。所以選用鏈表來實(shí)現(xiàn)。但是如果選用單鏈表,刪除這個(gè)結(jié)點(diǎn),需要 O(n) 遍歷一遍找到前驅(qū)結(jié)點(diǎn)。所以選用雙向鏈表,在刪除的時(shí)候也能 O(1) 完成。

核心就是:最近最多使用的節(jié)點(diǎn)永遠(yuǎn)在鏈表結(jié)尾,最近最少使用的節(jié)點(diǎn)在鏈表開頭。

雙向鏈表

雙向鏈表的結(jié)構(gòu)

value: 存儲(chǔ)的值

prev: 指向前一個(gè)元素的指針

next: 指向下一個(gè)元素的指針

Head和Tail是虛擬的頭部和尾部節(jié)點(diǎn),這是為了方便找到鏈表的首末設(shè)定的

       ┌──────>┐    ┌───────>┐   ┌───────>┐
  head • (x|"three"|•)  (•|"two"|•)  (•|"one"|x) • tail
               └<────────┘   └<───────┘   └<─────┘

實(shí)現(xiàn)思路

1.使用一個(gè)Map 對(duì)象來存儲(chǔ)鍵值對(duì)

2.使用一個(gè)雙向鏈表維護(hù)鍵值對(duì)的順序

3.抽離出一個(gè)addToTaill 方法(將節(jié)點(diǎn)插入末尾)抽離出一個(gè)remove 方法(刪除節(jié)點(diǎn))

4.當(dāng)執(zhí)行put 操作時(shí),判斷節(jié)點(diǎn)是否在map中

  • 如果存在,獲取當(dāng)前節(jié)點(diǎn)值,在雙向鏈表中remove刪除改節(jié)點(diǎn),重新調(diào)用 addToTail 添加到末尾
  • 如果不存在,建立一個(gè)雙向鏈表節(jié)點(diǎn),調(diào)用 addToTail 添加到末尾,同時(shí)添加進(jìn)map
  • 如果超過容量this.size > this.cap,刪除當(dāng)前head節(jié)點(diǎn),從map中刪除當(dāng)前key

5.當(dāng)執(zhí)行g(shù)et 操作時(shí),判斷節(jié)點(diǎn)是否在map中

  • 如果不存在,返回-1
  • 如果存在,獲取當(dāng)前key,value,重新執(zhí)行put 操作
class ListNode {
  constructor(key, value) {
    this.key = key;
    this.val = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity = 10) {
    this.capacity = capacity;
    // 實(shí)際保存的鍵值對(duì)數(shù)量
    this.size = 0;
    this.map = {};
    //代表最舊的節(jié)點(diǎn)
    this.head = null;
    //代表最新的節(jié)點(diǎn)
    this.tail = null;
  }

  get(key) {
    const node = this.map.get(key);
    if (!node) return -1;
    let node = this.map[key];
    this.put(node.key, node.val);
    return node.value;
  }

  put(key, value) {
    if(this.map[key]) {
    	let node = this.map[key]
      node.val = value
      this.remove(node)
      this.addTotail(node)
    } else {
      let node = new ListNode(key,value)
      this.addTotail(node)
      this.map[key] = node
      this.size++
    }
    if (this.size > this.cap) {
      let key = this.head.key;
      this.remove(this.head);
      delete this.map[key];
      this.size--;
    }
  }
  addToTail(node) {
    if(this.tail) {
      this.tail.next = node
      node.prev = this.tail
      this.tail = node
    } else {
      this.tail = node
      this.head = node
    }
  }
  remove(node) {
    if(node.prev) {
      node.prev.next = node.next
    } else {
      this.head = this.head.next
    }
    if(node.next) {
      node.next.prev = node.prev
    } else {
      this.tail = this.tail.prev
    }
    node.prev = node.next = null;
  }
}

以上就是JavaScript實(shí)現(xiàn)LRU算法的示例詳解的詳細(xì)內(nèi)容,更多關(guān)于JavaScript LRU算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

最新評(píng)論