6

#6
import collections
import functools
import time
from collections import Counter

from heapq import nsmallest
from operator import itemgetter
def lru_cache(n,maxsize=100):
    if n ==1:

        def decorating_function(user_function):
            cache = collections.OrderedDict()    # order: least recent to most recent

            @functools.wraps(user_function)
            def wrapper(*args, **kwds):
                key = args
                if kwds:
                    key += tuple(sorted(kwds.items()))
                try:
                    result = cache.pop(key)
                    wrapper.hits += 1
                except KeyError:
                    result = user_function(*args, **kwds)
                    wrapper.misses += 1
                    if len(cache) >= maxsize:
                        cache.popitem(0)    # purge least recently used cache entry
                cache[key] = result         # record recent use of this key
                return result
            wrapper.hits = wrapper.misses = 0
            return wrapper
        return decorating_function
    else:
        def decorating_function(user_function):
            cache = {}  # mapping of args to results
            use_count = Counter()  # times each key has been accessed
            kwarg_mark = object()  # separate positional and keyword args

            @functools.wraps(user_function)
            def wrapper(*args, **kwargs):
                key = args
                if kwargs:
                    key += (kwarg_mark,) + tuple(sorted(kwargs.items()))

                # get cache entry or compute if not found
                try:
                    result = cache[key]
                    use_count[key] += 1
                    wrapper.hits += 1
                except KeyError:
                    # need to add something to the cache, make room if necessary
                    if len(cache) == maxsize:
                        for k, _ in nsmallest(maxsize // 10 or 1,
                                              use_count.iteritems(),
                                              key=itemgetter(1)):
                            del cache[k], use_count[k]
                    cache[key] = user_function(*args, **kwargs)
                    result = cache[key]
                    use_count[key] += 1
                    wrapper.misses += 1
                return result

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

            wrapper.hits = wrapper.misses = 0
            wrapper.clear = clear
            wrapper.cache = cache
            return wrapper

        return decorating_function
@lru_cache(n=2,maxsize=3)
def fibonacci(n):
    time.sleep(0.5)
    if n < 2: return n

    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(50))
print(fibonacci(50))