[python-uk] memoize & ordering of kwargs.items()

[Jonathan]

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    tartley at tartley.com    http://tartley.com
Made of meat.       +44 7737 062 225       twitter/skype: tartley