大家好，歡迎大家來到算法數(shù)據(jù)結(jié)構(gòu)專題，今天我們和大家聊一個非常常用的算法，叫做LRU。

LRU的英文全稱是Least Recently Used，也即最不經(jīng)常使用。我們看著好像挺迷糊的，其實(shí)這個含義要結(jié)合緩存一起使用。對于工程而言，緩存是非常非常重要的機(jī)制，尤其是在當(dāng)下的互聯(lián)網(wǎng)應(yīng)用環(huán)境當(dāng)中，起到的作用非常重要。為了便于大家更好地理解，我們從緩存的機(jī)制開始說起。

緩存

緩存的英文是cache，最早其實(shí)指的是用于CPU和主存數(shù)據(jù)交互的。早年這塊存儲被稱為高速緩存，最近已經(jīng)聽不到這個詞了，不知道是不是淘汰了。因為緩存的讀寫速度要高于CPU低于主存，所以是用來過渡數(shù)據(jù)用的。CPU從緩存當(dāng)中讀取數(shù)據(jù)，主存的數(shù)據(jù)也會先加載到緩存當(dāng)中來，之后再進(jìn)入CPU。

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

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

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

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

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

LRU含義

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

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

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

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

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

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

LRU原理

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

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

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

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

查找

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

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

更新

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

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

因為我們要進(jìn)行鏈表到HashMap的反向刪除操作，所以鏈表當(dāng)中的節(jié)點(diǎn)上也需要記錄下Key值，否則的話刪除就沒辦法了。刪除之后再加入新的節(jié)點(diǎn)，這個都很簡單：

我們理順了整個過程之后來看代碼：

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): # 返回第一個節(jié)點(diǎn) return self.head.succclass 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

在這種實(shí)現(xiàn)當(dāng)中我們沒有用除了dict之外的其他任何工具，連LinkedList都是自己實(shí)現(xiàn)的。實(shí)際上在Python語言當(dāng)中有一個數(shù)據(jù)結(jié)構(gòu)叫做OrderedDict，它是一個字典，但是它當(dāng)中的元素都是有序的。我們利用OrderedDict來實(shí)現(xiàn)LRU就非常非常簡單，代碼量也要少得多。

我們來看代碼：

class LRU(OrderedDict): def __init__(self, cap=128, /, *args, **kwds): self.cap = cap super().__init__(*args, **kwds) def __getitem__(self, key): # 查詢函數(shù) value = super().__getitem__(key) # 把節(jié)點(diǎn)移動到末尾 self.move_to_end(key) return value def __setitem__(self, key, value): # 更新函數(shù) super().__setitem__(key, value) if len(self) > self.cap: oldest = next(iter(self)) del self[oldest]

在上面一種實(shí)現(xiàn)當(dāng)中由于只用了一個數(shù)據(jù)結(jié)構(gòu)，所以整個代碼要簡潔許多。使用起來也更加方便，直接像是dict一樣使用方括號進(jìn)行查詢以及更新就可以了。不過在其他語言當(dāng)中可能沒有OrderedDict這種數(shù)據(jù)結(jié)構(gòu)，這就需要我們自己來編碼實(shí)現(xiàn)了。

好了，今天的文章就到這里。衷心祝愿大家每天都有所收獲。如果還喜歡今天的內(nèi)容的話，請來一個三連支持吧~（點(diǎn)贊、關(guān)注、轉(zhuǎn)發(fā)）

以上就是工程師必須了解的LRU緩存淘汰算法以及python實(shí)現(xiàn)過程的詳細(xì)內(nèi)容，更多關(guān)于LRU緩存淘汰算法的資料請關(guān)注好吧啦網(wǎng)其它相關(guān)文章！