deferred_lfu_cache

cache.py

import collections
import functools
from itertools import ifilterfalse
from heapq import nsmallest
from operator import itemgetter
from twisted.internet.defer import maybeDeferred, succeed, Deferred

class Counter(dict):
    'Mapping where default values are zero'
    def __missing__(self, key):
        return 0

def deferred_lfu_cache(maxsize=100):
    '''Least-frequenty-used cache decorator.

    Arguments to the cached function must be hashable.
    Cache performance statistics stored in f.hits and f.misses.
    Clear the cache with f.clear().
    http://en.wikipedia.org/wiki/Least_Frequently_Used

    '''
    def decorating_function(user_function):
        cache = {}                      # mapping of args to results
        use_count = Counter()           # times each key has been accessed
        kwd_mark = object()             # separate positional and keyword args
        waiting = {}

        @functools.wraps(user_function)
        def wrapper(*args, **kwds):
            key = args
            if kwds:
                key += (kwd_mark,) + tuple(sorted(kwds.items()))
            use_count[key] += 1

            if key in cache:
                wrapper.hits += 1
                return succeed((cache[key], True))
            elif key in waiting:
                d = Deferred()
                waiting[key].append(d)
                return d
            else:
                def success(result, key):
                    wrapper.misses += 1
                    cache[key] = result
                    if len(cache) > maxsize:
                        for key, _ in nsmallest(maxsize // 10,
                                                use_count.iteritems(),
                                                key=itemgetter(1)):
                            del cache[key], use_count[key]
                    
                    wrapper.hits -= 1
                    
                    for d in waiting[key]:
                        wrapper.hits += 1
                        d.callback((result, False))
                        
                    del waiting[key]
                
                def err(err, key):
                    for d in waiting[key]:
                        d.errback(err)
                    del waiting[key]
                
                maybeDeferred(user_function, *args, **kwds).addCallback(success, key).addErrback(err, key)
                
                d = Deferred()
                waiting[key] = [d]
                return d


        def clear():
            cache.clear()
            use_count.clear()
            wrapper.hits = wrapper.misses = 0

        wrapper.hits = wrapper.misses = 0
        wrapper.clear = clear
        wrapper.size = lambda: len(cache)
        wrapper.waiting = lambda: len(waiting)
        wrapper.maxsize = maxsize
        
        return wrapper
    
    return decorating_function