dictionary interface

[Steve Holden]

Antoon Pardon wrote:
> Op 2005-10-05, Tom Anderson schreef <twic at urchin.earth.li>:
> 
>>On Tue, 4 Oct 2005, Robert Kern wrote:
>>
>>
>>>Antoon Pardon wrote:
>>>
>>>
>>>>  class Tree:
>>>>
>>>>    def __lt__(self, term):
>>>>      return set(self.iteritems()) < set(term.iteritems())
>>>>
>>>>    def __eq__(self, term):
>>>>      return set(self.iteritems()) == set(term.iteritems())
>>>>
>>>>Would this be a correct definition of the desired behaviour?
>>>
>>>No.
>>>
>>>In [1]: {1:2} < {3:4}
>>>Out[1]: True
>>>
>>>In [2]: set({1:2}.iteritems()) < set({3:4}.iteritems())
>>>Out[2]: False
>>>
>>>
>>>>Anyone a reference?
>>>
>>>The function dict_compare in dictobject.c .
>>
>>Well there's a really helpful answer. I'm intrigued, Robert - since you 
>>know the real answer to this question, why did you choose to tell the 
>>Antoon that he was wrong, not tell him in what way he was wrong, certainly 
>>not tell him how to be right, but just tell him to read the source, rather 
>>than simply telling him what you knew? Still, at least you told him which 
>>file to look in. And if he knows python but not C, or gets lost in the 
>>byzantine workings of the interpreter, well, that's his own fault, i 
>>guess.
>>
>>So, Antoon, firstly, your implementation of __eq__ is, i believe, correct.
>>
>>Your implementation of __lt__ is, sadly, not. While sets take "<" to mean 
>>"is a proper subset of", for dicts, it's a more conventional comparison 
>>operation, which constitutes a total ordering over all dicts (so you can 
>>sort with it, for example). However, since dicts don't really have a 
>>natural total ordering, it is ever so slightly arbitrary.
>>
>>The rules for ordering on dicts are, AFAICT:
>>
>>- If one dict has fewer elements than the other, it's the lesser
>>- If not, find the smallest key for which the two dicts have different 
>>values (counting 'not present' as a value)
>>-- If there is no such key, the dicts are equal
>>-- If the key is present in one dict but not the other, the dict in which 
>>it is present is the lesser
>>-- Otherwise, the dict in which the value is lesser is itself the lesser
>>
>>In code:
>>
>>def dict_cmp(a, b):
>> 	diff = cmp(len(a), len(b))
>> 	if (diff != 0):
>> 		return diff
>> 	for key in sorted(set(a.keys() + b.keys())):
>> 		if (key not in a):
>> 			return 1
>> 		if (key not in b):
>> 			return -1
>> 		diff = cmp(a[key], b[key])
>> 		if (diff != 0):
>> 			return diff
>> 	return 0
>>
> 
> 
> Thanks for the explanation, but you somehow give me too much.
> 
> I have been searching some more and finally stumbled on this:
> 
> http://docs.python.org/ref/comparisons.html
> 
>   Mappings (dictionaries) compare equal if and only if their sorted
>   (key, value) lists compare equal. Outcomes other than equality are
>   resolved consistently, but are not otherwise defined.
> 
> This seems to imply that the specific method to sort the dictionaries
> is unimported (as long as it is a total ordering). So I can use whatever
> method I want as long as it is achieves this.
> 
> But that is contradicted by the unittest. If you have a unittest for
> comparing dictionaries, that means comparing dictionaries has a
> testable characteristic and thus is further defined.
> 
> So I don't need a full implementation of dictionary comparison,
> I need to know in how far such a comparison is defined and
> what I can choose.
> 
The dict unit tests are probably trying to ensure that the dictionary 
ordering doesn't change from version to version, which is probably a 
good idea in case someone (foolishly?) deciess to rely on it.

I can't help wondering, though, under what conditions it actually makes 
sense to compare two dictionaries for anything other than equality.

regards
  Steve
-- 
Steve Holden       +44 150 684 7255  +1 800 494 3119
Holden Web LLC                     www.holdenweb.com
PyCon TX 2006                  www.python.org/pycon/