- Timestamp:
- 05/25/13 11:01:42 (3 years ago)
- Location:
- branches/decorate
- Files:
-
- 5 deleted
- 1 moved
Legend:
- Unmodified
- Added
- Removed
-
branches/decorate/cache.py
r660 r661 1 # 2 1 3 import collections 4 from random import choice #XXX: biased? 5 from heapq import nsmallest 6 from operator import itemgetter 7 from itertools import ifilterfalse 2 8 from functools import update_wrapper 3 9 from threading import RLock 4 from itertools import ifilterfalse5 10 from cache_helper import _CacheInfo, Counter, hashmap as _keymap 6 11 from INF_cache import inf_cache 7 12 from NO_cache import no_cache 13 14 15 def no_cache(*arg, **kwd): 16 '''empty cache decorator. 17 18 View the cache statistics named tuple (hits, misses, maxsize, currsize) with 19 f.info(). Clear the cache and statistics with f.clear(). Access the 20 underlying function with f.__wrapped__. This function does not cache, but 21 is a dummy that collects statistics and conforms to the caching interface. 22 23 ''' 24 maxsize = 0 25 cache = dict() #XXX: tuple, None, ...? 26 27 def decorating_function(user_function): 28 stats = [0, 0] # make statistics updateable non-locally 29 HITS, MISSES = 0, 1 # names for the stats fields 30 _len = len # localize the global len() function 31 #lock = RLock() # linkedlist updates aren't threadsafe 32 33 def wrapper(*args, **kwds): 34 # compute 35 result = user_function(*args, **kwds) 36 stats[MISSES] += 1 37 return result 38 39 def clear(): 40 """Clear the cache and statistics""" 41 stats[:] = [0, 0] 42 43 def info(): 44 """Report cache statistics""" 45 return _CacheInfo(stats[HITS], stats[MISSES], maxsize, len(cache)) 46 47 # interface 48 wrapper.__wrapped__ = user_function 49 wrapper.info = info 50 wrapper.clear = clear 51 #wrapper._cache = None #XXX 52 #wrapper._queue = None #XXX 53 return update_wrapper(wrapper, user_function) 54 55 return decorating_function 56 57 58 def inf_cache(*arg, **kwd): 59 '''Infinitely-growing cache decorator. 60 61 If *typed* is True, arguments of different types will be cached separately. 62 For example, f(3.0) and f(3) will be treated as distinct calls with 63 distinct results. Cache typing has a memory penalty, and may also may be 64 ignored by some 'keymaps'. 65 66 If *keymap* is given, it will replace the hashing algorithm for generating 67 cache keys. For example, see the other hashing algorithms available in 68 'cache_helper.py'. With the default keymap, arguments to the cached 69 function must be hashable. 70 71 View the cache statistics named tuple (hits, misses, maxsize, currsize) with 72 f.info(). Clear the cache and statistics with f.clear(). Access the 73 underlying function with f.__wrapped__. This cache will grow without bound. 74 75 ''' 76 maxsize = None 77 make_key = kwd.get('keymap', _keymap) 78 typed = kwd.get('typed', False) 79 80 def decorating_function(user_function): 81 cache = dict() # mapping of args to results 82 stats = [0, 0] # make statistics updateable non-locally 83 HITS, MISSES = 0, 1 # names for the stats fields 84 #_len = len # localize the global len() function 85 #lock = RLock() # linkedlist updates aren't threadsafe 86 87 def wrapper(*args, **kwds): 88 key = make_key(args, kwds, typed) 89 90 # get cache entry or compute if not found 91 try: 92 result = cache[key] 93 stats[HITS] += 1 94 except KeyError: 95 result = user_function(*args, **kwds) 96 cache[key] = result 97 stats[MISSES] += 1 98 return result 99 100 def clear(): 101 """Clear the cache and statistics""" 102 cache.clear() 103 stats[:] = [0, 0] 104 105 def info(): 106 """Report cache statistics""" 107 return _CacheInfo(stats[HITS], stats[MISSES], maxsize, len(cache)) 108 109 # interface 110 wrapper.__wrapped__ = user_function 111 wrapper.info = info 112 wrapper.clear = clear 113 #wrapper._cache = cache #XXX 114 #wrapper._queue = None #XXX 115 return update_wrapper(wrapper, user_function) 116 117 return decorating_function 118 119 120 def lfu_cache(maxsize=100, keymap=None, typed=False): 121 '''Least-frequenty-used cache decorator. 122 123 If *maxsize* is None, the LFU algorithm will be supressed and this cache 124 will grow without bound. 125 126 If *typed* is True, arguments of different types will be cached separately. 127 For example, f(3.0) and f(3) will be treated as distinct calls with 128 distinct results. Cache typing has a memory penalty, and may also may be 129 ignored by some 'keymaps'. 130 131 If *keymap* is given, it will replace the hashing algorithm for generating 132 cache keys. For example, see the other hashing algorithms available in 133 'cache_helper.py'. With the default keymap, arguments to the cached 134 function must be hashable. 135 136 View the cache statistics named tuple (hits, misses, maxsize, currsize) with 137 f.info(). Clear the cache and statistics with f.clear(). Access the 138 underlying function with f.__wrapped__. 139 140 See: http://en.wikipedia.org/wiki/Cache_algorithms#Least_Frequently_Used 141 142 ''' 143 if maxsize == 0: return no_cache() 144 if keymap is None: make_key = _keymap 145 else: make_key = keymap 146 if maxsize is None: return inf_cache(keymap=make_key, typed=typed) 147 148 def decorating_function(user_function): 149 cache = dict() # mapping of args to results 150 use_count = Counter() # times each key has been accessed 151 stats = [0, 0] # make statistics updateable non-locally 152 HITS, MISSES = 0, 1 # names for the stats fields 153 _len = len # localize the global len() function 154 #lock = RLock() # linkedlist updates aren't threadsafe 155 156 def wrapper(*args, **kwds): 157 key = make_key(args, kwds, typed) 158 159 # get cache entry or compute if not found 160 try: 161 result = cache[key] 162 use_count[key] += 1 163 stats[HITS] += 1 164 except KeyError: 165 cache[key] = user_function(*args, **kwds) 166 # need to add something to the cache, make room if necessary 167 if _len(cache) == maxsize: 168 for k, _ in nsmallest(maxsize // 10 or 1, 169 use_count.iteritems(), 170 key=itemgetter(1)): 171 del cache[k], use_count[k] 172 result = cache[key] 173 use_count[key] += 1 174 stats[MISSES] += 1 175 return result 176 177 def clear(): 178 """Clear the cache and statistics""" 179 cache.clear() 180 use_count.clear() 181 stats[:] = [0, 0] 182 183 def info(): 184 """Report cache statistics""" 185 return _CacheInfo(stats[HITS], stats[MISSES], maxsize, len(cache)) 186 187 # interface 188 wrapper.__wrapped__ = user_function 189 wrapper.info = info 190 wrapper.clear = clear 191 #wrapper._cache = cache #XXX 192 #wrapper._queue = use_count #XXX 193 return update_wrapper(wrapper, user_function) 194 195 return decorating_function 196 8 197 9 198 def lru_cache(maxsize=100, keymap=None, typed=False): … … 110 299 111 300 112 if __name__ == '__main__': 113 114 @lru_cache(maxsize=20, typed=True) 301 def mru_cache(maxsize=100, keymap=None, typed=False): 302 '''Most-recently-used cache decorator. 303 304 If *maxsize* is None, the MRU algorithm will be supressed and this cache 305 will grow without bound. 306 307 If *typed* is True, arguments of different types will be cached separately. 308 For example, f(3.0) and f(3) will be treated as distinct calls with 309 distinct results. Cache typing has a memory penalty, and may also may be 310 ignored by some 'keymaps'. 311 312 If *keymap* is given, it will replace the hashing algorithm for generating 313 cache keys. For example, see the other hashing algorithms available in 314 'cache_helper.py'. With the default keymap, arguments to the cached 315 function must be hashable. 316 317 View the cache statistics named tuple (hits, misses, maxsize, currsize) with 318 f.info(). Clear the cache and statistics with f.clear(). Access the 319 underlying function with f.__wrapped__. 320 321 See: http://en.wikipedia.org/wiki/Cache_algorithms#Most_Recently_Used 322 323 ''' 324 if maxsize == 0: return no_cache() 325 if keymap is None: make_key = _keymap 326 else: make_key = keymap 327 if maxsize is None: return inf_cache(keymap=make_key, typed=typed) 328 329 def decorating_function(user_function): 330 cache = dict() # mapping of args to results 331 queue = collections.deque() # order that keys have been used 332 stats = [0, 0] # make statistics updateable non-locally 333 HITS, MISSES = 0, 1 # names for the stats fields 334 _len = len # localize the global len() function 335 #lock = RLock() # linkedlist updates aren't threadsafe 336 337 # lookup optimizations (ugly but fast) 338 queue_append, queue_popleft = queue.append, queue.popleft 339 queue_appendleft, queue_pop = queue.appendleft, queue.pop 340 341 def wrapper(*args, **kwds): 342 key = make_key(args, kwds, typed) 343 344 # get cache entry or compute if not found 345 try: 346 result = cache[key] 347 queue.remove(key) 348 stats[HITS] += 1 349 except KeyError: 350 result = user_function(*args, **kwds) 351 cache[key] = result 352 stats[MISSES] += 1 353 354 # purge most recently used cache entry 355 if _len(cache) > maxsize: 356 del cache[queue_pop()] 357 358 # record recent use of this key 359 queue_append(key) 360 return result 361 362 def clear(): 363 """Clear the cache and statistics""" 364 cache.clear() 365 queue.clear() 366 stats[:] = [0, 0] 367 368 def info(): 369 """Report cache statistics""" 370 return _CacheInfo(stats[HITS], stats[MISSES], maxsize, len(cache)) 371 372 # interface 373 wrapper.__wrapped__ = user_function 374 wrapper.info = info 375 wrapper.clear = clear 376 #wrapper._cache = cache #XXX 377 #wrapper._queue = queue #XXX 378 return update_wrapper(wrapper, user_function) 379 380 return decorating_function 381 382 383 def rr_cache(maxsize=100, keymap=None, typed=False): 384 '''random-replacement cache decorator. 385 386 If *maxsize* is None, the RR algorithm will be supressed and this cache 387 will grow without bound. 388 389 If *typed* is True, arguments of different types will be cached separately. 390 For example, f(3.0) and f(3) will be treated as distinct calls with 391 distinct results. Cache typing has a memory penalty, and may also may be 392 ignored by some 'keymaps'. 393 394 If *keymap* is given, it will replace the hashing algorithm for generating 395 cache keys. For example, see the other hashing algorithms available in 396 'cache_helper.py'. With the default keymap, arguments to the cached 397 function must be hashable. 398 399 View the cache statistics named tuple (hits, misses, maxsize, currsize) with 400 f.info(). Clear the cache and statistics with f.clear(). Access the 401 underlying function with f.__wrapped__. 402 403 http://en.wikipedia.org/wiki/Cache_algorithms#Random_Replacement 404 405 ''' 406 if maxsize == 0: return no_cache() 407 if keymap is None: make_key = _keymap 408 else: make_key = keymap 409 if maxsize is None: return inf_cache(keymap=make_key, typed=typed) 410 411 def decorating_function(user_function): 412 cache = dict() # mapping of args to results 413 stats = [0, 0] # make statistics updateable non-locally 414 HITS, MISSES = 0, 1 # names for the stats fields 415 _len = len # localize the global len() function 416 #lock = RLock() # linkedlist updates aren't threadsafe 417 418 def wrapper(*args, **kwds): 419 key = make_key(args, kwds, typed) 420 421 # get cache entry or compute if not found 422 try: 423 result = cache[key] 424 stats[HITS] += 1 425 except KeyError: 426 result = user_function(*args, **kwds) 427 cache[key] = result 428 stats[MISSES] += 1 429 430 # purge random cache entry 431 if _len(cache) > maxsize: 432 del cache[choice(cache.keys())] 433 return result 434 435 def clear(): 436 """Clear the cache and statistics""" 437 cache.clear() 438 stats[:] = [0, 0] 439 440 def info(): 441 """Report cache statistics""" 442 return _CacheInfo(stats[HITS], stats[MISSES], maxsize, len(cache)) 443 444 # interface 445 wrapper.__wrapped__ = user_function 446 wrapper.info = info 447 wrapper.clear = clear 448 #wrapper._cache = cache #XXX 449 #wrapper._queue = None #XXX 450 return update_wrapper(wrapper, user_function) 451 452 return decorating_function 453 454 455 def _test_hits(algorithm, maxsize=20, typed=False, rangelimit=5, tries=1000): 456 457 @algorithm(maxsize=maxsize, typed=typed) 115 458 def f(x, y): 116 459 return 3*x+y 117 460 118 domain = range( 5)461 domain = range(rangelimit) 119 462 domain += [float(i) for i in domain] 120 463 from random import choice 121 for i in range( 1000):464 for i in range(tries): 122 465 r = f(choice(domain), choice(domain)) 123 466 124 467 print (f.info()) 125 468 469 470 if __name__ == '__main__': 471 472 for cache in [rr_cache, mru_cache, lru_cache, lfu_cache, inf_cache]: 473 print cache.__name__, ":", 474 _test_hits(cache, maxsize=1000, rangelimit=50) 475 476 477 # EOF
Note: See TracChangeset
for help on using the changeset viewer.