Source: LRU Cache (LeetCode: 146)

Design and implement a data structure for LRU (Least Recently Used) cache. It should support the following operations: get and set.

  1. get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
  2. set(key, value) – Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least recently used item before inserting the new item.

The LRU Cache will be initialized with an integer corresponding to its capacity. Capacity indicates the maximum number of unique keys it can hold at a time.

Definition of “least recently used” : An access to an item is defined as a get or a set operation of the item. “Least recently used” item is the one with the oldest access time.

NOTE: If you are using any global variables, make sure to clear them in the constructor.

Example :

Input : 
         capacity = 2
         set(1, 10)
         set(5, 12)
         get(5)        returns 12
         get(1)        returns 10
         get(10)       returns -1
         set(6, 14)    this pushes out key = 5 as LRU is full. 
         get(5)        returns -1

這題好像沒什麼好特別解說的，就是依據題目來設計程式碼。偷吃一點可以用前人寫好的 collections.deque 或是 collections.OrderedDict 來簡化程序。須要特別注意的是 get 這個函式如果有成功呼叫的話也必須更新資料新舊度並調整排序。

一開始筆者是另外用一個陣列來儲存當前在字典裡的所有 key 值，但若出現在 set 更新現有值以及 get 調整新舊度排序時就必須執行 list.remove(key) ，其需要從整個陣列中搜尋該 key 值，複雜度為 O(n)，較無效率。後來筆者改為用三個字典來分別儲存 key-value, key-order, order-key 這三組資訊，如此一來在進行更新時都可以直接採用 dict.pop(key) 來加快處理速度 （O(1)）。但用這方式在長度超過容量時就需要找當前的最大order值，這部分可能要視題目給的容量限制大小以及呼叫次數的多寡來決定是要用遞減的方式在 while 迴圈內找，或是直接採用 max(dict.values())。
筆者是採用 while 迴圈，直接算最大值是否會比較快就留待有興趣的人自行研究了，筆者的方法在 LeetCode 上速度是 Python3 的前 25% 以內，應該可以算是還蠻不錯了啦。

Code:

class LRUCache:

    def __init__(self, capacity):
        self.pairs = dict()
        self.capacity = capacity
        #recording command orders
        self.orderKey = dict()
        self.keyOrder = dict()
        self.orderNum = 10000
        self.orderLimit = 10000

    def get(self, key):
        try:
            v = self.pairs[key]
            self.orderKey.pop(self.keyOrder.pop(key))
            self.keyOrder[key] = self.orderNum
            self.orderKey[self.orderNum]  = key
            self.orderNum -= 1
            return v
        except:
            return -1

    def set(self, key, value):
        try:
            self.pairs.pop(key)
            self.orderKey.pop(self.keyOrder.pop(key))
        except:
            if len(self.pairs) >= self.capacity:
                while True:
                    keyToDrop = self.orderKey.pop(self.orderLimit, -1)
                    self.orderLimit -= 1
                    if keyToDrop == -1: continue
                    self.pairs.pop(keyToDrop)
                    self.keyOrder.pop(keyToDrop)
                    break
        self.pairs[key] = value
        self.keyOrder[key] = self.orderNum
        self.orderKey[self.orderNum]  = key
        self.orderNum -= 1

GitHub: GitHub

發表留言