LeetCode 筆記 - 146. LRU Cache

Posted on 標籤
解析如何實作具備最近最少使用（LRU）機制的快取系統。本文探討 Python 中 OrderedDict 的應用，並分享一個提升字典鍵值檢查效率的「奇技淫巧」，顯著優化執行速度。這是一篇兼具資料結構原理與 Python 效能優化的心得。
⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 146. LRU Cache

請實作 LRU Cache

解題思維

這題基本上就是 OrderedDict 的主戰場
筆者本著學習的心自幹了一個，過了但就是慢…(Faster than 10 % QQ

這裡有個奇技淫巧是 key in dict.keys() 比平常使用的 key in dict 快很多
只要簡單的改動一下，執行速度大幅提升 😲

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = collections.OrderedDict()

    def get(self, key: int) -> int:
        
        if key not in self.cache.keys():
            return -1
        
        self.cache.move_to_end(key)
        value = self.cache[key]
        
        return value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache.keys() and len(self.cache.keys()) >= self.capacity:
            self.cache.popitem(last=False)
        self.cache[key] = value
        self.cache.move_to_end(key)

也許你也會想看看