- Timestamp:
- 05/26/13 15:14:33 (3 years ago)
- Location:
- branches/decorate
- Files:
-
- 4 edited
- 1 moved
Legend:
- Unmodified
- Added
- Removed
-
branches/decorate/cache.py
r662 r663 1 1 # 2 2 3 import collections 3 try: 4 from collections import namedtuple 5 except ImportError: 6 from namedtuple import namedtuple 7 from collections import deque 4 8 from random import choice #XXX: biased? 5 9 from heapq import nsmallest … … 8 12 from functools import update_wrapper 9 13 from threading import RLock 10 from cache_helper import _CacheInfo, Counter, hashmap as _keymap 11 14 from keymaps import hashmap as _keymap 15 16 _CacheInfo = namedtuple("CacheInfo", ['hits','misses','maxsize','currsize']) 17 18 class Counter(dict): 19 'Mapping where default values are zero' 20 def __missing__(self, key): 21 return 0 12 22 13 23 def no_cache(*arg, **kwd): … … 57 67 '''Infinitely-growing cache decorator. 58 68 59 If *typed* is True, arguments of different types will be cached separately.60 For example, f(3.0) and f(3) will be treated as distinct calls with61 distinct results. Cache typing has a memory penalty, and may also may be62 ignored by some 'keymaps'.63 64 69 If *keymap* is given, it will replace the hashing algorithm for generating 65 cache keys. For example, see the other hashing algorithms available in 66 'cache_helper.py'. With the default keymap, arguments to the cached 67 function must be hashable. 70 cache keys. Several hashing algorithms are available in 'keymaps.py'. With 71 the default keymap, arguments to the cached function must be hashable. 72 73 If the keymap retains type information, then arguments of different types 74 will be cached separately. For example, f(3.0) and f(3) will be treated 75 as distinct calls with distinct results. Cache typing has a memory penalty, 76 and may also be ignored by some 'keymaps'. 68 77 69 78 View the cache statistics named tuple (hits, misses, maxsize, currsize) with … … 73 82 ''' 74 83 maxsize = None 75 make_key = kwd.get('keymap', _keymap)76 typed = kwd.get('typed', False)84 make_key = kwd.get('keymap', None) 85 if make_key is None: make_key = _keymap() 77 86 78 87 def decorating_function(user_function): … … 84 93 85 94 def wrapper(*args, **kwds): 86 key = make_key( args, kwds, typed)95 key = make_key(*args, **kwds) 87 96 88 97 # get cache entry or compute if not found … … 116 125 117 126 118 def lfu_cache(maxsize=100, keymap=None , typed=False):127 def lfu_cache(maxsize=100, keymap=None): 119 128 '''Least-frequenty-used cache decorator. 120 129 … … 122 131 will grow without bound. 123 132 124 If *typed* is True, arguments of different types will be cached separately.125 For example, f(3.0) and f(3) will be treated as distinct calls with126 distinct results. Cache typing has a memory penalty, and may also may be127 ignored by some 'keymaps'.128 129 133 If *keymap* is given, it will replace the hashing algorithm for generating 130 cache keys. For example, see the other hashing algorithms available in 131 'cache_helper.py'. With the default keymap, arguments to the cached 132 function must be hashable. 134 cache keys. Several hashing algorithms are available in 'keymaps.py'. With 135 the default keymap, arguments to the cached function must be hashable. 136 137 If the keymap retains type information, then arguments of different types 138 will be cached separately. For example, f(3.0) and f(3) will be treated 139 as distinct calls with distinct results. Cache typing has a memory penalty, 140 and may also be ignored by some 'keymaps'. 133 141 134 142 View the cache statistics named tuple (hits, misses, maxsize, currsize) with … … 140 148 ''' 141 149 if maxsize == 0: return no_cache() 142 if keymap is None: make_key = _keymap 150 if keymap is None: make_key = _keymap() 143 151 else: make_key = keymap 144 if maxsize is None: return inf_cache(keymap=make_key , typed=typed)152 if maxsize is None: return inf_cache(keymap=make_key) 145 153 146 154 def decorating_function(user_function): … … 153 161 154 162 def wrapper(*args, **kwds): 155 key = make_key( args, kwds, typed)163 key = make_key(*args, **kwds) 156 164 157 165 # get cache entry or compute if not found … … 194 202 195 203 196 def lru_cache(maxsize=100, keymap=None , typed=False):204 def lru_cache(maxsize=100, keymap=None): 197 205 '''Least-recently-used cache decorator. 198 206 … … 200 208 will grow without bound. 201 209 202 If *typed* is True, arguments of different types will be cached separately.203 For example, f(3.0) and f(3) will be treated as distinct calls with204 distinct results. Cache typing has a memory penalty, and may also may be205 ignored by some 'keymaps'.206 207 210 If *keymap* is given, it will replace the hashing algorithm for generating 208 cache keys. For example, see the other hashing algorithms available in 209 'cache_helper.py'. With the default keymap, arguments to the cached 210 function must be hashable. 211 cache keys. Several hashing algorithms are available in 'keymaps.py'. With 212 the default keymap, arguments to the cached function must be hashable. 213 214 If the keymap retains type information, then arguments of different types 215 will be cached separately. For example, f(3.0) and f(3) will be treated 216 as distinct calls with distinct results. Cache typing has a memory penalty, 217 and may also be ignored by some 'keymaps'. 211 218 212 219 View the cache statistics named tuple (hits, misses, maxsize, currsize) with … … 218 225 ''' 219 226 if maxsize == 0: return no_cache() 220 if keymap is None: make_key = _keymap 227 if keymap is None: make_key = _keymap() 221 228 else: make_key = keymap 222 if maxsize is None: return inf_cache(keymap=make_key , typed=typed)229 if maxsize is None: return inf_cache(keymap=make_key) 223 230 maxqueue = maxsize * 10 #XXX: user settable? confirm this works as expected 224 231 225 232 def decorating_function(user_function): 226 233 cache = dict() # mapping of args to results 227 queue = collections.deque()# order that keys have been used234 queue = deque() # order that keys have been used 228 235 refcount = Counter() # times each key is in the queue 229 236 sentinel = object() # marker for looping around the queue … … 238 245 239 246 def wrapper(*args, **kwds): 240 key = make_key( args, kwds, typed)247 key = make_key(*args, **kwds) 241 248 242 249 # get cache entry or compute if not found … … 297 304 298 305 299 def mru_cache(maxsize=100, keymap=None , typed=False):306 def mru_cache(maxsize=100, keymap=None): 300 307 '''Most-recently-used cache decorator. 301 308 … … 303 310 will grow without bound. 304 311 305 If *typed* is True, arguments of different types will be cached separately.306 For example, f(3.0) and f(3) will be treated as distinct calls with307 distinct results. Cache typing has a memory penalty, and may also may be308 ignored by some 'keymaps'.309 310 312 If *keymap* is given, it will replace the hashing algorithm for generating 311 cache keys. For example, see the other hashing algorithms available in 312 'cache_helper.py'. With the default keymap, arguments to the cached 313 function must be hashable. 313 cache keys. Several hashing algorithms are available in 'keymaps.py'. With 314 the default keymap, arguments to the cached function must be hashable. 315 316 If the keymap retains type information, then arguments of different types 317 will be cached separately. For example, f(3.0) and f(3) will be treated 318 as distinct calls with distinct results. Cache typing has a memory penalty, 319 and may also be ignored by some 'keymaps'. 314 320 315 321 View the cache statistics named tuple (hits, misses, maxsize, currsize) with … … 321 327 ''' 322 328 if maxsize == 0: return no_cache() 323 if keymap is None: make_key = _keymap 329 if keymap is None: make_key = _keymap() 324 330 else: make_key = keymap 325 if maxsize is None: return inf_cache(keymap=make_key , typed=typed)331 if maxsize is None: return inf_cache(keymap=make_key) 326 332 327 333 def decorating_function(user_function): 328 334 cache = dict() # mapping of args to results 329 queue = collections.deque()# order that keys have been used335 queue = deque() # order that keys have been used 330 336 stats = [0, 0] # make statistics updateable non-locally 331 337 HITS, MISSES = 0, 1 # names for the stats fields … … 338 344 339 345 def wrapper(*args, **kwds): 340 key = make_key( args, kwds, typed)346 key = make_key(*args, **kwds) 341 347 342 348 # get cache entry or compute if not found … … 379 385 380 386 381 def rr_cache(maxsize=100, keymap=None , typed=False):387 def rr_cache(maxsize=100, keymap=None): 382 388 '''random-replacement cache decorator. 383 389 … … 385 391 will grow without bound. 386 392 387 If *typed* is True, arguments of different types will be cached separately.388 For example, f(3.0) and f(3) will be treated as distinct calls with389 distinct results. Cache typing has a memory penalty, and may also may be390 ignored by some 'keymaps'.391 392 393 If *keymap* is given, it will replace the hashing algorithm for generating 393 cache keys. For example, see the other hashing algorithms available in 394 'cache_helper.py'. With the default keymap, arguments to the cached 395 function must be hashable. 394 cache keys. Several hashing algorithms are available in 'keymaps.py'. With 395 the default keymap, arguments to the cached function must be hashable. 396 397 If the keymap retains type information, then arguments of different types 398 will be cached separately. For example, f(3.0) and f(3) will be treated 399 as distinct calls with distinct results. Cache typing has a memory penalty, 400 and may also be ignored by some 'keymaps'. 396 401 397 402 View the cache statistics named tuple (hits, misses, maxsize, currsize) with … … 403 408 ''' 404 409 if maxsize == 0: return no_cache() 405 if keymap is None: make_key = _keymap 410 if keymap is None: make_key = _keymap() 406 411 else: make_key = keymap 407 if maxsize is None: return inf_cache(keymap=make_key , typed=typed)412 if maxsize is None: return inf_cache(keymap=make_key) 408 413 409 414 def decorating_function(user_function): … … 415 420 416 421 def wrapper(*args, **kwds): 417 key = make_key( args, kwds, typed)422 key = make_key(*args, **kwds) 418 423 419 424 # get cache entry or compute if not found … … 451 456 452 457 453 def _test_hits(algorithm, maxsize=20, typed=False, rangelimit=5, tries=1000):454 455 @algorithm(maxsize=maxsize, typed=typed)458 def _test_hits(algorithm, maxsize=20, keymap=None, rangelimit=5, tries=1000): 459 460 @algorithm(maxsize=maxsize, keymap=keymap) 456 461 def f(x, y): 457 462 return 3*x+y -
branches/decorate/keymaps.py
r662 r663 1 # helper functions for caching 2 try: 3 from collections import namedtuple 4 except ImportError: 5 from namedtuple import namedtuple 1 # 6 2 7 _CacheInfo = namedtuple("CacheInfo", ['hits','misses','maxsize','currsize']) 3 class _Sentinel(object): 4 def __repr__(self): 5 return "<SENTINEL>" 6 class _NoSentinel(object): 7 def __repr__(self): 8 return "<NOSENTINEL>" 9 10 SENTINEL = _Sentinel() 11 NOSENTINEL = _NoSentinel() 12 # SENTINEL = object() 13 # NOSENTINEL = (SENTINEL,) #XXX: use to indicate "don't use a sentinel" ? 8 14 9 15 10 #XXX: convert this into a 'keymap' class... 11 def keymap(args, kwds, #XXX: should only take args kwds; rest are 'settings' 12 typed = False, 13 kwd_mark = (object(),), #XXX: 'nicer' kwd_mark = ("",) ? None ? 14 flat = True, #XXX: if not flat, then key = (args, tuple) 15 fasttypes = set((int, str, frozenset, type(None))), 16 sorted=sorted, tuple=tuple, type=type, len=len): 17 'Make a cache key from optionally typed positional and keyword arguments' 18 if not flat: 16 class keymap(object): 17 18 def __init__(self, typed=False, flat=True, sentinel=NOSENTINEL, **kwds): 19 '''initialize the key builder 20 21 typed: if True, include type information in the key 22 flat: if True, flatten the key to a sequence; if False, use (args, kwds) 23 sentinel: marker for separating args and kwds in flattened keys 24 ''' 25 self.typed = typed 26 self.flat = flat 27 self.sentinel = sentinel 28 29 # some rare kwds that allow keymap customization 30 self._fasttypes = kwds.get('fasttypes', set((int,str,frozenset,type(None)))) 31 self._sorted = kwds.get('sorted', sorted) 32 self._tuple = kwds.get('tuple', tuple) 33 self._type = kwds.get('type', type) 34 self._len = kwds.get('len', len) 35 return 36 37 def __get_sentinel(self): 38 if self._mark: 39 return self._mark[0] 40 return NOSENTINEL #XXX: or None? 41 def __sentinel(self, mark): 42 if mark != NOSENTINEL: 43 self._mark = (mark,) 44 else: self._mark = None 45 46 def __call__(self, *args, **kwds): 47 'Make cache key from optionally typed positional and keyword arguments' 48 if self.flat: 49 return self.encode(*args, **kwds) 50 return self.encrypt(*args, **kwds) 51 52 def encrypt(self, *args, **kwds): 53 """use a non-flat scheme for producing a key""" 19 54 key = (args, kwds) #XXX: pickles larger, but is simpler to unpack 20 if typed:21 sorted_items = s orted(kwds.items())22 key += ( tuple(type(v) for v in args), \23 tuple(type(v) for k, vin sorted_items))55 if self.typed: 56 sorted_items = self._sorted(kwds.items()) 57 key += (self._tuple(self._type(v) for v in args), \ 58 self._tuple(self._type(v) for (k,v) in sorted_items)) 24 59 return key 25 key = args 26 if kwds: 27 sorted_items = sorted(kwds.items()) 28 key += kwd_mark 29 for item in sorted_items: 30 key += item 31 if typed: #XXX: 'kwd_mark' between each of the 4 parts, so easy to split 32 key += kwd_mark + tuple(type(v) for v in args) 60 61 def encode(self, *args, **kwds): 62 """use a flattened scheme for producing a key""" 63 key = args 33 64 if kwds: 34 key += kwd_mark + tuple(type(v) for k, v in sorted_items) 35 elif len(key) == 1 and type(key[0]) in fasttypes: 36 return key[0] 37 return key 38 # return _HashedSeq(key) 65 sorted_items = self._sorted(kwds.items()) 66 if self._mark: key += self._mark 67 for item in sorted_items: 68 key += item 69 if self.typed: #XXX: 'mark' between each part, so easy to split 70 if self._mark: key += self._mark 71 key += self._tuple(self._type(v) for v in args) 72 if kwds: 73 if self._mark: key += self._mark 74 key += self._tuple(self._type(v) for (k,v) in sorted_items) 75 elif self._len(key) == 1 and self._type(key[0]) in self._fasttypes: 76 return key[0] 77 return key 39 78 40 ''' 41 class _HashedSeq(list): 42 __slots__ = 'hashvalue' 79 def decrypt(self, key): 80 raise NotImplementedError, "Key decryption is not implemented" 43 81 44 def __init__(self, tup, hash=hash): 45 self[:] = tup 46 self.hashvalue = hash(tup) 82 def decode(self, key): 83 raise NotImplementedError, "Key decoding is not implemented" 47 84 48 def __hash__(self): 49 return self.hashvalue 85 def dumps(self, obj): 86 """a more pickle-like interface for encoding a key""" 87 return self.encode(obj) 88 89 def loads(self, key): 90 """a more pickle-like interface for decoding a key""" 91 return self.decode(key) 92 93 # interface 94 sentinel = property(__get_sentinel, __sentinel) 95 pass 50 96 51 97 52 def keymap(args, kwds, kwd_mark=object()): 53 """kwd_mark is a separator between args and kwds""" 54 key = args 55 if kwds: 56 key += (kwd_mark,) + tuple(sorted(kwds.items())) 57 return key 58 ''' 98 class hashmap(keymap): 99 def encode(self, *args, **kwds): 100 return hash(keymap.encode(self, *args, **kwds)) 101 def encrypt(self, *args, **kwds): 102 return hash(keymap.encrypt(self, *args, **kwds)) 59 103 60 def hashmap(*args, **kwds): 61 return hash(keymap(*args, **kwds)) 104 class stringmap(keymap): 105 #def __init__(self, *args, **kwds): 106 # keymap.__init__(self, *args, **kwds) 107 # self.typed = False #XXX: is always typed, so set typed=False 108 def encode(self, *args, **kwds): 109 return str(keymap.encode(self, *args, **kwds)) 110 def encrypt(self, *args, **kwds): 111 return str(keymap.encrypt(self, *args, **kwds)) 62 112 63 113 import dill as pickle 64 def picklemap(*args, **kwds): #XXX: is always typed, so set typed=False 65 kwds['typed'] = kwds.get('typed', False) 66 return pickle.dumps(keymap(*args, **kwds)) 67 68 def stringmap(*args, **kwds): #XXX: is always typed, so set typed=False 69 kwds['typed'] = kwds.get('typed', False) 70 return str(keymap(*args, **kwds)) 114 class picklemap(keymap): 115 #def __init__(self, *args, **kwds): 116 # keymap.__init__(self, *args, **kwds) 117 # self.typed = False #XXX: is always typed, so set typed=False 118 def encode(self, *args, **kwds): 119 return pickle.dumps(keymap.encode(self, *args, **kwds)) 120 def encrypt(self, *args, **kwds): 121 return pickle.dumps(keymap.encrypt(self, *args, **kwds)) 71 122 72 123 73 class Counter(dict): 74 'Mapping where default values are zero' 75 def __missing__(self, key): 76 return 0 77 78 124 # EOF -
branches/decorate/memoize.py
r662 r663 2 2 decorators that cache results to memory, to file, or to a database 3 3 """ 4 from keymaps import stringmap 4 5 5 6 __all__ = ['memoize','memoized','archive_dict','db_dict'] … … 338 339 339 340 340 def memoized(memo=None, serializer=str, tol=None, deep=False, archived=False):341 def memoized(memo=None, keymap=None, tol=None, deep=False, archived=False): 341 342 """Decorator that memoizes a function's return value each time it is called. 342 343 If called later with the same arguments, the memoized value is returned, and … … 346 347 347 348 memo = storage hashmap (default is {}) 348 serializer = serializing function (e.g. pickle.dumps, but default is str)349 keymap = cache key encoder (default is keymaps.stringmap(flat=False)) 349 350 tol = integer tolerance for rounding (default is None) 350 351 deep = boolean for rounding depth (default is False, i.e. 'shallow') 351 352 archived = boolean for archiving (default is False, i.e. "don't archive") 352 353 """ 354 if keymap is None: keymap = stringmap(flat=False) 353 355 if memo is None: memo = archive_dict() 354 356 elif type(memo) is dict: memo = archive_dict(memo) … … 367 369 try: 368 370 _args, _kwds = rounded_args(*args, **kwds) 369 argstr = serializer((_args, _kwds))371 argstr = keymap(*_args, **_kwds) 370 372 if memo.has_key(argstr): 371 373 return memo[argstr] … … 388 390 #FIXME: use cache maxsize algorithms... where dump if maxsize 389 391 #FIXME: can make trash_archive where archives to del 390 #FIXME: can have serializer be 'hash' or lambda x:x391 #FIXME: should sort(kwds.items) in argstr; probably add an object to separate392 392 393 393 class memoize(object): … … 397 397 Can memoize a *method* on an object. 398 398 """ 399 def __init__(self, memo=None, serializer=str, tol=None, deep=False):399 def __init__(self, memo=None, keymap=None, tol=None, deep=False): 400 400 # self.func = func 401 if keymap is None: keymap = stringmap(flat=False) 401 402 if memo is None: memo = archive_dict() 402 403 elif type(memo) is dict: memo = archive_dict(memo) 403 404 self.memo = memo 404 self.__ serializer = serializer405 self.__keymap = keymap 405 406 406 407 if deep: rounded = deep_round … … 420 421 try: 421 422 _args, _kwds = self.__rounded_args(*args, **kwds) 422 argstr = self.__ serializer((_args, _kwds))423 argstr = self.__keymap(*_args, **_kwds) 423 424 if self.memo.has_key(argstr): 424 425 return self.memo[argstr] -
branches/decorate/surrogate.py
r658 r663 20 20 21 21 22 import dill23 22 from memoize import memoized 24 #@memoized(serializer=dill.dumps, tol=0, deep=True) # slower, but more robust 23 from keymaps import picklemap 24 dumps = picklemap(flat=False) 25 #@memoized(keymap=dumps, tol=0, deep=True) # slower, but more robust 25 26 #@memoized(tol=0, deep=True) 26 #@memoized( serializer=dill.dumps, archived=True) # slower, but more robust27 #@memoized(keymap=dumps, archived=True) # slower, but more robust 27 28 @memoized(archived=True) 28 29 def marc_surr(x): -
branches/decorate/test_memoize.py
r658 r663 24 24 #from memoize import memoize 25 25 from timer import timed 26 import dill 27 26 from keymaps import picklemap 27 dumps = picklemap(flat=False) 28 28 29 29 class Spam(object): 30 30 """A simple class with a memoized method""" 31 31 32 @memoized( serializer=dill.dumps)32 @memoized(keymap=dumps) 33 33 def eggs(self, *args, **kwds): 34 34 print 'new:', args, kwds … … 49 49 50 50 # here caching saves time in a recursive function... 51 @memoized( serializer=dill.dumps)51 @memoized(keymap=dumps) 52 52 @timed() 53 53 def fibonacci(n): … … 64 64 65 65 from numpy import sum, asarray 66 @memoized( serializer=dill.dumps, tol=3)66 @memoized(keymap=dumps, tol=3) 67 67 def add(*args): 68 68 print 'new:', args … … 86 86 return sum(x**2 - y**2) 87 87 88 cost1 = memoized( serializer=dill.dumps, tol=1)(cost)89 cost0 = memoized( serializer=dill.dumps, tol=0)(cost)90 costD = memoized( serializer=dill.dumps, tol=0, deep=True)(cost)88 cost1 = memoized(keymap=dumps, tol=1)(cost) 89 cost0 = memoized(keymap=dumps, tol=0)(cost) 90 costD = memoized(keymap=dumps, tol=0, deep=True)(cost) 91 91 92 92 print "rounding to one decimals..." … … 135 135 print "re_dict_memo = %s" % add.memo 136 136 137 @memoized( serializer=dill.dumps)137 @memoized(keymap=dumps) 138 138 def add(x,y): 139 139 return x+y
Note: See TracChangeset
for help on using the changeset viewer.