Problem 539175 · hard · Level 05 Advanced Algorithms & Graphs

A Cache That Forgets the Oldest Idea

py-decorators · py-stdlib · LRU cache · OrderedDict · inspect.signature · memoisation

An unlimited cache can use more memory than a long computation can afford. Write a decorator factory lru_memo(maxsize) that memoises a function but keeps at most maxsize results, forgetting the one that was least recently used when it needs room.

  • Keys. Calls that mean the same thing share one entry: for def power(base, exp=2), the calls power(3), power(3, 2), power(base=3) and power(exp=2, base=3) are all the key (3, 2), the argument values in the order of the function's parameters, with defaults filled in.
  • Hits. A call whose key is cached returns the stored result without running the function, and makes that entry the most recently used.
  • Misses. Otherwise the function runs. When it returns, its result is stored as the most recently used entry, and if the cache now holds more than maxsize entries, the least recently used one is removed. A call that raises stores nothing (it still counts as a miss).
  • maxsize=None means no limit. Any other maxsize that is not at least 1 raises ValueError when lru_memo is called.

The decorated function keeps its __name__ and has two methods: info() returns (hits, misses, current number of entries), and cache_keys() returns the list of keys from least to most recently used.

Setup helpers that decorate their own recurrences, available with Run: choose_runs(n, k, maxsize) (binomial coefficients), staircase(n, maxsize), keyword_forms(), mixed_forms(n), recency(), sizes(), failures() and raises(fn, *args). Each reports body runs, info() or cache_keys().

Examples

Input:  keyword_forms()
Output: ([9, 9, 9, 9, 9, 8], 2, (4, 2, 2), [(3, 2), (2, 3)], "power")

Input:  recency()
Output: ([[(1,)], [(1,), (2,)], [(2,), (1,)], [(1,), (3,)], [(3,), (2,)], [(3,), (2,)], [(2,), (1,)]], (2, 5, 2))

Constraints

  • Decorated functions have ordinary parameters (no *args or **kwargs), and their arguments are hashable.
  • Recursion depth stays below 300. Up to 10**5 calls per test.

Goals

  • Build a memoising decorator with a size limit and least-recently-used eviction
  • Normalise positional, keyword and default arguments into one cache key
  • Measure a cache by its hits, misses and contents instead of by the clock
Starting Python…