這幾天我一直在研究 Python 的 collections 模組。裡面的工具非常豐富，但也容易讓人迷失。今天，我們將深入探討一個特別有用的資料結構：OrderedDict，並且藉由 Leetcode 第 146 題 LRU Cache 的範例，來展示它的應用。

問題背景：什麼是 LRU Cache？

在了解 OrderedDict 之前，讓我們先來看看 Leetcode 第 146 題：LRU Cache。LRU 代表 "Least Recently Used"（最近最少使用），這個問題要求設計一個具有固定容量的快取系統，當快取容量達到上限時，會移除最近最少使用的元素，以便插入新的資料。

具體來說，LRU Cache 支持兩個操作：

1. get(key) - 如果 key 存在於快取中，返回該值，否則返回 -1，並且每次 get 都應將該項目標記為最近使用過的。
2. put(key, value) - 插入新項目，如果快取已滿，則應移除最近最少使用的項目。

這個問題挑戰的是如何有效地管理最近使用的項目，同時保持快取操作的時間複雜度在 O(1)。

介紹 OrderedDict

Python 的 OrderedDict 是 collections 模組中的一個特別類別，它擴展了標準的字典，但有一個額外的特性：它記錄了元素插入的順序。這使得 OrderedDict 成為解決 LRU Cache 問題的天然選擇，因為我們可以輕鬆追蹤每個元素的使用順序，並且在需要時快速移除最早插入的元素。

與普通的字典不同，OrderedDict 可以讓你：

• 按照插入順序遍歷鍵值對。
• 輕鬆地刪除或移動最近使用或最早插入的元素。

例如，使用 popitem(last=False) 方法，我們可以移除並返回最早插入的元素，這在實現 LRU Cache 時非常有用。

使用 OrderedDict 實現 LRU Cache

現在，我們來看看如何使用 OrderedDict 來解決 LRU Cache 問題：

from collections import OrderedDict

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        else:
            # 移動該項目到字典的尾部，表示最近使用過
            self.cache.move_to_end(key)
            return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # 更新現有項目的值，並移動到尾部
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            # 刪除最早的項目，即最近最少使用的
            self.cache.popitem(last=False)

這段代碼展示了如何藉助 OrderedDict 來實現 LRU Cache。以下是實現細節的簡要說明：

1. 初始化：我們創建一個 OrderedDict 作為快取，並記錄容量 capacity。
2. get(key) 操作：我們檢查 key 是否存在於快取中。如果存在，我們使用 move_to_end 方法將該項目移動到字典尾部，以標記為最近使用過的元素，然後返回對應的值。否則，返回 -1。
3. put(key, value) 操作：首先檢查 key 是否已經存在於快取中。如果存在，我們更新其值並將其移到尾部。接著，我們插入新項目。如果此時快取的大小超過了容量，我們使用 popitem(last=False) 移除最早插入的元素。

結語

OrderedDict 提供了一個方便的方法來處理需要保持插入順序的場景，特別適合於像 LRU Cache 這樣的應用。它讓我們能夠有效地管理快取中的項目，並以 O(1) 的時間複雜度實現最近最少使用的邏輯。藉由這個問題，我們可以更深入地理解 Python 中資料結構的靈活性與實用性。