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

[Franklin? Lee]

On Sat, Dec 12, 2015 at 1:34 PM, Michael Selik <mike at selik.org> wrote:
> On Fri, Dec 11, 2015, 8:20 PM Franklin? Lee <leewangzhong+python at gmail.com>
> wrote:
>>
>> By the way, there are other usecases for ignoring arguments for
>> caching. For example, dynamic programming where the arguments are the
>> indices of a sequence, or some other object (tree?) which isn't a
>> recursive argument. I recommend that those also be done with a closure
>> (separating the recursive part from the initial arguments), but I
>> think it's worth considering an lru_cache implementation for students
>> who haven't learned to, er, abuse closures. Unless someone thinks a
>> recipe can/should be added to the docs.
>
>
> This whole thing is probably best implemented as two separate functions
> rather than using a closure, depending on how intertwined the code paths are
> for the shortcut/non-shortcut versions.

I like the closure because it has semantic ownership: the inner
function is a worker for the outer function.

Also, with many dynamic programming problems which have a
non-recursive variable, if you don't have a closure, you would need
global state instead. Here's an example:

    inf = float('inf')

    def max_nonconsecutive_subset_sum(lst, n):
        """ Returns the biggest possible sum of n non-consecutive items.
        """

        def rec(i, k):
            """
            i: index
            k: number of items summed so far
            """
            if k == n: # Stop summing
                return 0
            if i == len(lst): # Reached end of list
                return -inf

            return max(rec(i+1, k), rec(i+2, k+1) + lst[i])

        return rec(0, 0)


(We can also shortcut out if there aren't enough items left to take k
of them, and calculate length only once, but it's not needed for
correctness.)

There should be no significant cost for the closure, as the recursive
part should be the bulk of the work.


>> On Fri, Dec 11, 2015 at 8:01 PM, Franklin? Lee
>> <leewangzhong+python at gmail.com> wrote:
>> > Solutions:
>> > 1. Rewrite your recursive function so that the partial state is a
>> > nonlocal variable (in the closure), and memoize the recursive part.
>
>
> I'd flip the rare-case to the except block and put the normal-case in the
> try block. I believe this will be more compute-efficient and more readable.

The rare case is in the except block, though.