[docs] [issue9132] Documentation for comparing dictionaries is out of date

Terry J. Reedy report at bugs.python.org
Sun Jul 4 21:07:22 CEST 2010

Terry J. Reedy <tjreedy at udel.edu> added the comment:

On the 'patch' keyword: I thought the same as you (only for diff) until yesterday morning when Brett Cannon specifically told me that I should also set it for in-message text patches. This was in the context of him having not noticed for months (until I pinged him) that I had included a text patch in a message for an issue assigned to him, because he skims messages and looks for the keyword and other header changes. So until a 'higher' tracker authority tell me differently, I am following his direction. I am also highlighting the actual patch in the message to make it easy to find.

The current "compare equal if and only if their sorted (key, value) lists compare equal. [4]" was written when all objects were comparable and when dict == dict *was* written that way (according to [5]). The footnote was added to assure people that the new internal implementation was faster (ie, set comparison via hash lookup) than it once had been.

For a long time, that definition of dict equality has been invalid because it cannot be implemented that way; the definition is even more meaningless in Python3. So is footnote [4] saying that the meaningless definition is not the implementation. Both [4] and [5] are ancient fossils referring back to Python1. 

Without looking, I am confident that the actual implementation is O(1) if the dicts are unequal in size and an O(n) (key,value) set comparison if they are equal in size. My proposed revision is intended to imply that. Note that Python did not have sets when the sorted list definition was written. Also note that there is no footnote attached to set comparison (which once could have also been defined in terms of sorted lists).

Dicts are sets (of pairs), not unsorted lists (of pairs) and the current docs should reflect that.

The language def makes no guarantees about implementation efficiency.  In 13 years of watching c.l.p/python-list, I have not seen any particular concern about dict comparison that would warrant special notice. Rather, people worry about the big-O behavior of building large lists and dicts of millions of items. The sometimes need persuading that construction is more efficient than they might imagine. That is about the only thing I can think of for which an efficiency note might be a good idea.

'Comparisons other than equality testing' include 'is' and 'in'. They work for dictionaries as expected, which is to say, as identify and containment testing, as for everything else. They do not raise TypeError. So the statement that implies that they do is not correct.

PATCH REVISION: The suggested "Order comparision raise TypeError." has spelling and agreement errors in 'comparision' and should be "Order comparisons raise TypeError."


Python tracker <report at bugs.python.org>

More information about the docs mailing list