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 <tart...@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 tart...@tartley.com http://tartley.com
> Made of meat. +44 7737 062 225 twitter/skype: tartley
>
>
> ______________________________**_________________
> python-uk mailing list
> python-uk@python.org
> http://mail.python.org/**mailman/listinfo/python-uk<http://mail.python.org/mailman/listinfo/python-uk>
>
_______________________________________________
python-uk mailing list
python-uk@python.org
http://mail.python.org/mailman/listinfo/python-uk
