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

[Jonathan]

That's good to know René, but I *think* it's orthogonal to the question. 
Please correct me if I'm wrong.

If PyPy returns items in a different order than CPython, that doesn't 
matter to me, so long as every invocation of my function in a particular 
process ends up receiving a particular  order, that doesn't change until 
the process ends (or the cache is cleared.)

The dict subclass is a great idea - but if the change in order isn't 
ever manifested by a regular dict, then it implies to me that the 
'sorted' call isn't actually required in real life, so the need for this 
whole test disappears.

See also my imminent reply to Ross.

     Jonathan


On 11/11/2011 08:49, René Dudfield wrote:
> Good morning,
>
> 1. Run it on different versions of python, or on different 
> machines/OSes.  That usually results in different dictionary ordering.
> 2. create a dict subclass that returns items always randomised.
>
>     class my_fun_randomising_item_dict_subclass(dict):
>         def items(self):
>             return random.shuffle(dict.items(self, key))
>     def make_key(kwargs):
>         return (args, 
> tuple(sorted(my_fun_randomising_item_dict_subclass(kwargs).items())))
>
> cheers,
>
> On Fri, Nov 11, 2011 at 9:42 AM, Jonathan <tartley at tartley.com 
> <mailto:tartley at tartley.com>> 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 <mailto:tartley at tartley.com>
>     http://tartley.com
>     Made of meat. +44 7737 062 225 <tel:%2B44%207737%20062%20225>    
>       twitter/skype: tartley
>
>
>     _______________________________________________
>     python-uk mailing list
>     python-uk at python.org <mailto:python-uk at python.org>
>     http://mail.python.org/mailman/listinfo/python-uk
>
>
>
>
> _______________________________________________
> python-uk mailing list
> python-uk at python.org
> http://mail.python.org/mailman/listinfo/python-uk

-- 
Jonathan Hartley    tartley at tartley.com    http://tartley.com
Made of meat.       +44 7737 062 225       twitter/skype: tartley


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-uk/attachments/20111111/03c6a903/attachment.html>