文档章节

LRUCache LeetCode OJ

JoshuaShaw
 JoshuaShaw
发布于 2015/09/09 19:58
字数 215
阅读 16
收藏 0
# LRUCache

class DictMap:
    def __init__(self):
        self.dict = {}
        self.size = 0
    def set(self, key, value):
        self.size+=1
        self.dict[key] = value
    def get(self, key):
        value = None
        if(self.containKey(key)):
            value = self.dict[key]
        return value
    def remove(self, key):
        del self.dict[key]
        self.size-=1
    def containKey(self, key):
        try:
            self.dict[key]
            return True
        except:
            return False

class Entry:
    def __init__(self, k, v):
        self.k = k
        self.v = v
        self.pre = None
        self.next = None
        

class LRUCache(object):

    def __init__(self, capacity):
        self.c = capacity
        self.m = DictMap()
        self.head = Entry(-1, -1)
        self.tail = Entry(1, 1)
        self.head.next = self.tail
        self.tail.pre = self.head
        

    def get(self, key):
        if(self.m.containKey(key)):
            e = self.m.get(key)
            self.__moveToHead(e)
            return e.v
        else:
            return -1
        

    def set(self, key, value):
        if(self.m.containKey(key)):
            e = self.m.get(key)
            e.v = value
            self.__moveToHead(e)
        elif(self.m.size<self.c):
            e = Entry(key, value)
            self.__moveToHead(e)
            self.m.set(key, e)
        else:
            e = Entry(key, value)
            self.__moveToHead(e)
            self.m.set(key, e)
            index = self.__removeEnd()
            self.m.remove(index)


    def __removeEnd(self):
        e = self.tail.pre
        self.tail.pre.pre.next = self.tail
        self.tail.pre = e.pre
        e.pre = None
        e.next = None
        return e.k

    def __moveToHead(self, e):
        if(e.next!=None and e.pre!=None):
            e.pre.next = e.next
            e.next.pre = e.pre
        e.pre = self.head
        e.next = self.head.next
        self.head.next.pre = e
        self.head.next = e


© 著作权归作者所有

JoshuaShaw
粉丝 5
博文 27
码字总数 15604
作品 0
湛江
程序员
私信 提问
LruCache在美团DSP系统中的应用演进

背景 DSP系统是互联网广告需求方平台,用于承接媒体流量,投放广告。业务特点是并发度高,平均响应低(百毫秒)。 为了能够有效提高DSP系统的性能,美团平台引入了一种带有清退机制的缓存结构...

美团技术团队
2018/12/24
0
0
安卓图片的异步请求及使用LruCache缓存和手机内存两层存储图片,避免重新加载页面带来的重新请求

看到网友的一片技术博客讲解了LruCache的使用,我把它加到了我的项目中,但是加入断点发现,列表上下滑动时,确实可以不用重新加载图片,但是重新打开这个activity或者重新启动应用,LruCach...

bluecoffee
2015/04/03
0
0
Android内存优化之内存缓存

什么是缓存? 缓存技术原理就是把用户访问的所有对象看作一个全集,经过算法标记哪些是用户经常访问的对象,把这些对象放到一个集合里,这个集合是全集一个子集,下一次用户再访问的时候会先...

今晚打猴子
2015/08/21
0
0
Android LRUCache原理及使用(对象软引用不行,使用LRU算法)

> 对象软引用,弱引用 A a = new A(); SoftReference sr = new SoftReference(a); a = sr.get(); > LRUCache原理及使用 在Android中采用LRU算法的常用缓存有两种:LruCache和DisLruCache,分......

desaco
01/25
0
0
为什么Android官方废弃SoftRefrerence软引用和WeakReference弱引用,而拥抱LruCache?

为什么Android官方废弃SoftRefrerence软引用和WeakReference弱引用,而拥抱LruCache? 一些具有Java背景的研发者喜欢使用软引用(SoftRefrerence)和弱引用(WeakReference)来缓存Java对象和数据...

开开心心过
2018/06/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

mysql报错 [ERROR] Fatal error: Can't open and lock privilege tables: Table 'mysql.host' doesn't exist

CentOS 6.5 下安装配置 mysql 使用yum安装,具体过程参见最下边的参考文章。 安装之后启动失败: [root@localhost ~]# service mysqld startStarting mysqld: ...

BG2KNT
13分钟前
1
0
IOC的学习(1)

IOC IOC创建bean的4种方式: 无参构造器, 有参构造器,其中<constructor-arg>可以通过index="0"或者type="int"来指定构造方法参数。 静态工厂方法,factory-method。 普通工厂方法,需要指定......

太猪-YJ
26分钟前
1
0
tomcat 莫名奔溃问题

Apr 24, 2019 6:18:11 PM org.apache.coyote.AbstractProtocol pause INFO: Pausing ProtocolHandler ["http-nio-8080"] Apr 24, 2019 6:18:12 PM org.apache.coyote.AbstractProtocol pause......

mellen
44分钟前
3
0
组件开发规范 class名身份识别

组件需要通过一个组件共有的class来标识这个组件,外部调用的时候,可以通过锁定这个class来方便地改变组件的css样式。 设置方式 .my-checkbox { width: 20px; height: 20px; font-...

Carbenson
52分钟前
3
0
如何在工作中快速成长?致工程师的10个简单技巧

阿里妹导读:阿里有句非常经典的土话,“今天的最好表现,是明天的最低要求。”如何挖掘潜能、发现更好的自己?今天,阿里巴巴高级无线开发专家江建明将认知升级的方法总结出来,帮助你获得快...

阿里云云栖社区
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部