一个Python写的支持LRU的类

freeeyes

最近工作需要，写了一个Python下的池，需要LRU支持，感觉写起来比C++的简单。
脚本语言在逻辑处理上，还是提供了很多方便的接口。
在这里记录一下

2. #!/usr/bin/env python
3. # -*- coding:utf-8 -*-#
4. '''
5. Created on 2011-2-16
7. @author: freeeyes
8. '''
9. import time
10. from heapq import heappush, heappop, heapify
12. class LRUCache(object):
13.     class __Node(object):
14.         def __init__(self, key, obj, timestamp, sort_key):
15.             object.__init__(self)
16.             self.key = key
17.             self.obj = obj
18.             self.atime = timestamp
19.             self.mtime = self.atime
20.             self._sort_key = sort_key
21.    
22.         def __cmp__(self, other):
23.             return cmp(self._sort_key, other._sort_key)
24.         
25.         def __repr__(self):
26.             return "<%s %s => %s (%s)>" % (self.__class__, self.key, self.obj, time.asctime(time.localtime(self.atime)))
27.         
29.     def __init__(self, nCacheCount):
30.         self.m_nCacheCount = nCacheCount
31.         self.m_heap     = []
32.         self.m_dict     = {}
33.         self.m_nCounter = 0
35.     def GetSortKey(self):
36.         self.m_nCounter += 1
37.         return self.m_nCounter
38.    
39.     def __len__(self):
40.         return len(self.m_heap)
42.     def __setitem__(self, key, obj):
43.         if self.m_dict.has_key(key):
44.             node = self.m_dict[key]
45.             node.atime = time.time()
46.             node.mtime = node.atime
47.             node._sort_key = self.GetSortKey()
48.             heapify(self.m_heap)
49.         else:
50.             while len(self.m_heap) >= self.m_nCacheCount:
51.                 lru = heappop(self.m_heap)
52.                 self.SetData(lru.key, self.m_dict[lru.key].obj)
53.                 del self.m_dict[lru.key]
54.             
55.             node = self.__Node(key, obj, time.time(), self.GetSortKey())
56.             self.m_dict[key] = node
57.             heappush(self.m_heap, node)
59.     def __getitem__(self, key):
60.         if not self.m_dict.has_key(key):
61.             return self.GetData(key)
62.         else:
63.             node = self.m_dict[key]
64.             node.atime = time.time()
65.             node._sort_key = self.GetSortKey()
66.             heapify(self.m_heap)
67.             return node.obj
69.     def __delitem__(self, key):
70.         if not self.m_dict.has_key(key):
71.             return None
72.         else:
73.             node = self.m_dict[key]
74.             del self.m_dict[key]
75.             self.m_heap.remove(node)
76.             heapify(self.m_heap)
77.             return node.obj
78.         
79.     def __iter__(self):
80.         copy = self.m_heap[:]
81.         while len(copy) > 0:
82.             node = heappop(copy)
83.             yield node.key
84.         raise StopIteration
85.    
86.     def __setattr__(self, name, value):
87.         object.__setattr__(self, name, value)
88.         if name == 'size':
89.             while len(self.m_heap) > value:
90.                 lru = heappop(self.m_heap)
91.                 del self.m_dict[lru.key]
93.     def __repr__(self):
94.         return "<%s (%d elements)>" % (str(self.__class__), len(self.m_heap))
95.    
96.     def GetData(self, key):
97.         #重载实现函数，当找不到数据的时候，调用这个加载
98.         pass
99.    
100.     def SetData(self, key, obj):
101.         #当数据超过的池大小的时候，会调用这个。
102.         pass

复制代码

这里因为我个人需要，我需要在GetItem()的时候，如果不在指定的字典里面，则提供外围一个接口，从别的介质获取数据（数据库中查找并加载进队列），如果队列达到上限，则剔除最不常用的那个对象，同时调用SetData()接口，让你把这个数据放在其他介质上(比如数据库)。
测试代码如下：(数据库部分省略，只是简单测试)

1. class TaskLru(LRUCache):
2.     def GetData(self, key):
3.         print "[GetData]Key=" + str(key)
4.         
5.     def SetData(self, key, obj):
6.         print "[SetData]Key=" + str(key) + ",obj=" + str(obj)
7.         
8.         
9. objTaskLru = TaskLru(10)
10. for i in range(0, 20):
11.     objTaskLru[i] = i

复制代码

输出为
[SetData]Key=0,obj=0
[SetData]Key=1,obj=1
[SetData]Key=2,obj=2
[SetData]Key=3,obj=3
[SetData]Key=4,obj=4
[SetData]Key=5,obj=5
[SetData]Key=6,obj=6
[SetData]Key=7,obj=7
[SetData]Key=8,obj=8
[SetData]Key=9,obj=9


此代码在python2.6下编译通过。