[leetcode]LRU Cache (python)

发布时间:2017-09-13 12:38:56
[leetcode]LRU Cache (python)

LRU:最近最久未使用,为了得到这个最新最久的信息,需要一种策略来进行记录,如果加入类似时间戳式的字段,那么每次删除的时候,就必须通过遍历才能得到时间信息,或者对时间戳进行排序,但是无论哪种,都是需要额外的维护,维护成本都比较高。

广泛使用的策略是底层用双端队列来进行维护,双端使得在插入删除时操作更简单。而单单使用双端队列似乎还是不够,比如在get 时,还是需要顺序查找给定的key参数的,所以为了能在O(1) 时间获得key 需要类hash的结构,在python里,就用字典。

接下来的事情是,我们在字典和双端队列里,各保存什么信息呢?

class dqNode: def __init__(self, key, val): self.val = val self.key = key self.pre = None self.next = None
字典:< key: dqnode >

这样通过字典,我们可以快速的找到 key 所对应的结点,从结点中找到 value 信息。

这样,在对某个key 进行get 或set操作后, 我们就将对应的dqnode 移到 双端队列的头部,表示该结点是最近被访问的,而队尾的就是最近都没被访问的, 或者说距离上次访问时间最久的。这里我们看看可不可以再dqnode里只设val 子段,因为key的信息在字典里有了,考虑到删除的时候,这就不可以了,因为我们可以很简单的在队尾将dqnode 结点删除,但是要删除字典中对应的项就无能为力,因为字典的查找都是基于key的,所以key在dqnode中也要存储。

为了方便操作,站群系统,我们还是设定一个伪头结点和伪尾结点。

class LRUCache: # @param capacity, an integer def __init__( self, capacity ): self.capacity = capacity self.curSize = 0 self.keys2valNode = { } # mapping key to the node that has the value info # dqlist to store pairs self.head = dqNode(-1, -1) self.tail = dqNode(-1, -1) self.head.next = self.tail self.tail.pre = self.head
变量说明:

keys2valNode:是一个字典容器,健值就是key, 对应的val 是存储val所在的dqnode结点。

head,tail:双端队列的头尾指针

class dqNode: def __init__(self, key, val): self.val = val self.key = key self.pre = None self.next = None class LRUCache: # @param capacity, an integer def __init__( self, capacity ): self.capacity = capacity self.curSize = 0 self.keys2valNode = { } # mapping key to the node that has the value info # dqlist to store pairs self.head = dqNode(-1, -1) self.tail = dqNode(-1, -1) self.head.next = self.tail self.tail.pre = self.head # util functions def moveToFirst( self, pnode ): # link pnode.pre and pnode.next if pnode.pre: pnode.pre.next = pnode.next if pnode.next: pnode.next.pre = pnode.pre # move pnode to first pnode.next = self.head.next if self.head.next: self.head.next.pre = pnode self.head.next = pnode pnode.pre = self.head def removeLRU( self ): pdel = self.tail.pre pdel.pre.next = self.tail self.tail.pre = pdel.pre del self.keys2valNode[ pdel.key ] del pdel def Insert( self, key, value ): newNode = dqNode(key, value) # add to dict self.keys2valNode[ key ] = newNode # insert to first of dqueue self.moveToFirst(newNode) # @return an integer def get(self, key): if self.keys2valNode.has_key(key): # get the node that has value info. pvalue = self.keys2valNode[ key ] value = pvalue.val # change pvalue to be recently visited one self.moveToFirst( pvalue ) return value else: return -1 # @param key, an integer # @param value, an integer # @return nothing def set( self, key, value ): # if has key, just have to change the value if self.keys2valNode.has_key( key ): self.keys2valNode[ key ].val = value self.moveToFirst( self.keys2valNode[ key ] ) # insert a new key # 1) curSize < capacity, just insert # 2) curSize == capacity, remove LRU and insert else: self.Insert(key, value) if self.curSize < self.capacity: self.curSize += 1 else: self.removeLRU()



企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:神农架网站建设 http://shennongjia.45qun.com

上一篇:PHP超级全局变量总结
下一篇:最后一页