Python实现的一个简单LRU cache

起因:我的同事需要一个固定大小的cache,如果记录在cache中,直接从cache中读取,否则从数据库中读取。python的dict 是一个非常简单的cache,但是由于数据量很大,内存很可能增长的过大,因此需要限定记录数,并用LRU算法丢弃旧记录。key 是整型,value是10KB左右的python对象

分析:

1)可以想到,在对于cache,我们需要维护 key -> value 的关系

2)而为了实现LRU,我们又需要一个基于时间的优先级队列,来维护   timestamp  -> (key, value) 的关系

3)当cache 中的记录数达到一个上界maxsize时,需要将timestamp 最小的(key,value) 出队列

4) 当一个(key, value) 被命中时,实际上我们需要将它从队列中,移除并插入到队列的尾部。

从分析可以看出我们的cache 要达到性能最优需要满足上面的四项功能,对于队表的快速移除和插入,链表显然是最优的选择,为了快速移除,最好使用双向链表,为了插入尾部,需要有指向尾部的指针。

下面用python 来实现:

代码如下:

#encoding=utf-8

class LRUCache(object):
    def __init__(self, maxsize):
        # cache 的最大记录数
        self.maxsize = maxsize
        # 用于真实的存储数据
        self.inner_dd = {}
        # 链表-头指针
        self.head = None
        # 链表-尾指针
        self.tail = None

def set(self, key, value):
        # 达到指定大小     
        if len(self.inner_dd) >= self.maxsize:
            self.remove_head_node()

node = Node()
        node.data = (key, value)
        self.insert_to_tail(node)
        self.inner_dd[key] = node

def insert_to_tail(self, node):
        if self.tail is None:
            self.tail = node
            self.head = node
        else:
            self.tail.next = node
            node.pre = self.tail
            self.tail = node

def remove_head_node(self):
        node = self.head
        del self.inner_dd[node.data[0]]
        node = None
        self.head = self.head.next
        self.head.pre = None
    def get(self, key):
        if key in self.inner_dd:
            # 如果命中, 需要将对应的节点移动到队列的尾部
            node = self.inner_dd.get(key)
            self.move_to_tail(node)
            return node.data[1]
        return None

def move_to_tail(self, node):
        # 只需处理在队列头部和中间的情况
        if not (node == self.tail):
            if node == self.head:
                self.head = node.next
                self.head.pre = None
                self.tail.next = node
                node.pre = self.tail
                node.next = None
                self.tail = node
            else:
                pre_node = node.pre
                next_node = node.next
                pre_node.next = next_node
                next_node.pre = pre_node

self.tail.next = node
                node.pre = self.tail
                node.next = None
                self.tail = node

class Node(object):
    def __init__(self):
        self.pre = None
        self.next = None
        # (key, value)
        self.data = None

def __eq__(self, other):
        if self.data[0] == other.data[0]:
            return True
        return False
    def __str__(self):
       return str(self.data)

if __name__ == '__main__':
    cache = LRUCache(10)
    for i in xrange(1000):
        cache.set(i, i+1)
        cache.get(2)
    for key in cache.inner_dd:
        print key, cache.inner_dd[key]

(0)

