- # length-limited O(1) LRU cache implementation by Josiah Carlson
- # source: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/252524
- class Node(object):
- __slots__ = ['prev', 'next', 'me']
- def __init__(self, prev, me):
- self.prev = prev
- self.me = me
- self.next = None
- class LRU:
- """
- Implementation of a length-limited O(1) LRU queue.
- Built for and used by PyPE:
- http://pype.sourceforge.net
- Copyright 2003 Josiah Carlson.
- """
- def __init__(self, count=100, pairs=[]):
- self.count = max(count, 1)
- self.d = {}
- self.first = None
- self.last = None
- for key, value in pairs:
- self[key] = value
- def __contains__(self, obj):
- return obj in self.d
- def __getitem__(self, obj):
- a = self.d[obj].me
- self[a[0]] = a[1]
- return a[1]
- def __setitem__(self, obj, val):
- if obj in self.d:
- del self[obj]
- nobj = Node(self.last, (obj, val))
- if self.first is None:
- self.first = nobj
- if self.last:
- self.last.next = nobj
- self.last = nobj
- self.d[obj] = nobj
- if len(self.d) > self.count:
- if self.first == self.last:
- self.first = None
- self.last = None
- return
- a = self.first
- a.next.prev = None
- self.first = a.next
- a.next = None
- del self.d[a.me[0]]
- del a
- def __delitem__(self, obj):
- nobj = self.d[obj]
- if nobj.prev:
- nobj.prev.next = nobj.next
- else:
- self.first = nobj.next
- if nobj.next:
- nobj.next.prev = nobj.prev
- else:
- self.last = nobj.prev
- del self.d[obj]
- def __iter__(self):
- cur = self.first
- while cur != None:
- cur2 = cur.next
- yield cur.me[1]
- cur = cur2
- def iteritems(self):
- cur = self.first
- while cur != None:
- cur2 = cur.next
- yield cur.me
- cur = cur2
- def iterkeys(self):
- return iter(self.d)
- def itervalues(self):
- for i,j in self.iteritems():
- yield j
- def keys(self):
- return self.d.keys()
- # ----------------------------------------------------------------
- # test compatibility interface
- def size(self):
- return len(self.d)
- def get(self, key):
- return self[key]
- def set(self, key, value):
- self[key] = value
- if __name__ == "__main__":
- a =LRU(4,[("first",1),("second",2),("third",3),("fourth",4)])
- print a.get("first")
- print a.get("third")
- print a.get("fourth")
- print a.d
- #该片段来自于http://www.codesnippet.cn/detail/030920135559.html
来源: http://www.codesnippet.cn/detail/030920135559.html