Python实现LRU算法

在第一节中已经实现了双向链表DoubleLinkedList类，本节我们基于双向链表实现LRU（Least Recently Used最近最少使用）缓存置换算法。Redis的淘汰机制就包括LRU算法，用来淘汰那些最近最少使用的数据，具体怎么使用可在redis的配置文件中设置。

一、LRU算法的实现

逻辑很简单，get和put两种操作，其中get时如果元素存在则将节点从当前位置移到链表头部，表示最近被访问到的节点；put时也是，不管节点之前存不存在都要移动到链表头部。同样通过一个map来实现查找时的O(1)复杂度。

class LRUCache(object):

    def __init__(self, capacity=0xffffffff):
        """
        LRU缓存置换算法 最近最少使用
        :param capacity:
        """
        self.capacity = capacity
        self.size = 0
        self.map = {}
        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)
        self.list.remove(node)
        self.list.append_front(node)

        return node.value

    def put(self, key, value):
        """
        添加元素
            被添加的元素已存在 更新元素值并已到链表头部
            被添加的元素不存在
                链表容量达到上限 删除尾部元素
                链表容量未达上限 添加至链表头部
        :param key:
        :param value:
        :return:
        """
        if key in self.map:
            node = self.map.get(key)
            node.value = value
            self.list.remove(node)
            self.list.append_front(node)
        else:
            if self.size >= self.capacity:
                old_node = self.list.remove()
                del self.map[old_node.key]
                self.size -= 1

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

        return node

    def print(self):
        """
        打印当前链表
        :return:
        """
        self.list.print()

二、测试逻辑

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

测试结果:

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • 工程师必须了解的LRU缓存淘汰算法以及python实现过程

    大家好,欢迎大家来到算法数据结构专题,今天我们和大家聊一个非常常用的算法,叫做LRU. LRU的英文全称是Least Recently Used,也即最不经常使用.我们看着好像挺迷糊的,其实这个含义要结合缓存一起使用.对于工程而言,缓存是非常非常重要的机制,尤其是在当下的互联网应用环境当中,起到的作用非常重要.为了便于大家更好地理解,我们从缓存的机制开始说起. 缓存 缓存的英文是cache,最早其实指的是用于CPU和主存数据交互的.早年这块存储被称为高速缓存,最近已经听不到这个词了,不知道是不是

  • Python 的lru_cache装饰器使用简介

    Python 的lru_cache装饰器使用简介

    Python 的 lru_cache 装饰器是一个为自定义函数提供缓存功能的装饰器.其内部会在下次以相同参数调用该自定义函数时直接返回计算好的结果.通过缓存计算结果可以很好地提升性能. 1 从示例说起 假设我们有一个计算斐波那契数列的求和函数,其内部采用递归方式实现. from xxx.clock_decorator import clock @clock def fibonacci(n): if n<2: return n return fibonacci(n-2)+fibonacci(n-1

  • Python实现LRU算法的2种方法

    LRU:least recently used,最近最少使用算法.它的使用场景是:在有限的空间中存储对象时,当空间满时,会按一定的原则删除原有的对象,常用的原则(算法)有LRU,FIFO,LFU等.在计算机的Cache硬件,以及主存到虚拟内存的页面置换,还有Redis缓存系统中都用到了该算法.我在一次面试和一个笔试时,也遇到过这个问题. LRU的算法是比较简单的,当对key进行访问时(一般有查询,更新,增加,在get()和set()两个方法中实现即可)时,将该key放到队列的最前端(或最后端)就

  • python自带缓存lru_cache用法及扩展的使用

    目录 1. lru_cache的使用 1.1 参数详解 1.2 基本用法 1.3 进阶用法 2. functiontools.wrap装饰器对lru_cache的影响 2.1 多个装饰器装饰同一函数时的执行顺序 2.2 functiontools.wrap原理 2.3 使用wrap装饰器前后的变化 3. 自制简易的my_cache 3.1 lru_cache提供的功能 3.2 cache的核心部件 3.3 my_cache的实现 4. lru_cache缓存和redis缓存的区别 5. 总结 本

  • Python中lru_cache的使用和实现详解

    在计算机软件领域,缓存(Cache)指的是将部分数据存储在内存中,以便下次能够更快地访问这些数据,这也是一个典型的用空间换时间的例子.一般用于缓存的内存空间是固定的,当有更多的数据需要缓存的时候,需要将已缓存的部分数据清除后再将新的缓存数据放进去.需要清除哪些数据,就涉及到了缓存置换的策略,LRU(Least Recently Used,最近最少使用)是很常见的一个,也是 Python 中提供的缓存置换策略. 下面我们通过一个简单的示例来看 Python 中的 lru_cache 是如何使用的.

  • Python 如何手动编写一个自己的LRU缓存装饰器的方法实现

    LRU缓存算法,指的是近期最少使用算法,大体逻辑就是淘汰最长时间没有用的那个缓存,这里我们使用有序字典,来实现自己的LRU缓存算法,并将其包装成一个装饰器. 1.首先创建一个my_cache.py文件 编写自己我们自己的LRU缓存算法,代码如下: import time from collections import OrderedDict ''' 基于LRU,近期最少用缓存算法写的装饰器. ''' class LRUCacheDict: def __init__(self, max_size=

  • Python中缓存lru_cache的基本介绍和讲解

    目录 一.前言 二.举例说明 三.lru_cache 用法 1.参数详解 2. lru_cache不支持可变参数 四.lru_cache 与redis的区别 五.总结 一.前言 我们经常谈论的缓存一词,更多的类似于将硬盘中的数据存放到内存中以至于提高读取速度,比如常说的redis,就经常用来做数据的缓存.Python的缓存(lru_cache)是一种装饰在被执行的函数上,将其执行的结果缓存起来,当下次请求的时候,如果请求该函数的传参未变则直接返回缓存起来的结果而不再执行函数的一种缓存装饰器. 那

  • python实现LRU热点缓存及原理

    LRU LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是"如果数据最近被访问过,那么将来被访问的几率也更高". 基于列表+Hash的LRU算法实现. 访问某个热点时,先将其从原来的位置删除,再将其插入列表的表头 为使读取及删除操作的时间复杂度为O(1),使用hash存储热点的信息的键值 class LRUCaceh(): def __init__(self, size=5): ''' 默认队列的长度为5 使用列表来维护

  • LRUCache的实现原理及利用python实现的方法

    简介 LRU(Least Recently Used)最近最少使用,最近有时间和空间最近的歧义,所以我更喜欢叫它近期最少使用算法.它的核心思想是,如果一个数据被访问过,我们有理由相信它在将来被访问的概率就越高.于是当LRU缓存达到设定的最大值时将缓存中近期最少使用的对象移除.LRUCache内部使用LinkedHashMap来存储key-value键值对,并将LinkedHashMap设置为访问顺序来体现LRU算法. 无论是对某个key的get,还是set都算做是对该key的一次使用.当set一

  • Python实现的一个简单LRU cache

    起因:我的同事需要一个固定大小的cache,如果记录在cache中,直接从cache中读取,否则从数据库中读取.python的dict 是一个非常简单的cache,但是由于数据量很大,内存很可能增长的过大,因此需要限定记录数,并用LRU算法丢弃旧记录.key 是整型,value是10KB左右的python对象 分析: 1)可以想到,在对于cache,我们需要维护 key -> value 的关系 2)而为了实现LRU,我们又需要一个基于时间的优先级队列,来维护   timestamp  ->

随机推荐