实现LRU缓存置换算法（Python）

关于LRU算法

如下图，假设缓存4个子块，（）表示使用的字块，[]表示淘汰的字块。

使用双向链表实现LRU

淘汰缓存时，把链表尾部的节点淘汰。

具体实现

（代码中引入的双向链表-->https://blog.csdn.net/huanglei305/article/details/99422314）

# -*- encoding=utf-8 -*-


from computer_principle.DoubleLinkedList import DoubleLinkedList, Node


class LRUCache(object):

    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.list = DoubleLinkedList(self.capacity)

    def get(self, key):
        if key in self.map:
            node = self.map[key]
            self.list.remove(node)
            self.list.append_front(node)
            return node.value
        else:
            return -1

    def put(self, key, value):
        if key in self.map:
            node = self.map.get(key)
            self.list.remove(node)
            node.value = value
            self.list.append_front(node)
        else:
            node = Node(key, value)
            # 缓存已经满了
            if self.list.size >= self.list.capacity:
                old_node = self.list.remove()
                self.map.pop(old_node.key)

            self.list.append_front(node)
            self.map[key] = node

    def print(self):
        self.list.print()


if __name__ == '__main__':
    cache = LRUCache(2)
    cache.put(2, 2)
    cache.print()
    cache.put(1, 1)
    cache.print()
    cache.put(3, 3)
    cache.print()
    print(cache.get(1))
    cache.print()
    print(cache.get(2))
    cache.print()
    print(cache.get(3))
    cache.print()

相关推荐：

计算机组成原理核心知识点https://blog.csdn.net/huanglei305/article/details/99318328

实现双向链表（Python）https://blog.csdn.net/huanglei305/article/details/99422314

实现FIFO缓存置换算法（Python）https://blog.csdn.net/huanglei305/article/details/99424177

实现LFU缓存置换算法（Python）https://blog.csdn.net/huanglei305/article/details/99428409