The Algorithms path turns slow recurrences into fast ones by remembering results. Write that idea once, as a decorator memoize that can be put above any recursive function, and make it report how much work it saved.
The decorated function returns the same results as the original and has these attributes:
cache: a dictionary from the tuple of positional arguments to the result;hits: how many calls were answered from the cache;misses: how many calls had to run the original function;cache_clear(): empties the cache and sets both counters back to0.
Two more rules make it safe:
- If an argument cannot be hashed (for example a list), the call runs the original function without using the cache, and it counts as neither a hit nor a miss.
- If the original function raises, the exception reaches the caller unchanged, nothing is stored, and the call counts as a miss. In particular, a
TypeErrorraised inside the function must not be mistaken for an unhashable argument.
The decorated function keeps the original's __name__. Setup helpers that decorate their own recurrences, available with Run: coin_ways(amount, coins), edit_distance(a, b), small_cache(), unhashable(), errors_inside(), flaky_then_fine() and raises(fn, *args).
Examples
Input: coin_ways(10, [5, 2, 1])
Output: (10, 34, 34, 7, 34)
Explanation: 10 ways; the body ran 34 times, and 7 calls were answered from the cache.
Input: unhashable()
Output: ([3, 3, 3, 3, 5], 4, 1, 1, 1)
Constraints
- Positional arguments only. Recursion depth stays below 400.
- Do not use
functools.cacheorfunctools.lru_cache: the attributes above are yours to provide.
Goals
- Write a memoising decorator that stores results by their argument tuple
- Report hits and misses so the effect of the cache can be measured
- Handle arguments that cannot be cached and results that must not be cached