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

[Ross Lawley]

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> 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<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
>
>
> ______________________________**_________________
> python-uk mailing list
> python-uk at python.org
> http://mail.python.org/**mailman/listinfo/python-uk<http://mail.python.org/mailman/listinfo/python-uk>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-uk/attachments/20111111/dbf7a294/attachment-0001.html>