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

[Jonathan]

Thanks Ross.

The thing is, the 'kwargs' dict that callers pass in is not the same 
dict as the kwargs that my wrapper function receives. My 'wrapper' 
function always receives a brand-new dictionary, created from scratch as 
the function is invoked. Hence, the kwargs never has any 'history' - 
they are always newly created, from the keyword args passed in to the 
function. This, I suspect, is why their 'items()' always appear in the 
same order.

I tried calling 'wrapper' with keyword args in a different order:

     wrapper(x=1, y=2, z=3)
     wrapper(y=2, x=1, z=3)
     ...etc, for every permutation

and by passing in **kwargs dictionaries with different histories 
(detailed in my original mail):

     wrapper(**kwargs)

but in every case, inside wrapper...

     def wrapper(*args, **kwargs):
         print kwargs.items()

...the items call always returns the dictionary's content in the same 
order. So I *suspect*, but cannot yet prove, that the '**' mechanism is 
already sorting the keyword args used to construct the kwargs dictionary 
(or is doing some equivalent, such that the dicts always end up 
identical-including-order-of-items())

I agree that 'to be sure' is enough of a justification for including the 
'sorted' call anyway. But it irks me that I can't write a test to show it.

     Jonathan


On 11/11/2011 08:50, Ross Lawley wrote:
> Hi,
>
> From the docs: http://docs.python.org/library/stdtypes.html#dict.items
>
> "CPython implementation detail: Keys and values are listed in an 
> arbitrary order which is non-random, varies across Python 
> implementations, and depends on the dictionary's history of insertions 
> and deletions."
>
> Given that I would use sorted to guarantee order.  Then no matter what 
> anyone has done to the kwargs passed in the memoizing will not have a bug.
>
> Ross
>
> On Fri, Nov 11, 2011 at 8: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/830babbf/attachment-0001.html>