本篇文章為大家展示了LRU緩存淘汰算法以及python實(shí)現(xiàn)的方法，內(nèi)容簡(jiǎn)明扼要并且容易理解，絕對(duì)能使你眼前一亮，通過(guò)這篇文章的詳細(xì)介紹希望你能有所收獲。

成都創(chuàng)新互聯(lián)公司服務(wù)項(xiàng)目包括忻州網(wǎng)站建設(shè)、忻州網(wǎng)站制作、忻州網(wǎng)頁(yè)制作以及忻州網(wǎng)絡(luò)營(yíng)銷策劃等。多年來(lái)，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，忻州網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到忻州省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

緩存

緩存的英文是cache，最早其實(shí)指的是用于CPU和主存數(shù)據(jù)交互的。早年這塊存儲(chǔ)被稱為高速緩存，最近已經(jīng)聽(tīng)不到這個(gè)詞了，不知道是不是淘汰了。因?yàn)榫彺娴淖x寫(xiě)速度要高于CPU低于主存，所以是用來(lái)過(guò)渡數(shù)據(jù)用的。CPU從緩存當(dāng)中讀取數(shù)據(jù)，主存的數(shù)據(jù)也會(huì)先加載到緩存當(dāng)中來(lái)，之后再進(jìn)入CPU。

后來(lái)緩存有了更多的應(yīng)用和意為，在后端服務(wù)當(dāng)中一般用來(lái)快速響應(yīng)請(qǐng)求。其實(shí)這里的思想和記憶化搜索有點(diǎn)像，我們把可能要用到的數(shù)據(jù)先存起來(lái)，后期如果要用到的話，就可以直接從內(nèi)存當(dāng)中讀取而不是再去計(jì)算一遍了。原理也是一樣的，有了緩存我們可以把要返回給用戶的數(shù)據(jù)儲(chǔ)存在內(nèi)存中，當(dāng)同樣的請(qǐng)求過(guò)來(lái)的時(shí)候，我們就可以直接從內(nèi)存當(dāng)中讀取結(jié)果，而不是再走一次鏈路獲取數(shù)據(jù)了。

舉一個(gè)很簡(jiǎn)單的例子，比如說(shuō)我們打開(kāi)淘寶首頁(yè)會(huì)看到很多商品的推薦。其實(shí)推薦商品的流程是非常復(fù)雜的，首先要根據(jù)一定的策略去商品庫(kù)當(dāng)中召回商品。比如根據(jù)用戶之前的行為召回和歷史行為相關(guān)的商品，召回了商品之后還要進(jìn)行清洗，過(guò)濾掉一些明確不感興趣或者是非法、違規(guī)的商品。過(guò)濾了之后需要使用機(jī)器學(xué)習(xí)或者是深度學(xué)習(xí)的模型來(lái)進(jìn)行點(diǎn)擊率預(yù)測(cè)，從而將發(fā)生點(diǎn)擊可能性最高的商品排在前面。

到這里還沒(méi)結(jié)束，推薦商品列表其實(shí)也是分展位的，有些位置的商品是運(yùn)營(yíng)配好的，有些位置固定展示的是廣告。廣告往往也有自己的一條鏈路，還有些位置有一些其他的邏輯。這些商品的數(shù)據(jù)都拿到了之后，還要獲取圖片以及其他一些零零散散的信息，最后才能展示出來(lái)。因此大家可以試一下打開(kāi)淘寶首頁(yè)要比打開(kāi)百度首頁(yè)慢得多，這并不是淘寶技術(shù)差，而是因?yàn)檫@中間的鏈路實(shí)在是太長(zhǎng)了。

我們很容易發(fā)現(xiàn)，對(duì)于一些經(jīng)常打開(kāi)淘寶的用戶來(lái)說(shuō)，其實(shí)沒(méi)有必要每一次都把完整的鏈路走一遍。我們大可以把之前展示的結(jié)果存儲(chǔ)在內(nèi)存里，下一次再遇到同樣請(qǐng)求的時(shí)候，直接從內(nèi)存當(dāng)中讀取并且返回就可以了。這樣可以節(jié)省大量的時(shí)間以及計(jì)算資源，比如在大促的時(shí)候，就可以把計(jì)算資源節(jié)省下來(lái)用在更加需要的地方。

緩存雖然好用，但是也不是萬(wàn)能的，因?yàn)閮?nèi)存是很貴的，我們不可能把所有數(shù)據(jù)都存在內(nèi)存里。內(nèi)存里只能放一些我們認(rèn)為比較高價(jià)值的數(shù)據(jù)，在這種情況下，計(jì)算科學(xué)家們想出了種種策略來(lái)調(diào)度緩存，保持緩存當(dāng)中數(shù)據(jù)的高價(jià)值。LRU就是其中一種比較常用的策略。

