On Sat, Dec 12, 2015 at 1:34 PM, Michael Selik mike@selik.org wrote:
On Fri, Dec 11, 2015, 8:20 PM Franklin? Lee leewangzhong+python@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@gmail.com wrote:
Solutions:
- 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.