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

[Michael Selik]

I saw that Bill previously considered and rejected the idea of a class on
the Reddit thread, calling it unpythonic and musing about changing the
keying function of lru_cache. It seems to me that while recursion is the
hallmark of functional style, shared state is a major feature of object
orientation. This example seems particularly appropriate for the blend of
the two styles -- a recursive function housed in a class.

To reduce the chances someone creates a second instance of the class,
wasting the cached results of the first instance, one could wrap an
instance in a plain module-level function.

def recurse(*args, state=None):
    recurse.instance.state = state
    return recurse.instance.recurse(*args)
recurse.instance = MethodsHaveCaches()

Good, Bad, Ugly?


On Sat, Dec 5, 2015 at 3:15 AM Michael Selik <mike at selik.org> wrote:

> The source (https://hg.python.org/cpython/file/3.5/Lib/functools.py)
> warns on lines 411-414 that one should only use the public API for
> thread-safety and forwards-compatibility with a possible C version.
>
> Why not encapsulate the recursive function and its persistent state in a
> class?
>
>     from functools import lru_cache
>
>     class Fibonacci:
>         'the classic recursion example'
>
>         def __init__(self, shortcut=False):
>             self.shortcut = shortcut
>
>         @lru_cache()
>         def nth(self, n):
>             if self.shortcut: return -1
>             if n == 0: return 0
>             if n == 1: return 1
>             return self.nth(n-1) + self.nth(n-2)
>
>
> On Fri, Dec 4, 2015 at 7:59 PM Ryan Gonzalez <rymg19 at gmail.com> wrote:
>
>> http://thecodelesscode.com/topics/caching
>>
>> This smells like something that could cause trouble to me... If it's in
>> the stdlib, it's easier for someone to use it and then be confused when
>> something doesn't work correctly (maybe someone else will make
>> partial_state affect the result, not realizing that that argument is
>> ignored).
>>
>> Too buggy to me.
>>
>> On December 4, 2015 3:44:18 PM CST, Bill Winslow <bunslow at gmail.com>
>> 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.)
>>>
>>> I want to memoize this function for obvious reasons, but I need the
>>> lru_cache to ignore the partial_state argument, for its value does not
>>> affect the output, only the computation expense.
>>>
>>> Is there any reasonable way to do this?
>>>
>>> Things such as memoizing a wrapper don't actually solve the problem.
>>> About the only way I can think of with current technology is either to have
>>> a hidden singleton class which maintains state, or a hidden global
>>> variable, which amount to the same thing of storing the partial state
>>> outside the function. But those strike me as unwieldy and unpythonic.
>>>
>>> What I'd really like to do is to have some way to tell
>>> functools.lru_cache to ignore some arguments of a function it's memoizing
>>> for the purposes of caching.
>>>
>>> One way would be to add an "arg_filter" argument, which for purposes of
>>> this example would be used like so:
>>>
>>> @lru_cache(arg_filter=lambda args, kwargs: args[:1], {})
>>> def deterministic_recursive_calculation(input, partial_state=None):
>>>     condition = do_some_calculations(input)
>>>     if condition:
>>>         return deterministic_recursive_calculation(reduced_input,
>>> some_state)
>>>
>>> This effectively ignores all arguments except the first positional one
>>> for the purposes of caching. Such an option could be implemented as in the
>>> diff below (provided only for discussion purposes).
>>>
>>> So what I want to know is:
>>> 1) Am I sane? Is there no particularly good way currently to go about
>>> caching functions following the given pattern?
>>> 2) Assuming the answer to 1) is "Yes I am sane, and there's no good way
>>> currently", is my proposal a reasonable one? Mostly on philosophical
>>> grounds, not necessarily specifics of how it works.
>>>
>>> Thank you for your time and consideration.
>>>
>>> Bill
>>>
>>>
>>> ----------------------------------------------------------------------------------------------------------------------------------
>>> https://hg.python.org/cpython/file/3.5/Lib/functools.py
>>>
>>> diff functools.py functools.py.orig
>>> 363c363
>>> < def _make_key(args, kwds, typed, arg_filter,
>>> ---
>>> > def _make_key(args, kwds, typed,
>>> 377,378d376
>>> <     if arg_filter is not None:
>>> <         args, kwds = arg_filter(args, kwds)
>>> 393c391
>>> < def lru_cache(maxsize=128, typed=False, arg_filter=None):
>>> ---
>>> > def lru_cache(maxsize=128, typed=False):
>>> 403,406d400
>>> <     *arg_filter* is an optional function which filters user-speicified
>>> portions
>>> <     of the arguments from the caching key (e.g. if an argument affects
>>> the
>>> <     computation but not the final result).
>>> <
>>> 428,430d421
>>> <     if arg_filter is not None and not callable(arg_filter):
>>> <         raise TypeError('Expected arg_filter to be a callable')
>>> <
>>> 432,433c423
>>> <         wrapper = _lru_cache_wrapper(user_function, maxsize, typed,
>>> arg_filter,
>>> <                                      _CacheInfo)
>>> ---
>>> >         wrapper = _lru_cache_wrapper(user_function, maxsize, typed,
>>> _CacheInfo)
>>> 438c428
>>> < def _lru_cache_wrapper(user_function, maxsize, typed, arg_filter,
>>> _CacheInfo):
>>> ---
>>> > def _lru_cache_wrapper(user_function, maxsize, typed, _CacheInfo):
>>> 466c456
>>> <             key = make_key(args, kwds, typed, arg_filter)
>>> ---
>>> >             key = make_key(args, kwds, typed)
>>> 481c471
>>> <             key = make_key(args, kwds, typed, arg_filter)
>>> ---
>>> >             key = make_key(args, kwds, typed)
>>>
>>>
>>>
>>>
>>> Python-ideas mailing list
>>> Python-ideas at python.org
>>> https://mail.python.org/mailman/listinfo/python-ideas
>>> Code of Conduct: http://python.org/psf/codeofconduct/
>>>
>>>
>> --
>> Sent from my Nexus 5 with K-9 Mail. Please excuse my brevity.
>> _______________________________________________
>> Python-ideas mailing list
>> Python-ideas at python.org
>> https://mail.python.org/mailman/listinfo/python-ideas
>> Code of Conduct: http://python.org/psf/codeofconduct/
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20151205/99481d62/attachment-0001.html>