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

Jonathan tartley at tartley.com
Fri Nov 11 10:30:23 CET 2011

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):


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 

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.


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>

More information about the python-uk mailing list