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 = None

class 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  。 


大家觉得文章对你有些作用! 如果想赏钱,可以用微信扫描下面的二维码,感谢!
另外再次标注博客原地址  xiaorui.cc

3 Responses

  1. killer 2014年11月4日 / 上午7:46

    pypi有时候会删掉一些无意义得项目

  2. orangleliu 2014年11月2日 / 下午7:02

    搞爬虫不错,这么多新东西。

发表评论

邮箱地址不会被公开。 必填项已用*标注