1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
|
:mod:`cachetools` --- Extensible memoizing collections and decorators
=======================================================================
.. module:: cachetools
This module provides various memoizing collections and decorators,
including variants of the Python 3 Standard Library `@lru_cache`_
function decorator.
For the purpose of this module, a *cache* is a mutable_ mapping_ of a
fixed maximum size. When the cache is full, i.e. by adding another
item the cache would exceed its maximum size, the cache must choose
which item(s) to discard based on a suitable `cache algorithm`_. In
general, a cache's size is the total size of its items, and an item's
size is a property or function of its value, e.g. the result of
``sys.getsizeof(value)``. For the trivial but common case that each
item counts as :const:`1`, a cache's size is equal to the number of
its items, or ``len(cache)``.
Multiple cache classes based on different caching algorithms are
implemented, and decorators for easily memoizing function and method
calls are provided, too.
Cache implementations
------------------------------------------------------------------------
This module provides several classes implementing caches using
different cache algorithms. All these classes derive from class
:class:`Cache`, which in turn derives from
:class:`collections.MutableMapping`, and provide :attr:`maxsize` and
:attr:`currsize` properties to retrieve the maximum and current size
of the cache. When a cache is full, :meth:`setitem` calls
:meth:`popitem` repeatedly until there is enough room for the item to
be added.
All cache classes accept an optional `missing` keyword argument in
their constructor, which can be used to provide a default *factory
function*. If the key `key` is not present, the ``cache[key]``
operation calls :meth:`Cache.__missing__`, which in turn calls
`missing` with `key` as its sole argument. The cache will then store
the object returned from ``missing(key)`` as the new cache value for
`key`, possibly discarding other items if the cache is full. This may
be used to provide memoization for existing single-argument functions::
from cachetools import LRUCache
import urllib.request
def get_pep(num):
"""Retrieve text of a Python Enhancement Proposal"""
url = 'http://www.python.org/dev/peps/pep-%04d/' % num
with urllib.request.urlopen(url) as s:
return s.read()
cache = LRUCache(maxsize=4, missing=get_pep)
for n in 8, 9, 290, 308, 320, 8, 218, 320, 279, 289, 320, 9991:
try:
print(n, len(cache[n]))
except urllib.error.HTTPError:
print(n, 'Not Found')
print(sorted(cache.keys()))
:class:`Cache` also features a :meth:`getsizeof` method, which returns
the size of a given `value`. The default implementation of
:meth:`getsizeof` returns :const:`1` irrespective of its argument,
making the cache's size equal to the number of its items, or
``len(cache)``. For convenience, all cache classes accept an optional
named constructor parameter `getsizeof`, which may specify a function
of one argument used to retrieve the size of an item's value.
.. autoclass:: Cache
:members:
This class discards arbitrary items using :meth:`popitem` to make
space when necessary. Derived classes may override :meth:`popitem`
to implement specific caching strategies. If a subclass has to
keep track of item access, insertion or deletion, it may
additionally need to override :meth:`__getitem__`,
:meth:`__setitem__` and :meth:`__delitem__`. If a subclass wants
to store meta data with its values, i.e. the `value` argument
passed to :meth:`Cache.__setitem__` is different from what the
derived class's :meth:`__setitem__` received, it will probably need
to override :meth:`getsizeof`, too.
.. autoclass:: LFUCache
:members:
This class counts how often an item is retrieved, and discards the
items used least often to make space when necessary.
.. autoclass:: LRUCache
:members:
This class discards the least recently used items first to make
space when necessary.
.. autoclass:: RRCache(maxsize, choice=random.choice, missing=None, getsizeof=None)
:members:
This class randomly selects candidate items and discards them to
make space when necessary.
By default, items are selected from the list of cache keys using
:func:`random.choice`. The optional argument `choice` may specify
an alternative function that returns an arbitrary element from a
non-empty sequence.
.. autoclass:: TTLCache(maxsize, ttl, timer=time.time, missing=None, getsizeof=None)
:members:
:exclude-members: expire
This class associates a time-to-live value with each item. Items
that expire because they have exceeded their time-to-live will be
removed automatically. If no expired items are there to remove,
the least recently used items will be discarded first to make space
when necessary. Trying to access an expired item will raise a
:exc:`KeyError`.
By default, the time-to-live is specified in seconds, and the
:func:`time.time` function is used to retrieve the current time. A
custom `timer` function can be supplied if needed.
.. automethod:: expire(self, time=None)
Since expired items will be "physically" removed from a cache
only at the next mutating operation, e.g. :meth:`__setitem__` or
:meth:`__delitem__`, to avoid changing the underlying dictionary
while iterating over it, expired items may still claim memory
although they are no longer accessible. Calling this method
removes all items whose time-to-live would have expired by
`time`, so garbage collection is free to reuse their memory. If
`time` is :const:`None`, this removes all items that have
expired by the current value returned by :attr:`timer`.
Memoizing decorators
------------------------------------------------------------------------
The :mod:`cachetools` module provides decorators for memoizing
function and method calls. This can save time when a function is
often called with the same arguments::
from cachetools import cached
@cached(cache={})
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)
for i in range(100):
print('fib(%d) = %d' % (i, fib(i)))
.. decorator:: cached(cache, key=cachetools.keys.hashkey, lock=None)
Decorator to wrap a function with a memoizing callable that saves
results in a cache.
The `cache` argument specifies a cache object to store previous
function arguments and return values. Note that `cache` need not
be an instance of the cache implementations provided by the
:mod:`cachetools` module. :func:`cached` will work with any
mutable mapping type, including plain :class:`dict` and
:class:`weakref.WeakValueDictionary`.
`key` specifies a function that will be called with the same
positional and keyword arguments as the wrapped function itself,
and which has to return a suitable cache key. Since caches are
mappings, the object returned by `key` must be hashable. The
default is to call :func:`cachetools.keys.hashkey`.
If `lock` is not :const:`None`, it must specify an object
implementing the `context manager`_ protocol. Any access to the
cache will then be nested in a ``with lock:`` statement. This can
be used for synchronizing thread access to the cache by providing a
:class:`threading.RLock` instance, for example.
.. note::
The `lock` context manager is used only to guard access to the
cache object. The underlying wrapped function will be called
outside the `with` statement, and must be thread-safe by itself.
The original underlying function is accessible through the
:attr:`__wrapped__` attribute of the memoizing wrapper function.
This can be used for introspection or for bypassing the cache.
To perform operations on the cache object, for example to clear the
cache during runtime, the cache should be assigned to a variable.
When a `lock` object is used, any access to the cache from outside
the function wrapper should also be performed within an appropriate
`with` statement::
from threading import RLock
from cachetools import cached, LRUCache
cache = LRUCache(maxsize=100)
lock = RLock()
@cached(cache, lock=lock)
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)
# make sure access to cache is synchronized
with lock:
cache.clear()
It is also possible to use a single shared cache object with
multiple functions. However, care must be taken that different
cache keys are generated for each function, even for identical
function arguments::
from functools import partial
from cachetools import cached, hashkey, LRUCache
cache = LRUCache(maxsize=100)
@cached(cache, key=partial(hashkey, 'fib'))
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)
@cached(cache, key=partial(hashkey, 'fac'))
def fac(n):
return 1 if n == 0 else n * fac(n - 1)
print(fib(42))
print(fac(42))
print(cache)
.. decorator:: cachedmethod(cache, key=cachetools.keys.hashkey, lock=None)
Decorator to wrap a class or instance method with a memoizing
callable that saves results in a (possibly shared) cache.
The main difference between this and the :func:`cached` function
decorator is that `cache` and `lock` are not passed objects, but
functions. Both will be called with :const:`self` (or :const:`cls`
for class methods) as their sole argument to retrieve the cache or
lock object for the method's respective instance or class.
.. note::
As with :func:`cached`, the context manager obtained by calling
``lock(self)`` will only guard access to the cache itself. It
is the user's responsibility to handle concurrent calls to the
underlying wrapped method in a multithreaded environment.
One advantage of :func:`cachedmethod` over the :func:`cached`
function decorator is that cache properties such as `maxsize` can
be set at runtime::
import operator
import urllib.request
from cachetools import LRUCache, cachedmethod
class CachedPEPs(object):
def __init__(self, cachesize):
self.cache = LRUCache(maxsize=cachesize)
@cachedmethod(operator.attrgetter('cache'))
def get(self, num):
"""Retrieve text of a Python Enhancement Proposal"""
url = 'http://www.python.org/dev/peps/pep-%04d/' % num
with urllib.request.urlopen(url) as s:
return s.read()
peps = CachedPEPs(cachesize=10)
print("PEP #1: %s" % peps.get(1))
:mod:`cachetools.keys` --- Key functions for memoizing decorators
============================================================================
.. module:: cachetools.keys
This module provides several functions that can be used as key
functions with the :func:`cached` and :func:`cachedmethod` decorators:
.. autofunction:: hashkey
This function returns a :class:`tuple` instance suitable as a cache
key, provided the positional and keywords arguments are hashable.
.. autofunction:: typedkey
This function is similar to :func:`hashkey`, but arguments of
different types will yield distinct cache keys. For example,
``typedkey(3)`` and ``typedkey(3.0)`` will return different
results.
These functions can also be helpful when implementing custom key
functions for handling some non-hashable arguments. For example,
calling the following function with a dictionary as its `env` argument
will raise a :class:`TypeError`, since :class:`dict` is not hashable::
@cached(LRUCache(maxsize=128))
def foo(x, y, z, env={}):
pass
However, if `env` always holds only hashable values itself, a custom
key function can be written that handles the `env` keyword argument
specially::
def envkey(*args, env={}, **kwargs):
key = hashkey(*args, **kwargs)
key += tuple(env.items())
return key
The :func:`envkey` function can then be used in decorator declarations
like this::
@cached(LRUCache(maxsize=128), key=envkey)
:mod:`cachetools.func` --- :func:`functools.lru_cache` compatible decorators
============================================================================
.. module:: cachetools.func
To ease migration from (or to) Python 3's :func:`functools.lru_cache`,
this module provides several memoizing function decorators with a
similar API. All these decorators wrap a function with a memoizing
callable that saves up to the `maxsize` most recent calls, using
different caching strategies. Note that unlike
:func:`functools.lru_cache`, setting `maxsize` to :const:`None` is not
supported.
If the optional argument `typed` is set to :const:`True`, function
arguments of different types will be cached separately. For example,
``f(3)`` and ``f(3.0)`` will be treated as distinct calls with
distinct results.
The wrapped function is instrumented with :func:`cache_info` and
:func:`cache_clear` functions to provide information about cache
performance and clear the cache. See the :func:`functools.lru_cache`
documentation for details.
.. decorator:: lfu_cache(maxsize=128, typed=False)
Decorator that wraps a function with a memoizing callable that
saves up to `maxsize` results based on a Least Frequently Used
(LFU) algorithm.
.. decorator:: lru_cache(maxsize=128, typed=False)
Decorator that wraps a function with a memoizing callable that
saves up to `maxsize` results based on a Least Recently Used (LRU)
algorithm.
.. decorator:: rr_cache(maxsize=128, choice=random.choice, typed=False)
Decorator that wraps a function with a memoizing callable that
saves up to `maxsize` results based on a Random Replacement (RR)
algorithm.
.. decorator:: ttl_cache(maxsize=128, ttl=600, timer=time.time, typed=False)
Decorator to wrap a function with a memoizing callable that saves
up to `maxsize` results based on a Least Recently Used (LRU)
algorithm with a per-item time-to-live (TTL) value.
.. _@lru_cache: http://docs.python.org/3/library/functools.html#functools.lru_cache
.. _cache algorithm: http://en.wikipedia.org/wiki/Cache_algorithms
.. _context manager: http://docs.python.org/dev/glossary.html#term-context-manager
.. _mapping: http://docs.python.org/dev/glossary.html#term-mapping
.. _mutable: http://docs.python.org/dev/glossary.html#term-mutable
|