常見的緩存機制

LRU Cache

Least Recently Used鸵荠，在操作系統(tǒng)里是一種常用的頁面置換算法，置換策略即伤极，選擇最近最久未使用的頁面予以淘汰

LeetCode - 146.LRU Cache

link: https://leetcode-cn.com/problems/lru-cache/

中文題目

運用你所掌握的數(shù)據(jù)結(jié)構(gòu)腰鬼，設(shè)計和實現(xiàn)一個 LRU (最近最少使用) 緩存機制 。
實現(xiàn) LRUCache 類：

LRUCache(int capacity) 以正整數(shù)作為容量 capacity 初始化 LRU 緩存
int get(int key) 如果關(guān)鍵字 key 存在于緩存中塑荒，則返回關(guān)鍵字的值熄赡，否則返回 -1 。
void put(int key, int value) 如果關(guān)鍵字已經(jīng)存在齿税，則變更其數(shù)據(jù)值彼硫；如果關(guān)鍵字不存在，則插入該組「關(guān)鍵字-值」凌箕。當(dāng)緩存容量達(dá)到上限時拧篮，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間牵舱。

進(jìn)階：你是否可以在 O(1) 時間復(fù)雜度內(nèi)完成這兩種操作串绩？

Example

輸入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
輸出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解釋
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 緩存是 {1=1}
lRUCache.put(2, 2); // 緩存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 該操作會使得關(guān)鍵字 2 作廢，緩存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 該操作會使得關(guān)鍵字 1 作廢芜壁，緩存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

Note:

1. 1 <= capacity <= 3000
2. 0 <= key <= 3000
3. 0 <= value <= 104
4. 最多調(diào)用 3 * 104 次 get 和 put

問題描述

需要實現(xiàn)一個LRU緩存礁凡，需要保證時間復(fù)雜度是O(1)

題目分析

數(shù)據(jù)結(jié)構(gòu)分析

• 根據(jù)LRU Cache的定義高氮，實際的替換原則就是將最久未使用過的元素置換出去
• 既然涉及到key和value，需要快速在O(1)時間內(nèi)快速查找數(shù)據(jù)顷牌，那就得用到hash數(shù)據(jù)結(jié)構(gòu)
• 需要將最新使用的數(shù)據(jù)放到最前剪芍，最久未使用的數(shù)據(jù)放后面，這就是個鏈表結(jié)構(gòu)
• 當(dāng)數(shù)據(jù)容量滿了的時候窟蓝，需要將最久未使用的數(shù)據(jù)罪裹，也就是鏈表最后一個數(shù)據(jù)刪掉，那這就需要用到雙端鏈表运挫，且需要支持雙向查找状共，因此節(jié)點的數(shù)據(jù)結(jié)構(gòu)需要選用帶有雙端的雙向鏈表
• 為此，我們可以創(chuàng)建一個偽head和偽tail谁帕，用于指向第一個和最后一個節(jié)點
• 為了get操作在O(1)時間內(nèi)完成口芍，我們可以在hash里直接對節(jié)點進(jìn)行索引，這樣就能根據(jù)key快速定位節(jié)點在鏈表中的位置及前后關(guān)系

操作過程分析

• 對于get操作
  • 如果key在dict中雇卷，那我們需要將節(jié)點從原本位置移動到第一個節(jié)點處鬓椭，也就是head的指向
  • 如果key不在dict中，那我們直接按題意返回-1即可
• 對于put操作
  • 如果key在dict中关划，那么我們同get時一樣小染，直接移動到第一個節(jié)點處即可，此時需要注意的是贮折，value值可能被覆蓋裤翩，所以對節(jié)點的value需要重新賦值
  • 如果key不在dict中，那就需要進(jìn)行添加操作了调榄，當(dāng)然這個節(jié)點是最近剛使用的踊赠，那么一定是在第一個節(jié)點位置
  • 當(dāng)新的節(jié)點被添加進(jìn)來時，由于cache是有容量限制的每庆，因此需要將最久未使用的那個數(shù)據(jù)移除掉筐带，也就是最后一個節(jié)點相關(guān)數(shù)據(jù)
• 其它
  • 為了調(diào)試，我寫了個visit方法缤灵，這個方法可以遍歷鏈表伦籍，輸出中間結(jié)果

代碼實現(xiàn)

Python3 實現(xiàn)

class Node(object):
    def __init__(self, key = 0, value = 0):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None


class LRUCache:
    def visit(self):
        result = []
        p = self.head.next
        while p and p != self.tail:
            result.append(str(p.value))
            p = p.next
        # print('->'.join(result))

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.move_node_to_head(node)
        # self.visit()
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self.move_node_to_head(node)
        else:
            node = Node(key, value)
            self.add_to_head(node)
            self.cache[key] = node
            if len(self.cache) <= self.capacity:
                pass
            else:
                last_node = self.remove_tail_node()
                self.cache.pop(last_node.key)
        # self.visit()

    def remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def add_to_head(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def move_node_to_head(self, node):
        self.remove_node(node)
        self.add_to_head(node)

    def remove_tail_node(self):
        node = self.tail.prev
        node.prev.next = self.tail
        self.tail.prev = node.prev
        return node
            

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

運行結(jié)果

執(zhí)行結(jié)果：

通過

顯示詳情

執(zhí)行用時：168 ms, 在所有 Python3 提交中擊敗了78.98%的用戶

內(nèi)存消耗：23.7 MB, 在所有 Python3 提交中擊敗了14.51%的用戶