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

[Jonathan]

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