LRU含義

我們前面也說(shuō)了，LRU的意思是最長(zhǎng)不經(jīng)常使用，也可以理解成最久沒(méi)有使用。在這種策略下我們用最近一次使用的時(shí)間來(lái)衡量一塊內(nèi)存的價(jià)值，越久之前使用的價(jià)值也就越低，最近剛剛使用過(guò)的，后面接著會(huì)用到的概率也就越大，那么自然也就價(jià)值越高。

當(dāng)然只有這個(gè)限制是不夠的，我們前面也說(shuō)了，由于內(nèi)存是非常金貴的，導(dǎo)致我們可以存儲(chǔ)在緩存當(dāng)中的數(shù)據(jù)是有限的。比如說(shuō)我們固定只能存儲(chǔ)1w條，當(dāng)內(nèi)存滿了之后，緩存每插入一條新數(shù)據(jù)，都要拋棄一條最長(zhǎng)沒(méi)有使用的舊數(shù)據(jù)。這樣我們就保證了緩存當(dāng)中的數(shù)據(jù)的價(jià)值都比較高，并且內(nèi)存不會(huì)超過(guò)限制。

我們把上面的內(nèi)容整理一下，可以得到幾點(diǎn)要求：

1.保證緩存的讀寫(xiě)效率，比如讀寫(xiě)的復(fù)雜度都是O(1)

2.當(dāng)一條緩存當(dāng)中的數(shù)據(jù)被讀取，將它最近使用的時(shí)間更新

3.當(dāng)插入一條新數(shù)據(jù)的時(shí)候，彈出更新時(shí)間最遠(yuǎn)的數(shù)據(jù)

LRU原理

我們仔細(xì)想一下這個(gè)問(wèn)題會(huì)發(fā)現(xiàn)好像沒(méi)有那么簡(jiǎn)單，顯然我們不能通過(guò)數(shù)組來(lái)實(shí)現(xiàn)這個(gè)緩存。因?yàn)閿?shù)組的查詢速度是很慢的，不可能做到O(1)。其次我們用HashMap好像也不行，因?yàn)殡m然查詢的速度可以做到O(1)，但是我們沒(méi)辦法做到更新最近使用的時(shí)間，并且快速找出最遠(yuǎn)更新的數(shù)據(jù)。

如果是在面試當(dāng)中被問(wèn)到想到這里的時(shí)候，可能很多人都已經(jīng)束手無(wú)策了。但是先別著急，我們冷靜下來(lái)想想會(huì)發(fā)現(xiàn)問(wèn)題其實(shí)并沒(méi)有那么模糊。首先HashMap是一定要用的，因?yàn)橹挥蠬ashMap才可以做到O(1)時(shí)間內(nèi)的讀寫(xiě)，其他的數(shù)據(jù)結(jié)構(gòu)幾乎都不可行。但是只有HashMap解決不了更新以及淘汰的問(wèn)題，必須要配合其他數(shù)據(jù)結(jié)構(gòu)進(jìn)行。這個(gè)數(shù)據(jù)結(jié)構(gòu)需要能夠做到快速地插入和刪除，其實(shí)我這么一說(shuō)已經(jīng)很明顯了，只有一個(gè)數(shù)據(jù)結(jié)構(gòu)可以做到，就是鏈表。

鏈表有一個(gè)問(wèn)題是我們想要查詢鏈表當(dāng)中的某一個(gè)節(jié)點(diǎn)需要O(n)的時(shí)間，這也是我們無(wú)法接受的。但這個(gè)問(wèn)題并非無(wú)法解決，實(shí)際上解決也很簡(jiǎn)單，我們只需要把鏈表當(dāng)中的節(jié)點(diǎn)作為HashMap中的value進(jìn)行儲(chǔ)存即可，最后得到的系統(tǒng)架構(gòu)如下：

對(duì)于緩存來(lái)說(shuō)其實(shí)只有兩種功能，第一種功能就是查找，第二種是更新。

查找

查找會(huì)分為兩種情況，第一種是沒(méi)查到，這種沒(méi)什么好說(shuō)的，直接返回空即可。如果能查到節(jié)點(diǎn)，在我們返回結(jié)果的同時(shí)，我們需要將查到的節(jié)點(diǎn)在鏈表當(dāng)中移動(dòng)位置。我們假設(shè)越靠近鏈表頭部表示數(shù)據(jù)越舊，越靠近鏈表尾部數(shù)據(jù)越新，那么當(dāng)我們查找結(jié)束之后，我們需要把節(jié)點(diǎn)移動(dòng)到鏈表的尾部。

