基于LRU的缓存神器，LRU缓存神器,稍微修改，如“移除队列时

基于LRU的缓存神器，LRU缓存神器,稍微修改，如“移除队列时

稍微修改，如“移除队列时存入介质”，会更爽。从web-miner中提取的

# length-limited O(1) LRU cache implementation by Josiah Carlson# source: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/252524class Node(object):    __slots__ = ['prev', 'next', 'me']    def __init__(self, prev, me):        self.prev = prev        self.me = me        self.next = Noneclass 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] = valueif __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://byrx.net