首页 > 代码库 > [leetcode]LRU Cache (python)

[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 <key, value> 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 <key, value> 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 = http://www.mamicode.com/self.keys2valNode[ key ]>