Re: [Python-ideas] Using functools.lru_cache only on some arguments of a function
(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_cach... 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_cach...) 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)
participants (2)
-
Franklin? Lee
-
Michael Selik