Python实现的最近最少使用算法

这篇文章主要介绍了Python实现的最近最少使用算法,涉及节点、时间、流程控制等相关技巧,需要的朋友可以参考下

本文实例讲述了Python实现的最近最少使用算法。分享给大家供大家参考。具体如下：

1. # lrucache.py -- a simple LRU (Least-Recently-Used) cache class  
2. # Copyright 2004 Evan Prodromou <evan@bad.dynu.ca>  
3. # Licensed under the Academic Free License 2.1  
4. # Licensed for ftputil under the revised BSD license  
5. # with permission by the author, Evan Prodromou. Many  
6. # thanks, Evan! :-)  
7. #  
8. # The original file is available at  
9. # http://pypi.python.org/pypi/lrucache/0.2 .  
10. # arch-tag: LRU cache main module  
11. """a simple LRU (Least-Recently-Used) cache module  
12. This module provides very simple LRU (Least-Recently-Used) cache  
13. functionality.  
14. An *in-memory cache* is useful for storing the results of an  
15. 'expe/nsive' process (one that takes a lot of time or resources) for  
16. later re-use. Typical examples are accessing data from the filesystem,  
17. a database, or a network location. If you know you'll need to re-read  
18. the data again, it can help to keep it in a cache.  
19. You *can* use a Python dictionary as a cache for some purposes.  
20. However, if the results you're caching are large, or you have a lot of  
21. possible results, this can be impractical memory-wise.  
22. An *LRU cache*, on the other hand, only keeps _some_ of the results in  
23. memory, which keeps you from overusing resources. The cache is bounded  
24. by a maximum size; if you try to add more values to the cache, it will  
25. automatically discard the values that you haven't read or written to  
26. in the longest time. In other words, the least-recently-used items are  
27. discarded. [1]_  
28. .. [1]: 'Discarded' here means 'removed from the cache'.  
29. """ 
30. from __future__ import generators  
31. import time  
32. from heapq import heappush, heappop, heapify  
33. # the suffix after the hyphen denotes modifications by the  
34. # ftputil project with respect to the original version  
35. __version__ = "0.2-1" 
36. __all__ = ['CacheKeyError', 'LRUCache', 'DEFAULT_SIZE']  
37. __docformat__ = 'reStructuredText en' 
38. DEFAULT_SIZE = 16 
39. """Default size of a new LRUCache object, if no 'size' argument is given.""" 
40. class CacheKeyError(KeyError):  
41. """Error raised when cache requests fail  
42. When a cache record is accessed which no longer exists (or never did),  
43. this error is raised. To avoid it, you may want to check for the existence  
44. of a cache record before reading or deleting it.""" 
45. pass 
46. class LRUCache(object):  
47. """Least-Recently-Used (LRU) cache.  
48. Instances of this class provide a least-recently-used (LRU) cache. They  
49. emulate a Python mapping type. You can use an LRU cache more or less like  
50. a Python dictionary, with the exception that objects you put into the  
51. cache may be discarded before you take them out.  
52. Some example usage::  
53. cache = LRUCache(32) # new cache  
54. cache['foo'] = get_file_contents('foo') # or whatever  
55. if 'foo' in cache: # if it's still in cache...  
56. # use cached version  
57. contents = cache['foo']  
58. else:  
59. # recalculate  
60. contents = get_file_contents('foo')  
61. # store in cache for next time  
62. cache['foo'] = contents  
63. print cache.size # Maximum size  
64. print len(cache) # 0 <= len(cache) <= cache.size  
65. cache.size = 10 # Auto-shrink on size assignment  
66. for i in range(50): # note: larger than cache size  
67. cache[i] = i  
68. if 0 not in cache: print 'Zero was discarded.'  
69. if 42 in cache:  
70. del cache[42] # Manual deletion  
71. for j in cache: # iterate (in LRU order)  
72. print j, cache[j] # iterator produces keys, not values  
73. """ 
74. class __Node(object):  
75. """Record of a cached value. Not for public consumption.""" 
76. def __init__(self, key, obj, timestamp, sort_key):  
77. object.__init__(self)  
78. self.key = key  
79. self.obj = obj  
80. self.atime = timestamp  
81. self.mtime = self.atime  
82. self._sort_key = sort_key  
83. def __cmp__(self, other):  
84. return cmp(self._sort_key, other._sort_key)  
85. def __repr__(self):  
86. return "<%s %s => %s (%s)>" % /  
87. (self.__class__, self.key, self.obj, /  
88. time.asctime(time.localtime(self.atime)))  
89. def __init__(self, size=DEFAULT_SIZE):  
90. # Check arguments  
91. if size <= 0:  
92. raise ValueError, size  
93. elif type(size) is not type(0):  
94. raise TypeError, size  
95. object.__init__(self)  
96. self.__heap = []  
97. self.__dict = {}  
98. """Maximum size of the cache.  
99. If more than 'size' elements are added to the cache,  
100. the least-recently-used ones will be discarded.""" 
101. self.size = size  
102. self.__counter = 0 
103. def _sort_key(self):  
104. """Return a new integer value upon every call.  
105. Cache nodes need a monotonically increasing time indicator.  
106. time.time() and time.clock() don't guarantee this in a  
107. platform-independent way.  
108. """ 
109. self.__counter += 1 
110. return self.__counter  
111. def __len__(self):  
112. return len(self.__heap)  
113. def __contains__(self, key):  
114. return self.__dict.has_key(key)  
115. def __setitem__(self, key, obj):  
116. if self.__dict.has_key(key):  
117. node = self.__dict[key]  
118. # update node object in-place  
119. node.obj = obj  
120. node.atime = time.time()  
121. node.mtime = node.atime  
122. node._sort_key = self._sort_key()  
123. heapify(self.__heap)  
124. else:  
125. # size may have been reset, so we loop  
126. while len(self.__heap) >= self.size:  
127. lru = heappop(self.__heap)  
128. del self.__dict[lru.key]  
129. node = self.__Node(key, obj, time.time(), self._sort_key())  
130. self.__dict[key] = node  
131. heappush(self.__heap, node)  
132. def __getitem__(self, key):  
133. if not self.__dict.has_key(key):  
134. raise CacheKeyError(key)  
135. else:  
136. node = self.__dict[key]  
137. # update node object in-place  
138. node.atime = time.time()  
139. node._sort_key = self._sort_key()  
140. heapify(self.__heap)  
141. return node.obj  
142. def __delitem__(self, key):  
143. if not self.__dict.has_key(key):  
144. raise CacheKeyError(key)  
145. else:  
146. node = self.__dict[key]  
147. del self.__dict[key]  
148. self.__heap.remove(node)  
149. heapify(self.__heap)  
150. return node.obj  
151. def __iter__(self):  
152. copy = self.__heap[:]  
153. while len(copy) > 0:  
154. node = heappop(copy)  
155. yield node.key  
156. raise StopIteration  
157. def __setattr__(self, name, value):  
158. object.__setattr__(self, name, value)  
159. # automagically shrink heap on resize  
160. if name == 'size':  
161. while len(self.__heap) > value:  
162. lru = heappop(self.__heap)  
163. del self.__dict[lru.key]  
164. def __repr__(self):  
165. return "<%s (%d elements)>" % (str(self.__class__), len(self.__heap))  
166. def mtime(self, key):  
167. """Return the last modification time for the cache record with key.  
168. May be useful for cache instances where the stored values can get  
169. 'stale', such as caching file or network resource contents.""" 
170. if not self.__dict.has_key(key):  
171. raise CacheKeyError(key)  
172. else:  
173. node = self.__dict[key]  
174. return node.mtime  
175. if __name__ == "__main__":  
176. cache = LRUCache(25)  
177. print cache  
178. for i in range(50):  
179. cache[i] = str(i)  
180. print cache  
181. if 46 in cache:  
182. print "46 in cache" 
183. del cache[46]  
184. print cache  
185. cache.size = 10 
186. print cache  
187. cache[46] = '46' 
188. print cache  
189. print len(cache)  
190. for c in cache:  
191. print c  
192. print cache  
193. print cache.mtime(46)  
194. for c in cache:  
195. print c  

希望本文所述对大家的Python程序设计有所帮助。