python实现最少使用算法lru包括dict和list队列

Lru 就是个 最少使用的算法，不是最少使用，他的名字就叫 ‘最少使用算法’。原理就是除了原本的数据之外，我另外维护一个dict或者是list，专门用来做排序，我每次get的时候，维护的那个dict里面key的value 加1 。你懂的。

用途，一般在于数据的缓存，在一定范围内，可以确保数据的鲜活度，经常用的数据和刚刚进来的数据，是保留的，去除的往往是有段时间没用了。 可以省内存的空间，在python下使用的话，内存可以回收的。

话说，哥们现在对python的gc内存回收很是敏感，上次的问题到了，是MySQLdb的一个问题，但是…..。还是无法解决，只能是把那段逻辑fork出去，然后kill，不让main thread 看到这样的麻烦事。

关于lru的代码已经提交到:https://github.com/rfyiamcool/pyLruCache ,有兴趣的朋友自己看看。

另外我也push到pypi站点了，大家直接pip install pyLruCache 安装 。

这个文章的原文是在 http://blog.xiaorui.cc ，我的文章总是被爬来爬去的。

注: 我一年前发布的几个项目，一个是websocket监控相关的，一个是ipmitool的python封装。 但是今天在pypi找不到了，貌似是被干掉了，也有可能是名字我记错了。翻看了下邮件没有给我回复啥信息。 感觉应该不会删除才对。 留个截图为证。

class Node(object):    __slots__ = ['prev', 'next', 'me']    def __init__(self, prev, me):        self.prev = prev        self.me = me        self.next = Noneclass pyLruListCache:    def __init__(self, count):        self.count = count        self.l = []        self.lru = {}        self.tm = 0    def extend(self,t_list):        for i in t_list:            self.lru[item] = self.tm            self.tm += 1            self.append(i)    def appendd(self, item):        if len(self.l)>=self.count:            old_key = min(self.lru.keys(), key=lambda k:self.lru[k])            self.l.remove(old_key)            self.lru.pop(old_key)        self.l.append(item)        self.lru[item] = self.tm        self.tm += 1    def pop(self):        old_key = min(self.lru.keys(), key=lambda k:self.lru[k])        self.l.remove(old_key)        return old_key    def __getitem__(self,item):        data = self.l[item]        self.lru[item] = self.tm        self.tm += 1        return data class pyLruDictCache:    """ for dict """    def __init__(self, count, 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()

和Lru类似的还有别的一些对于缓存的算法，比如LFU、MRU 。