相关推荐

  • python求众数问题实例

    本文实例讲述了python求众数问题的方法,是一个比较典型的应用.分享给大家供大家参考.具体如下: 问题描述: 多重集中重数最大的元素称为众数...就是一个可以有重复元素的集合,在这个集合中重复的次数最多的那个数就叫它的众数... 如S = [1,2,2,2,3,5] 重数是2,其重数为3 实例代码如下: list_num = [] list_num_count = 0 dict_num ={} #从文件读入,文件第一行为集合中元素的个数,以后每一行为一个元素 list_num_count =

  • python实现自动登录人人网并访问最近来访者实例

    本文实例讲述了python实现自动登录人人网并访问最近来访者的方法,分享给大家供大家参考. 具体方法如下: ##-*- coding : gbk -*- #在 import os from xml.dom import minidom import re import urllib import urllib2 import cookielib import datetime import time from urllib2 import URLError,HTTPError #登录模块 在网上

  • python实现根据图标提取分类应用程序实例

    本文实例讲述了python实现根据图标提取分类应用程序,分享给大家供大家参考. 具体方法如下: #!/usr/bin/python # -*- coding: utf-8 -*- import Image import win32ui import win32gui def make_regalur_image(img, size = (256, 256)): return img.resize(size).convert('RGB') def split_image(img, part_siz

  • python中实现定制类的特殊方法总结

    看到类似__slots__这种形如__xxx__的变量或者函数名就要注意,这些在Python中是有特殊用途的. __slots__我们已经知道怎么用了,__len__()方法我们也知道是为了能让class作用于len()函数. 除此之外,Python的class中还有许多这样有特殊用途的函数,可以帮助我们定制类. __str__ 我们先定义一个Student类,打印一个实例: 复制代码 代码如下: >>> class Student(object): ...     def __init

  • python错误处理详解

    在程序运行的过程中,如果发生了错误,可以事先约定返回一个错误代码,这样,就可以知道是否有错,以及出错的原因.在操作系统提供的调用中,返回错误码非常常见.比如打开文件的函数open(),成功时返回文件描述符(就是一个整数),出错时返回-1. 用错误码来表示是否出错十分不便,因为函数本身应该返回的正常结果和错误码混在一起,造成调用者必须用大量的代码来判断是否出错: 复制代码 代码如下: def foo():     r = some_function()     if r==(-1):       

  • python快速查找算法应用实例

    本文实例讲述了Python快速查找算法的应用,分享给大家供大家参考. 具体实现方法如下: import random def partition(list_object,start,end): random_choice = start #random.choice(range(start,end+1)) #把这里的start改成random()效率会更高些 x = list_object[random_choice] i = start j = end while True: while li

  • python实现得到一个给定类的虚函数

    本文实例讲述了python实现得到一个给定类的虚函数的方法,分享给大家供大家参考.具体如下: 现来看看如下代码: import wx for method in dir(wx.PyPanel): #这里改成给定的类 if method.startswith("base_"): print method 输出的结果为: base_AcceptsFocus base_AcceptsFocusFromKeyboard base_AddChild base_DoGetBestSize base

  • python字典序问题实例

    本文实例讲述了python字典序问题,分享给大家供大家参考.具体如下: 问题描述: 将字母从左向右的次序与字母表中的次序相同,且每个字符最大出现一次..例如:a,b,ab,bc,xyz等都是升序的字符串.现对字母表A产生的所有长度不超过6的升序字符串按照字典充排列并编码如下: 1 2 .. 26 27 28 ... a b .. z ab ac .. 对一个升序字符串,迅速计算出它在上述字典中的编码. 实现代码如下: import string all_letter = string.ascii

  • python人人网登录应用实例

    本文实例讲述了python人人网登录应用的实现方法,分享给大家供大家参考. 具体方法如下: import re import urllib import urllib2 import cookielib import datetime import time from urllib2 import URLError,HTTPError #第一个参数为日志文件,第二个参数为用户名,第三个参数为密码 def renren_login(logfile,username,password): logfi

  • Python实现从url中提取域名的几种方法

    从url中找到域名,首先想到的是用正则,然后寻找相应的类库.用正则解析有很多不完备的地方,url中有域名,域名后缀一直在不断增加等.通过google查到几种方法,一种是用Python中自带的模块和正则相结合来解析域名,另一种是使第三方用写好的解析模块直接解析出域名. 要解析的url 复制代码 代码如下: urls = ["http://meiwen.me/src/index.html",           "http://1000chi.com/game/index.htm

  • wxPython事件驱动实例详解

    本文实例讲述了wxPython的事件驱动机制,分享给大家供大家参考.具体方法如下: 先来看看如下代码: #!/usr/bin/python # moveevent.py import wx #导入wx库 class MoveEvent(wx.Frame): def __init__(self, parent, id, title): wx.Frame.__init__(self, parent, id, title, size=(250, 180)) #窗口大小为(250, 180) wx.St

  • python的re模块应用实例

    本文实例讲述了python的re模块应用.是非常重要的应用技巧.分享给大家供大家参考. 具体方法如下: import re # match_object = re.match('foo','foo') if match_object is not None: print type(match_object) print match_object.group() # match_object = re.match('foo','fooabv') if match_object is not Non

  • python中的多重继承实例讲解

    python和C++一样,支持多继承.概念虽然容易,但是困难的工作是如果子类调用一个自身没有定义的属性,它是按照何种顺序去到父类寻找呢,尤其是众多父类中有多个都包含该同名属性. 对经典类和新式类来说,属性的查找顺序是不同的.现在我们分别看一下经典类和新式类两种不同的表现: 经典类: 复制代码 代码如下: #! /usr/bin/python # -*- coding:utf-8 -*- class P1():     def foo(self):         print 'p1-foo' c

  • python之wxPython菜单使用详解

    本文实例讲述了python中wxPython菜单的使用方法,分享给大家供大家参考.具体如下: 先来看看下面这段代码: import wx APP_EXIT=1 #定义一个控件ID class Example(wx.Frame): def __init__(self, parent, id, title): super(Example,self).__init__(parent, id, title) #调用你类的初始化 self.InitUI() #调用自身的函数 def InitUI(self

随机推荐