[Python-ideas] Using functools.lru_cache only on some arguments of a function

[Franklin? Lee]

(Replying to an email I didn't get in my inbox. I hope this goes
through correctly.)

On Friday, December 4, 2015 at 4:44:47 PM UTC-5, Bill Winslow wrote:
> This is a question I posed to reddit, with no real resolution: https://www.reddit.com/r/learnpython/comments/3v75g4/using_functoolslru_cache_only_on_some_arguments/
> The summary for people here is the following:
> Here's a pattern I'm using for my code:
> def deterministic_recursive_
calculation(input, partial_state=None):
>     condition = do_some_calculations(input)
>     if condition:
>         return deterministic_recursive_calculation(reduced_input, some_state)
> Basically, in calculating the results of the subproblem, the subproblem can be calculated quicker by including/sharing some partial results from the superproblem. (Calling the subproblem without the partial state still gives the same result, but takes substantially longer.)

Solutions:
1. Rewrite your recursive function so that the partial state is a
nonlocal variable (in the closure), and memoize the recursive part.
2. Attach the state to the function, rather than passing it as a
parameter. (Also suggested in this comment:
https://www.reddit.com/r/learnpython/comments/3v75g4/using_functoolslru_cache_only_on_some_arguments/cxr7cnp)
3. Wrap the state in a class for which __eq__ is defined to say that
all instances of it are the same, and __hash__ always returns a
constant (say, the id of the class).

I think #1 is the best: The state is a property of the current
recursive execution. You make a function which solves the problem, and
the recursive function is an inner function of the solver. The state
will be lost when you finish computing the answer.

If you want to keep the partial state even after the recursion
finished, then #2 is the right answer: the state is a property of the
solver.

I feel that #3 is icky and heavy-handed. The function won't be
semantically responsible for the state.

Hacking/extending lru_cache is saying the wrong thing about what the
partial state is. Cached information (which is what your state is)
isn't really an argument to the function as a mathematical
input-output box. Also, if you're calling this function multiple
times, you as the caller shouldn't be expected to keep track of the
cache, so you shouldn't be expected to store it (in global scope). But
if it's reusable, it should be stored, so the function should be
responsible for storing it.

If you want to keep the lru_cache, too, then you can store the
recursive function as an attribute. It will even keep itself and your
partial state in its closure.

Sample code so you can confirm that the state is stored between calls.
Just call solve(50) twice in a row, and compare the times.

# WARNING: I don't recommend x > 100.
#    I've killed two interpreters while messing with this.
def solve(x):
    try:
        rec = solve.rec # To trigger the exception the first time.
    except:
        @lru_cache(None)
        def rec(n, m):
            return sum(
                    rec(i, j)
                    for i in reversed(range(n))
                    for j in reversed(range(m)))
        solve.rec = rec
    return rec(x, x)