Python實現(xiàn)FIFO緩存置換算法

更新時間：2022年05月25日 13:20:03 作者：旺旺小小超

這篇文章主要為大家詳細介紹了Python實現(xiàn)FIFO（先進先出）緩存置換算法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

本文實例為大家分享了Python實現(xiàn)FIFO緩存置換算法的具體代碼，供大家參考，具體內(nèi)容如下

在上一節(jié)中我們實現(xiàn)了雙向鏈表DoubleLinkedList類，本節(jié)我們基于雙向鏈表實現(xiàn)FIFO（先進先出）緩存置換算法。

一、FIFO實現(xiàn)

代碼邏輯很簡單，就是遵循先進先出的原則，具體流程都寫在注釋中了。通過一個map來實現(xiàn)查找時的O(1)復(fù)雜度

class FIFOCache(object):

? ? def __init__(self, capacity=0xffffffff):
? ? ? ? """
? ? ? ? FIFO緩存置換算法
? ? ? ? :param capacity:
? ? ? ? """
? ? ? ? self.capacity = capacity
? ? ? ? self.map = {}
? ? ? ? self.size = 0
? ? ? ? self.list = DoubleLinkedList(capacity)

? ? def get(self, key):
? ? ? ? """
? ? ? ? 獲取元素
? ? ? ? ? ? 不存在 返回None
? ? ? ? ? ? 已存在 則返回緩存值
? ? ? ? :param key:
? ? ? ? :return:
? ? ? ? """
? ? ? ? # 當前緩存中不存在
? ? ? ? if key not in self.map:
? ? ? ? ? ? return None

? ? ? ? # 當前緩存中存在
? ? ? ? node = self.map.get(key)

? ? ? ? return node.value

? ? def put(self, key, value):
? ? ? ? """
? ? ? ? 添加元素
? ? ? ? ? ? 已存在 更新值并添加至鏈表尾部
? ? ? ? ? ? 不存在 判斷緩存容量大小后添加
? ? ? ? :param key:
? ? ? ? :param value:
? ? ? ? :return: 已添加的節(jié)點
? ? ? ? """
? ? ? ? # 當前緩存中已存在
? ? ? ? if key in self.map:
? ? ? ? ? ? node = self.map.get(key)
? ? ? ? ? ? self.list.remove(node)
? ? ? ? ? ? node.value = value
? ? ? ? ? ? self.list.append(node)
? ? ? ? else:
? ? ? ? ? ? # 緩存容量達到上限 刪除頭結(jié)點
? ? ? ? ? ? if self.size >= self.capacity:
? ? ? ? ? ? ? ? old_node = self.list.pop()
? ? ? ? ? ? ? ? del self.map[old_node.key]
? ? ? ? ? ? ? ? self.size -= 1

? ? ? ? ? ? node = Node(key, value)
? ? ? ? ? ? self.map[key] = node
? ? ? ? ? ? self.list.append(node)
? ? ? ? ? ? self.size += 1

? ? ? ? return node

? ? def print(self):
? ? ? ? """
? ? ? ? 打印當前鏈表
? ? ? ? :return:
? ? ? ? """
? ? ? ? self.list.print()
? ? ? ? # print(self.map)

二、測試邏輯

if __name__ == '__main__':
? ? fifo_cache = FIFOCache(2)
? ? fifo_cache.put(1, 1)
? ? fifo_cache.print()
? ? fifo_cache.put(2, 2)
? ? fifo_cache.print()
? ? print(fifo_cache.get(2))
? ? fifo_cache.put(3, 3)
? ? fifo_cache.print()
? ? print(fifo_cache.get(1))
? ? fifo_cache.put(2, 4)
? ? fifo_cache.print()

測試結(jié)果: