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

向右看齐 2021-10-01 03:26 426阅读 0赞

## 关于LRU算法 ##

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5nbGVpMzA1_size_16_color_FFFFFF_t_70][]

## 使用双向链表实现LRU ##

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5nbGVpMzA1_size_16_color_FFFFFF_t_70 1][]

## 具体实现 ##

（代码中引入的双向链表-->[https://blog.csdn.net/huanglei305/article/details/99422314][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][https_blog.csdn.net_huanglei305_article_details_99318328]

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

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

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5nbGVpMzA1_size_16_color_FFFFFF_t_70]: /images/20210923/88c17367113a4874996fee4b7e386a93.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5nbGVpMzA1_size_16_color_FFFFFF_t_70 1]: /images/20210923/4455fbda9f5f4fb69adaf573db5aa5f7.png
[https_blog.csdn.net_huanglei305_article_details_99422314]: https://blog.csdn.net/huanglei305/article/details/99422314
[https_blog.csdn.net_huanglei305_article_details_99318328]: https://blog.csdn.net/huanglei305/article/details/99318328
[https_blog.csdn.net_huanglei305_article_details_99424177]: https://blog.csdn.net/huanglei305/article/details/99424177
[https_blog.csdn.net_huanglei305_article_details_99428409]: https://blog.csdn.net/huanglei305/article/details/99428409