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

[Duncan Booth]

On Fri, Nov 11, 2011 at 8:50 AM, Ross Lawley <ross.lawley at gmail.com> wrote:
>> 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)]
>>
There are two ways to create dictionaries that are equal but have
their keys in different order. The way you used ends up with a very
sparse dictionary after you deleted the padding keys. When you call a
function it copies the kwargs dictionary so at that point the
sparseness is lost as is your artificial key ordering.

The other way is simply to pick keys that that hash to the same value
modulo the size of the dictionary. Since the dictionary copy copies
the keys in the order they are stored you will get the same hash
conflict in the copy as the original.

>> Is 'sorted' really required? If so, how can I write a test to demonstrate
>> it?

This should help you:

>>> def foo(**kw):
	print(kw)

	
>>> foo(a=None, i=None)
{'a': None, 'i': None}
>>> foo(i=None, a=None)
{'i': None, 'a': None}
>>>

And here's an easy way to find some conflicts. You could use this code
to find a conflict instead of hardwiring the argument names in the
test.

>>> for p, q in itertools.product(ascii_letters, ascii_letters):
	d1, d2 = {p:None, q:None}, {q:None, p:None}
	if repr(d1) != repr(d2):
		print(d1)
		count += 1
		if count > 20:
			break

		
{'a': None, 'i': None}
{'a': None, 'q': None}
{'a': None, 'y': None}
{'a': None, 'A': None}
{'a': None, 'I': None}
{'a': None, 'Q': None}
{'a': None, 'Y': None}
{'b': None, 'j': None}
{'b': None, 'z': None}
{'c': None, 'k': None}
{'c': None, 's': None}
{'c': None, 'C': None}
{'c': None, 'K': None}
{'c': None, 'S': None}
{'d': None, 'l': None}
{'d': None, 't': None}
{'d': None, 'D': None}
{'d': None, 'L': None}
{'d': None, 'T': None}
{'m': None, 'e': None}
{'u': None, 'e': None}