Re: memoize & ordering of kwargs.items()

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

Re: memoize & ordering of kwargs.items()

Jonathan Hartley
oops. wrong list. sorry all. The question still stands though, if
anyone's interested.

On 11/11/2011 08:42, Jonathan wrote:

> Hey,
>
> I've been writing my own 'memoize' function a lot recently - I'm using
> it as an interview question.
>
> Here's what I've got (with a corresponding series of tests):
>
>     def memoize(wrapped):
>
>         cache = {}
>
>         @wraps(wrapped)
>         def wrapper(*args, **kwargs):
>             key = (args, tuple(kwargs.items()))
>             if key not in cache:
>                 cache[key] = wrapped(*args, **kwargs)
>             return cache[key]
>
>         return wrapper
>
> Yesterday a candidate pointed out that this is wrong because .items()
> for two equal dictionaries might return the (key,value) pairs in a
> different order, presumably dependent on the respective dictionary's
> history. This would produce a different 'key' and hence an erroneous
> cache miss.
>
> This implies that the second line of 'wrapper' should become:
>
>               key = (args, tuple(sorted(kwargs.items())))
>
> (I've added 'sorted')
> Looking at lru_cache, I see that is exactly how it is implemented there.
> http://hg.python.org/cpython/file/default/Lib/functools.py
>
> However, I'm unable to come up with a test that proves this is
> necessary. I'm can create two equal dictionaries which return their
> .items() in a different order:
>
>         # The intent is that 'small.items()' comes out in a different
> order
>         # than 'large.items()'
>         small = {'x':1, 'y':5}
>         large = {hex(i): i for i in range(257)}
>         large.update(small)
>         for i in range(257):
>             del large[hex(i)]
>
> >>> print small.items()
>     [('y', 5), ('x', 1)]
> >>> print large.items()
>     [('x', 1), ('y', 5)]
>
> If I could magically transfer these dictionaries directly into the
> 'kwargs' of wrapper, then I think I'd be done. However, I have to pass
> these dictionaries in to wrapper via the '**' mechanism. Printing
> 'kwargs.items()' within 'wrapper' shows that equal dictionaries always
> return their items in the same order, so the 'sorted' call is
> apparently not necessary.
>
> Is 'sorted' really required? If so, how can I write a test to
> demonstrate it?
>
> Best regards,
>
>     Jonathan
>

--
Jonathan Hartley    [hidden email]    http://tartley.com
Made of meat.       +44 7737 062 225       twitter/skype: tartley


_______________________________________________
python-uk mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-uk