LRU算法在後端工程師面試中，是一個比較常出現的題目，這篇文章帶大家一起，理解LRU算法，並最終用Python輕鬆實現一個基於LRU算法的緩存。
緩存是什麼
先看一張圖，當我們訪問網頁，瀏覽器會給伺服器發請求，伺服器會經過一系列的運算，把頁面返回給瀏覽器。
當有多個瀏覽器同時訪問的時候，就會在短時間內發起多個請求，而伺服器對每一個請求都要進行一系列相同的操作。重複工作不僅浪費資源，還可能導致響應速度變慢。
而緩存則可以把伺服器返回的頁面保存下來，當有其他的瀏覽器再訪問時候，就不必勞伺服器大駕，直接由緩存返回頁面。為了保證響應速度，緩存通常是基於比較昂貴的硬體，比如RAM，這就決定了我們很難用大量的緩存把所有的頁面都存下來，當恰好沒有緩存瀏覽器請求的頁面時，依然需要請求伺服器。由於緩存容量有限，而數據量無限（網際網路每天新產生的頁面數無法估計），就需要把好剛用在刀刃上，緩存那些最有用的信息。
LRU是什麼
LRU是一種緩存淘汰算法（在OS中也叫內存換頁算法），由於緩存空間是有限的，所以要淘汰緩存中不常用的數據，留下常用的數據，達到緩存效率的最大化。LRU就是這樣一種決定「淘汰誰留下誰」的算法，LRU是Least recently used的縮寫，從字面意思「最近最少使用」，我們就可以理解LRU的淘汰規則。
LRU的淘汰邏輯
我們用一張圖來描述LRU的淘汰邏輯，圖中的緩存是一個列表結構，上面是頭結點下面是尾節點，緩存容量為8（8個小格子）：
有新數據（意味著數據之前沒有被緩存過）時，加入到列表頭緩存到達最大容量時，需要淘汰數據多出來的數據，此時淘汰列表尾部的數據當緩存中有數據被命中，則將數據移動到列表頭部（相當於新加入緩存）按上面的邏輯我們可以看到，一個數據如果經常被訪問就會不斷地被移動到列表頭部，不會被淘汰出緩存，而越不經常訪問的數據，越容易被擠出緩存。
對想學習Python的小夥伴，小編給你們準備了全套Python電子版書籍，包含了目前大部分Python軟體開發的書領取方式，先關注小編，然後私信「Python」，就能獲取全套書籍，你還不心動嗎？心動就趕緊發私信 ，獲取資源還有一個交流學習的好地方
【私信方法】文章上方處點擊「作者頭像」，進入作者首頁，右上角點擊「發私信」 即可
20行Python代碼實踐LRU
接下來我們用Python來實現一個採用LRU算法的緩存。
從前面的文章中我們可以知道，緩存簡化下來就兩個功能，一個是往裡裝數據（緩存數據），一個是往外吐數據（命中緩存），所以我們的緩存對外只需要put和get兩個接口就可以了。
按照前面的示意圖，緩存內部我們只需要有一個列表（list）就可以實現LRU邏輯，不過用列表雖然能實現邏輯，但是在判斷是否命中緩存時，速度可能非常慢（列表需要遍歷才能知道數據有沒有在裡面）。在Python中，我們可以用基於hash的結構，比如字典（dict）或集合（set），來快速判斷數據是否存在，解決列表實現的性能問題。但是字典和集合又是沒有順序的，如果能有一種既能排序，又是基於hash存儲的數據結構，就好了。
在Python的collections包中，已經內置了這種實用的結構OrderedDict，OrderedDict是dict的子類，但是存儲在內部的元素是有序的（列表的特點）。
解決了數據結構的問題，我們可以直接上手寫邏輯了，代碼如下：
class LRUCache:def __init__(self, capacity): self.capacity = capacity self.queue = collections.OrderedDict() def get(self, key): if key not in self.queue: return -1 // 要找的數據不在緩存中返回-1 value = self.queue.pop(key) // 將命中緩存的數據移除 self.queue[key] = value // 將命中緩存的數據重新添加到頭部 return self.queue[key] def put(self, key, value): if key in self.queue: // 如果已經在緩存中，則先移除老的數據 self.queue.pop(key) elif len(self.queue.items()) == self.capacity: self.queue.popitem(last=False) // 如果不在緩存中並且到達最大容量，則把最後的數據淘汰 self.queue[key] = value // 將新數據添加到頭部
下次面試在遇到LRU的題目，是不是就胸有成竹了？
喜歡這篇文章，歡迎關注小編