一个Python写的支持LRU的类
本帖最后由 freeeyes 于 2011-2-16 14:30 编辑最近工作需要，写了一个Python下的池，需要LRU支持，感觉写起来比C++的简单。
脚本语言在逻辑处理上，还是提供了很多方便的接口。
在这里记录一下
#!/usr/bin/env python
# -*- coding:utf-8 -*-#
'''
Created on 2011-2-16
@author: freeeyes
'''
import time
from heapq import heappush, heappop, heapify
class LRUCache(object):
class __Node(object):
def __init__(self, key, obj, timestamp, sort_key):
object.__init__(self)
self.key = key
self.obj = obj
self.atime = timestamp
self.mtime = self.atime
self._sort_key = sort_key
def __cmp__(self, other):
return cmp(self._sort_key, other._sort_key)
def __repr__(self):
return "<%s %s => %s (%s)>" % (self.__class__, self.key, self.obj, time.asctime(time.localtime(self.atime)))
def __init__(self, nCacheCount):
self.m_nCacheCount = nCacheCount
self.m_heap = []
self.m_dict = {}
self.m_nCounter = 0
def GetSortKey(self):
self.m_nCounter += 1
return self.m_nCounter
def __len__(self):
return len(self.m_heap)
def __setitem__(self, key, obj):
if self.m_dict.has_key(key):
node = self.m_dict
node.atime = time.time()
node.mtime = node.atime
node._sort_key = self.GetSortKey()
heapify(self.m_heap)
else:
while len(self.m_heap) >= self.m_nCacheCount:
lru = heappop(self.m_heap)
self.SetData(lru.key, self.m_dict.obj)
del self.m_dict
node = self.__Node(key, obj, time.time(), self.GetSortKey())
self.m_dict = node
heappush(self.m_heap, node)
def __getitem__(self, key):
if not self.m_dict.has_key(key):
return self.GetData(key)
else:
node = self.m_dict
node.atime = time.time()
node._sort_key = self.GetSortKey()
heapify(self.m_heap)
return node.obj
def __delitem__(self, key):
if not self.m_dict.has_key(key):
return None
else:
node = self.m_dict
del self.m_dict
self.m_heap.remove(node)
heapify(self.m_heap)
return node.obj
def __iter__(self):
copy = self.m_heap[:]
while len(copy) > 0:
node = heappop(copy)
yield node.key
raise StopIteration
def __setattr__(self, name, value):
object.__setattr__(self, name, value)
if name == 'size':
while len(self.m_heap) > value:
lru = heappop(self.m_heap)
del self.m_dict
def __repr__(self):
return "<%s (%d elements)>" % (str(self.__class__), len(self.m_heap))
def GetData(self, key):
#重载实现函数，当找不到数据的时候，调用这个加载
pass
def SetData(self, key, obj):
#当数据超过的池大小的时候，会调用这个。
pass
这里因为我个人需要，我需要在GetItem()的时候，如果不在指定的字典里面，则提供外围一个接口，从别的介质获取数据（数据库中查找并加载进队列），如果队列达到上限，则剔除最不常用的那个对象，同时调用SetData()接口，让你把这个数据放在其他介质上(比如数据库)。
测试代码如下：(数据库部分省略，只是简单测试)
class TaskLru(LRUCache):
def GetData(self, key):
print "Key=" + str(key)
def SetData(self, key, obj):
print "Key=" + str(key) + ",obj=" + str(obj)
objTaskLru = TaskLru(10)
for i in range(0, 20):
objTaskLru = i
输出为
Key=0,obj=0
Key=1,obj=1
Key=2,obj=2
Key=3,obj=3
Key=4,obj=4
Key=5,obj=5
Key=6,obj=6
Key=7,obj=7
Key=8,obj=8
Key=9,obj=9
此代码在python2.6下编译通过。
页:
[1]