发布于 2015-11-16 19:55:44 | 75 次阅读 | 评论: 0 | 来源: 网友投递

这里有新鲜出炉的Python3 Cookbook中文版,程序狗速度看过来!

Python编程语言

Python 是一种面向对象、解释型计算机程序设计语言,由Guido van Rossum于1989年底发明,第一个公开发行版发行于1991年。Python语法简洁而清晰,具有丰富和强大的类库。它常被昵称为胶水语言,它能够把用其他语言制作的各种模块(尤其是C/C++)很轻松地联结在一起。


这篇文章主要介绍了Python实现LRU算法的2种方法,本文分别给出了用OrderedDict实现、用dict+list实现两种方法,需要的朋友可以参考下

LRU:least recently used,最近最少使用算法。它的使用场景是:在有限的空间中存储对象时,当空间满时,会按一定的原则删除原有的对象,常用的原则(算法)有LRU,FIFO,LFU等。在计算机的Cache硬件,以及主存到虚拟内存的页面置换,还有Redis缓存系统中都用到了该算法。我在一次面试和一个笔试时,也遇到过这个问题。

LRU的算法是比较简单的,当对key进行访问时(一般有查询,更新,增加,在get()和set()两个方法中实现即可)时,将该key放到队列的最前端(或最后端)就行了,这样就实现了对key按其最后一次访问的时间降序(或升序)排列,当向空间中增加新对象时,如果空间满了,删除队尾(或队首)的对象。

在Python中,可以使用collections.OrderedDict很方便的实现LRU算法,当然,如果你想不到用OrderedDict,那可以用dict+list来实现。本文主要参考了LRU CACHE IN PYTHON,写的非常好,既实现了功能,又简洁易读。方法一的代码与参考文章基本相同,方法二是我自己想出来的,比较繁琐一些,其实OrderedDict本身也是类似的这种机制来实现的有序。

不过,下面的实现是有问题的,这个cache的key:value键值对中,value只能是不可变类型。因为,如果value是可变类型,那对于同一个key,所有调用get(key)方法返回的value都是指向同一个可变对象的,当修改其中一个value时,那所有的value都会被修改了,即使你没有调用set()方法也会这样。这是我们不希望看到的。解决方法我想到了两种,一是可变对象序列化后再存储,即将可变对象转为不可变对象;二是仍存储可变对象,但get()时,返回一个深拷贝,这样每个get()调用返回的对象就不会相互影响了。推荐第一种方法。另外,对于key,推荐使用str/unicode类型。

当并发时,还会存在一个问题,因为这涉及到对公共资源的写操作,所以必须要对set()加锁。其实,在并发情况下,所有对公共资源的写操作都要加锁。如果不存在并发的情况,只有单线程,那可以不加锁。

方法一:用OrderedDict实现(推荐)

代码如下:

from collections import OrderedDict
 
 
class LRUCache(OrderedDict):
    '''不能存储可变类型对象,不能并发访问set()'''

    def __init__(self,capacity):
        self.capacity = capacity
        self.cache = OrderedDict()
    

    def get(self,key):
        if self.cache.has_key(key):
            value = self.cache.pop(key)
            self.cache[key] = value
        else:
            value = None
        
        return value
    

    def set(self,key,value):
        if self.cache.has_key(key):
            value = self.cache.pop(key)
            self.cache[key] = value
        else:
            if len(self.cache) == self.capacity:
                self.cache.popitem(last = False)    #pop出第一个item
                self.cache[key] = value
            else:
                self.cache[key] = value


测试代码如下
代码如下:

c = LRUCache(5)
 
for i in range(5,10):
    c.set(i,10*i)
 
 
print c.cache, c.cache.keys()
 
c.get(5)
c.get(7)
 
print c.cache, c.cache.keys()
 
c.set(10,100)
print c.cache, c.cache.keys()
 
c.set(9,44)
print c.cache, c.cache.keys()

输出如下

代码如下:

OrderedDict([(5, 50), (6, 60), (7, 70), (8, 80), (9, 90)])     [5, 6, 7, 8, 9]
OrderedDict([(6, 60), (8, 80), (9, 90), (5, 50), (7, 70)])     [6, 8, 9, 5, 7]
OrderedDict([(8, 80), (9, 90), (5, 50), (7, 70), (10, 100)])   [8, 9, 5, 7, 10]
OrderedDict([(8, 80), (5, 50), (7, 70), (10, 100), (9, 90)])   [8, 5, 7, 10, 9]


方法二:用dict+list实现(不推荐)

代码如下:

class LRUCache(object):
    '''不能存储可变类型对象,不能并发访问set()'''
 
    def __init__(self,capacity):
        self.l = []
        self.d = {}
        self.capacity = capacity
         

    def get(self,key):
        if self.d.has_key(key):
            value = self.d[key]
            self.l.remove(key)
            self.l.insert(0,key)
        else:
            value = None
         
        return value
     

    def set(self,key,value):
        if self.d.has_key(key):
            self.l.remove(key)
        elif len(self.d) == self.capacity:
                oldest_key = self.l.pop()
                self.d.pop(oldest_key)
                 
        self.d[key] = value
        self.l.insert(0, key)


测试代码如下
代码如下:

c = LRUCache(5)
 
for i in range(5,10):
    c.set(i,10*i)
 
 
print c.d,c.l
 
c.get(5)
c.get(7)
 
print c.d,c.l
 
c.set(10,100)
print c.d,c.l
 
c.set(9,44)
print c.d,c.l

输出为

代码如下:

{8: 80, 9: 90, 5: 50, 6: 60, 7: 70}   [9, 8, 7, 6, 5]
{8: 80, 9: 90, 5: 50, 6: 60, 7: 70}   [7, 5, 9, 8, 6]
{5: 50, 7: 70, 8: 80, 9: 90, 10: 100} [10, 7, 5, 9, 8]
{5: 50, 7: 70, 8: 80, 9: 44, 10: 100} [9, 10, 7, 5, 8]



相关阅读 :
Python实现LRU算法的2种方法
python实现中文输出的两种方法
Python读取键盘输入的2种方法
python实现字符串连接的三种方法及其效率、适用场景详解
python实现下载文件的三种方法
Python实现检测服务器是否可以ping通的2种方法
Python编程实现生成特定范围内不重复多个随机数的2种方法
Python实现获取磁盘剩余空间的2种方法
python字符串替换的2种方法总结
Python xlrd读取excel日期类型的2种方法
Python简单检测文本类型的2种方法【基于文件头及cchardet库】
总结python实现父类调用两种方法的不同
最新网友评论  共有(0)条评论 发布评论 返回顶部

Copyright © 2007-2017 PHPERZ.COM All Rights Reserved   冀ICP备14009818号  版权声明  广告服务