1 from collections import namedtuple
2 from functools import update_wrapper
3 from threading import RLock
4
5 _CacheInfo = namedtuple("CacheInfo", ["hits", "misses", "maxsize", "currsize"])
6
7 class _HashedSeq(list):
8 __slots__ = 'hashvalue'
9
10 def __init__(self, tup, hash=hash):
11 self[:] = tup
12 self.hashvalue = hash(tup)
13
14 def __hash__(self):
15 return self.hashvalue
16
17 def _make_key(args, kwds, typed,
18 kwd_mark = (object(),),
19 fasttypes = {int, str, frozenset, type(None)},
20 sorted=sorted, tuple=tuple, type=type, len=len):
21 'Make a cache key from optionally typed positional and keyword arguments'
22 key = args
23 if kwds:
24 sorted_items = sorted(kwds.items())
25 key += kwd_mark
26 for item in sorted_items:
27 key += item
28 if typed:
29 key += tuple(type(v) for v in args)
30 if kwds:
31 key += tuple(type(v) for k, v in sorted_items)
32 elif len(key) == 1 and type(key[0]) in fasttypes:
33 return key[0]
34 return _HashedSeq(key)
35
36 def lru_cache(maxsize=100, typed=False):
37 """Least-recently-used cache decorator.
38
39 If *maxsize* is set to None, the LRU features are disabled and the cache
40 can grow without bound.
41
42 If *typed* is True, arguments of different types will be cached separately.
43 For example, f(3.0) and f(3) will be treated as distinct calls with
44 distinct results.
45
46 Arguments to the cached function must be hashable.
47
48 View the cache statistics named tuple (hits, misses, maxsize, currsize) with
49 f.cache_info(). Clear the cache and statistics with f.cache_clear().
50 Access the underlying function with f.__wrapped__.
51
52 See: http://en.wikipedia.org/wiki/Cache_algorithms#Least_Recently_Used
53
54 """
55
56 # Users should only access the lru_cache through its public API:
57 # cache_info, cache_clear, and f.__wrapped__
58 # The internals of the lru_cache are encapsulated for thread safety and
59 # to allow the implementation to change (including a possible C version).
60
61 def decorating_function(user_function):
62
63 cache = dict()
64 stats = [0, 0] # make statistics updateable non-locally
65 HITS, MISSES = 0, 1 # names for the stats fields
66 make_key = _make_key
67 cache_get = cache.get # bound method to lookup key or return None
68 _len = len # localize the global len() function
69 lock = RLock() # because linkedlist updates aren't threadsafe
70 root = [] # root of the circular doubly linked list
71 root[:] = [root, root, None, None] # initialize by pointing to self
72 nonlocal_root = [root] # make updateable non-locally
73 PREV, NEXT, KEY, RESULT = 0, 1, 2, 3 # names for the link fields
74
75 if maxsize == 0:
76
77 def wrapper(*args, **kwds):
78 # no caching, just do a statistics update after a successful call
79 result = user_function(*args, **kwds)
80 stats[MISSES] += 1
81 return result
82
83 elif maxsize is None:
84
85 def wrapper(*args, **kwds):
86 # simple caching without ordering or size limit
87 key = make_key(args, kwds, typed)
88 result = cache_get(key, root) # root used here as a unique not-found sentinel
89 if result is not root:
90 stats[HITS] += 1
91 return result
92 result = user_function(*args, **kwds)
93 cache[key] = result
94 stats[MISSES] += 1
95 return result
96
97 else:
98
99 def wrapper(*args, **kwds):
100 # size limited caching that tracks accesses by recency
101 key = make_key(args, kwds, typed) if kwds or typed else args
102 with lock:
103 link = cache_get(key)
104 if link is not None:
105 # record recent use of the key by moving it to the front of the list
106 root, = nonlocal_root
107 link_prev, link_next, key, result = link
108 link_prev[NEXT] = link_next
109 link_next[PREV] = link_prev
110 last = root[PREV]
111 last[NEXT] = root[PREV] = link
112 link[PREV] = last
113 link[NEXT] = root
114 stats[HITS] += 1
115 return result
116 result = user_function(*args, **kwds)
117 with lock:
118 root, = nonlocal_root
119 if key in cache:
120 # getting here means that this same key was added to the
121 # cache while the lock was released. since the link
122 # update is already done, we need only return the
123 # computed result and update the count of misses.
124 pass
125 elif _len(cache) >= maxsize:
126 # use the old root to store the new key and result
127 oldroot = root
128 oldroot[KEY] = key
129 oldroot[RESULT] = result
130 # empty the oldest link and make it the new root
131 root = nonlocal_root[0] = oldroot[NEXT]
132 oldkey = root[KEY]
133 oldvalue = root[RESULT]
134 root[KEY] = root[RESULT] = None
135 # now update the cache dictionary for the new links
136 del cache[oldkey]
137 cache[key] = oldroot
138 else:
139 # put result in a new link at the front of the list
140 last = root[PREV]
141 link = [last, root, key, result]
142 last[NEXT] = root[PREV] = cache[key] = link
143 stats[MISSES] += 1
144 return result
145
146 def cache_info():
147 """Report cache statistics"""
148 with lock:
149 return _CacheInfo(stats[HITS], stats[MISSES], maxsize, len(cache))
150
151 def cache_clear():
152 """Clear the cache and cache statistics"""
153 with lock:
154 cache.clear()
155 root = nonlocal_root[0]
156 root[:] = [root, root, None, None]
157 stats[:] = [0, 0]
158
159 wrapper.__wrapped__ = user_function
160 wrapper.cache_info = cache_info
161 wrapper.cache_clear = cache_clear
162 return update_wrapper(wrapper, user_function)
163
164 return decorating_function
165
Saturday, December 21, 2013
Test Code Insert
Subscribe to:
Posts (Atom)