移動(dòng)可以通過(guò)兩個(gè)步驟來(lái)完成，第一個(gè)步驟是在鏈表上刪除該節(jié)點(diǎn)，第二個(gè)步驟是插入到尾部：

更新

更新也同樣分為兩種情況，第一種情況就是更新的key已經(jīng)在HashMap當(dāng)中了，那么我們只需要更新它對(duì)應(yīng)的Value，并且將它移動(dòng)到鏈表尾部。對(duì)應(yīng)的操作和上面的查找是一樣的，只不過(guò)多了一個(gè)更新HashMap的步驟，這沒(méi)什么好說(shuō)的，大家應(yīng)該都能想明白。

第二種情況就是要更新的值在鏈表當(dāng)中不存在，這也會(huì)有兩種情況，第一個(gè)情況是緩存當(dāng)中的數(shù)量還沒(méi)有達(dá)到限制，那么我們直接添加在鏈表結(jié)尾即可。第二種情況是鏈表現(xiàn)在已經(jīng)滿了，我們需要移除掉一個(gè)元素才可以放入新的數(shù)據(jù)。這個(gè)時(shí)候我們需要?jiǎng)h除鏈表的第一個(gè)元素，不僅僅是鏈表當(dāng)中刪除就可以了，還需要在HashMap當(dāng)中也刪除對(duì)應(yīng)的值，否則還是會(huì)占據(jù)一份內(nèi)存。

因?yàn)槲覀円M(jìn)行鏈表到HashMap的反向刪除操作，所以鏈表當(dāng)中的節(jié)點(diǎn)上也需要記錄下Key值，否則的話刪除就沒(méi)辦法了。刪除之后再加入新的節(jié)點(diǎn)，這個(gè)都很簡(jiǎn)單：

我們理順了整個(gè)過(guò)程之后來(lái)看代碼：

class Node:
  def __init__(self, key, val, prev=None, succ=None):
    self.key = key
    self.val = val
    # 前驅(qū)
    self.prev = prev
    # 后繼
    self.succ = succ

  def __repr__(self):
    return str(self.val)


class LinkedList:
  def __init__(self):
    self.head = Node(None, 'header')
    self.tail = Node(None, 'tail')
    self.head.succ = self.tail
    self.tail.prev = self.head

  def append(self, node):
    # 將node節(jié)點(diǎn)添加在鏈表尾部
    prev = self.tail.prev
    node.prev = prev
    node.succ = prev.succ
    prev.succ = node
    node.succ.prev = node

  def delete(self, node):
    # 刪除節(jié)點(diǎn)
    prev = node.prev
    succ = node.succ
    succ.prev, prev.succ = prev, succ

  def get_head(self):
    # 返回第一個(gè)節(jié)點(diǎn)
    return self.head.succ


class LRU:
  def __init__(self, cap=100):
    # cap即capacity，容量
    self.cap = cap
    self.cache = {}
    self.linked_list = LinkedList()


  def get(self, key):
    if key not in self.cache:
      return None

    self.put_recently(key)
    return self.cache[key]

  def put_recently(self, key):
    # 把節(jié)點(diǎn)更新到鏈表尾部
    node = self.cache[key]
    self.linked_list.delete(node)
    self.linked_list.append(node)

  def put(self, key, value):
    # 能查到的話先刪除原數(shù)據(jù)再更新
    if key in self.cache:
      self.linked_list.delete(self.cache[key])
      self.cache[key] = Node(key, value)
      self.linked_list.append(self.cache[key])
      return 

    if len(self.cache) >= self.cap:
      # 如果容量已經(jīng)滿了，刪除最舊的節(jié)點(diǎn)
      node = self.linked_list.get_head()
      self.linked_list.delete(node)
      del self.cache[node.key]

    u = Node(key, value)
    self.linked_list.append(u)
    self.cache[key] = u

網(wǎng)頁(yè)名稱：LRU緩存淘汰算法以及python實(shí)現(xiàn)的方法-創(chuàng)新互聯(lián)
當(dāng)前路徑：http://www.rwnh.cn/article38/cegopp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信公眾號(hào)、網(wǎng)頁(yè)設(shè)計(jì)公司、ChatGPT、動(dòng)態(tài)網(wǎng)站、企業(yè)建站、網(wǎng)站設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)